Statistical Zero-Knowledge Arguments for NP from Any One-Way Function.
Fault-Tolerant Distributed Computing in Full-Information Networks.
Explicit Exclusive Set Systems with Applications to Broadcast Encryption.
A simple condition implying rapid mixing of single-site dynamics on spin systems.
Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body.
Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization.
A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks.
Strategic Network Formation through Peering and Service Agreements.
Towards Secure and Scalable Computation in Peer-to-Peer Networks.
Lp metrics on the Heisenberg group and the Goemans-Linial conjecture.
Ramsey partitions and proximity data structures.
Algorithms on negatively curved spaces.
Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method.
Improved Approximation Algorithms for Large Matrices via Random Projections.
Worst-case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-means Method.
The Effectiveness of Lloyd-Type Methods for the k-Means Problem.
Better lossless condensers through derandomized curve samplers.
Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification.
Index Coding with Side Information.
Subspace Polynomials and List Decoding of Reed-Solomon Codes.
SDP gaps and UGC-hardness for MAXCUTGAIN.
Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets.
Cryptography from Anonymity.
Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority.
Settling the Complexity of Two-Player Nash Equilibrium.
Minimum Bounded Degree Spanning Trees.
Approximate Min-Max Theorems of Steiner Rooted-Orientations of Hypergraphs.
Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach.
Improved Dynamic Planar Point Location.
Coresets forWeighted Facilities and Their Applications.
Planar Point Location in Sublogarithmic Time.
Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry.
Concurrent Non-Malleable Zero Knowledge.
Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP.
Input-Indistinguishable Computation.
Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders.
Lower Bounds for Additive Spanners, Emulators, and More.
Solving Evacuation Problems Efficiently--Earliest Arrival Flows with Multiple Sources.
New Limits on Fault-Tolerant Quantum Computation.
Postselection threshold against biased noise.
On the Quantum Query Complexity of Local Search in Two and Three Dimensions.
On the time complexity of 2-tag systems and small universal Turing machines.
On the Optimality of the Dimensionality Reduction Method.
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions.
Points on Computable Curves.
Local Graph Partitioning using PageRank Vectors.
Norm of the inverse of a random matrix.
Witnesses for non-satisfiability of dense random 3CNF formulas.
Accidental Algorthims.
The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels.
Algebraic Structures and Algorithms for Matching and Matroid Problems.
Hardness of Learning Halfspaces with Noise.
Cryptographic Hardness for Learning Intersections of Halfspaces.
New Results for Learning Noisy Parities and Halfspaces.
Inclusion--Exclusion Algorithms for Counting Set Partitions.
An O*(2^n ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion--Exclusion.
Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths.
Computing Nash Equilibria: Approximation and Smoothed Complexity.
On the Impact of Combinatorial Structure on Congestion Games.
Balanced Allocations of Cake.
On a Geometric Generalization of the Upper Bound Theorem.
Higher Lower Bounds for Near-Neighbor and Further Rich Problems.
Planar Earthmover is not in L_1.
Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e.
Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design.
How to Play Unique Games Using Embeddings.
Improved approximation algorithms for multidimensional bin packing problems.
Lower bounds for circuits with MOD_m gates.
On the Compressibility of NP Instances and Cryptographic Applications.
Dispersion of Mass and the Complexity of Randomized Geometric Algorithms.
An Omega(n<sup>1/3</sup>) Lower Bound for Bilinear Group Based Private Information Retrieval.
On the Unique Games Conjecture.
Algorithmic Techniques and Tools from Computational Geometry.
Agnostically Learning Halfspaces.
Noise stability of functions with low in.uences invariance and optimality.
Every decision tree has an in.uential variable.
Lower Bounds for the Noisy Broadcast Problem.
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l<sub>1</sub>.
The Closest Substring problem with small distances.
Fitting tree metrics: Hierarchical clustering and Phylogeny.
Metric Embeddings with Relaxed Guarantees.
Nonembeddability theorems via Fourier analysis.
On the Complexity of Two-PlayerWin-Lose Games.
Nash Equilibria in Random Games.
Query Incentive Networks.
Sink Equilibria and Convergence.
On the Complexity of Real Functions.
Linear Lower Bounds on Real-World Implementations of Concurrent Objects.
Towards a Final Analysis of Pairing Heaps.
Structuring labeled trees for optimal succinctness, and beyond.
Approximation Algorithms for Unique Games.
On Non-Approximability for Quadratic Programs.
Hardness of Approximating the Closest Vector Problem with Pre-Processing.
Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion.
A Recursive Greedy Algorithm for Walks in Directed Graphs.
Approximation Algorithms for Scheduling on Multiple Machines.
AdWords and Generalized On-line Matching.
The Parking Permit Problem.
Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time.
Error Correction via Linear Programming.
Error-Correcting Codes for Automatic Control.
Almost Orthogonal Linear Codes are Locally Testable.
On Delsarte's Linear Programming Bounds for Binary Codes.
Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method.
Improved Smoothed Analysis of the Shadow Vertex Simplex Method.
Sampling-based Approximation Algorithms for Multi-stage Stochastic.
How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems.
Group-theoretic Algorithms for Matrix Multiplication.
Answering distance queries in directed graphs using fast matrix multiplication.
A Randomness-Efficient Sampler for Matrix-valued Functions and Applications.
Deterministic Extractors for Affine Sources over Large Fields.
Additive Approximation for Edge-Deletion Problems.
A Characterization of the (natural) Graph Properties Testable with One-Sided Error.
An Algorithmic Version of the Hypergraph Regularity Method.
Cryptography In the Bounded Quantum-Storage Model.
Quantum Information and the PCP Theorem.
From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups.
The Symmetric Group Defies Strong Fourier Sampling.
On Learning Mixtures of Heavy-Tailed Distributions.
Learning mixtures of product distributions over discrete domains.
A general lower bound for mixing of single-site dynamics on graphs.
Analysis and Prediction of the Long-Run Behavior of Probabilistic Sequential Programs with Recursion (Extended Abstract).
Safraless Decision Procedures.
How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation.
On the Impossibility of Obfuscation with Auxiliary Input.
Concurrent Non-Malleable Commitments.
The Complexity of Online Memory Checking.
Rational Secure Computation and Ideal Mechanism Design.
Truthful and Near-Optimal Mechanism Design via Linear Programming.
Mechanism Design via Machine Learning.
Beyond VCG: Frugality of Truthful Mechanisms.
An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs.
Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring.
A linear-time approximation scheme for planar weighted TSP.
A Tale of Two Dimensional Bin Packing.
Quantum Weak Coin-Flipping with Bias of 0.192.
Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs.
Quantum Walk Algorithm for Element Distinctness.
Quantum Speed-Up of Markov Chain Based Algorithms.
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation.
Maximizing Quadratic Programs: Extending Grothendieck's Inequality.
An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem.
Edge-Disjoint Paths in Planar Graphs.
Machine Minimization for Scheduling Jobs with Interval Constraints.
Random Edge Can Be Exponential on Abstract Cubes.
On the Integrality Ratio for Asymmetric TSP.
The Hardness of Metric Labeling.
Hardness of Buy-at-Bulk Network Design.
Hardness of Approximating the Shortest Vector Problem in Lattices.
Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique.
Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem.
Cryptography in NC<sup>0</sup>.
An Unconditional Study of Computational Zero Knowledge.
Universally Composable Protocols with Relaxed Set-Up Assumptions.
On the (Im)possibility of Cryptography with Imperfect Randomness.
Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity.
An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design.
Stochastic Optimization is (Almost) as easy as Deterministic Optimization.
0(sqrt (log n)) Approximation to SPARSEST CUT in &Otilde;(n<sup>2</sup>) Time.
Maximum Matchings via Gaussian Elimination.
Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game.
Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users.
Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games.
A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities.
The Price of Stability for Network Design with Fair Cost Allocation.
Holographic Algorithms (Extended Abstract).
Hierarchy Theorems for Probabilistic Polynomial Time.
Private Codes or Succinct Random Codes That Are (Almost) Perfect.
On the List and Bounded Distance Decodibility of the Reed-Solomon Codes (Extended Abstract).
Multilinear-NC neq Multilinear-NC.
Algebras with Polynomial Identities and Computing the Determinant.
Lattice Problems in NP cap coNP.
Worst-Case to Average-Case Reductions Based on Gaussian Measures.
Extracting Randomness Using Few Independent Sources.
Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed.
Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap.
Testing Polynomials over General Fields.
Testing Low-Degree Polynomials over Prime Fields.
Measured Descent: A New Embedding Method for Finite Metrics.
Triangulation and Embedding Using Small Sets of Beacons.
A Simple Linear Time (1+ ) -Approximation Algorithm for k-Means Clustering in Any Dimensions.
On the Power of Discrete and of Lexicographic Helly-Type Theorems.
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching.
Dynamic Optimality -- Almost.
No Sorting? Better Searching!
Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs.
Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract).
Dynamic Speed Scaling to Manage Energy and Temperature.
Optimal Power-Down Strategies.
On the Streaming Model Augmented with a Sorting Primitive.
Approximating Edit Distance Efficiently.
trong Spatial Mixing for Lattice Graphs with Fewer Colours.
Shuffling by Semi-Random Transpositions.
Randomly Coloring Constant Degree Graphs.
The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem.
Spectral Analysis of Random Graphs with Skewed Degree Distributions.
Learning with Errors in Answers to Membership Queries.
Learnability and Automatizability.
Machine Learning: My Favorite Results, Directions, and Open Problems.
Mixing.
Performance Analysis of Dynamic Network Processes.
A Polynomial Algorithm for Recognizing Perfect Graphs.
On Certain Connectivity Properties of the Internet Topology.
Paths, Trees, and Minimum Latency Tours.
Approximation Algorithms for Orienteering and Discounted-Reward TSP.
Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs.
On the Implementation of Huge Random Objects.
Zero-Knowledge Sets.
Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography.
On the (In)security of the Fiat-Shamir Paradigm.
Locally Testable Cyclic Codes.
List-Decoding Using The XOR Lemma.
On e-Biased Generators in NC0.
Proving Hard-Core Predicates Using List Decoding.
Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model.
Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem.
Always Good Turing: Asymptotically Optimal Probability Estimation.
Learning DNF from Random Walks.
Quantum Search of Spatial Regions.
A Lattice Problem in Quantum NP.
A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness.
Polynomial Degree vs. Quantum Query Complexity.
An In-Place Sorting with O(n log n) Comparisons and O(n) Moves.
Breaking a Time-and-Space Barrier in Constructing Full-Text Indices.
I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs.
The Cost of Cache-Oblivious Searching.
Tight Lower Bounds for the Distinct Elements Problem.
Hardness of Approximating the Shortest Vector Problem in High Lp Norms.
More on Average Case vs Approximation Complexity.
On Worst-Case to Average-Case Reductions for NP Problems.
Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.
The Resolution Complexity of Random Constraint Satisfaction Problems.
Algorithms and Complexity Results for #SAT and Bayesian Inference.
Linear Upper Bounds for Random Walk on Small Density Random 3-CNF.
On the Maximum Satisfiability of Random Formulas.
Logics for Reasoning about Cryptographic Constructions.
Lower Bounds for Non-Black-Box Zero Knowledge.
General Composition and Universal Composability in Secure Multi-Party Computation.
Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds.
Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m<sup>1.31</sup>).
Separating the Power of Monotone Span Programs over Different Fields.
A Group-Theoretic Approach to Fast Matrix Multiplication.
Symmetric Polynomials over Z<sub>m</sub> and Simultaneous Communication Protocol.
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm.
Stability and Efficiency of a Random Local Load Balancing Protocol.
Gossip-Based Computation of Aggregate Information.
Broadcasting Algorithms in Radio Networks with Unknown Topology.
Switch Scheduling via Randomized Edge Coloring.
On the Impossibility of Dimension Reduction in l<sub>1</sub>.
Clustering with Qualitative Information.
Bounded Geometries, Fractals, and Low-Distortion Embeddings.
On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences.
The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side.
Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem.
Towards a Characterization of Truthful Combinatorial Auctions.
Group Strategyproof Mechanisms via Primal-Dual Algorithms.
The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions.
Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem.
A Non-Markovian Coupling for Randomly Sampling Colorings.
The Ising Model on Trees: Boundary Conditions and Mixing Time.
Logconcave Functions: Geometry and Efficient Sampling Algorithms.
Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm.
Zero-Knowledge.
Randomness Extractors and their Many Guises.
Locally Testable Codes and PCPs of Almost-Linear Length.
Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs.
The Hardness of 3 - Uniform Hypergraph Coloring.
Minimizing Congestion in General Networks.
Small Induced-Universal Graphs and Compact Implicit Graph Representations.
Deterministic Broadcasting Time in Radio Networks of Unknown Topology.
Explicit Unique-Neighbor Expanders.
Abstract Combinatorial Programs and Efficient Property Testers.
A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs.
Testing Juntas.
A Spectral Algorithm for Learning Mixtures of Distributions.
Equivalence between Priority Queues and Sorting.
Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space.
Implicit B-Trees: New Results for the Dictionary Problem.
An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree.
PAC = PAExact and Other Equivalent Models in Learning.
Learning Intersections and Thresholds of Halfspaces.
On-Line Confidence Machines Are Well-Calibrated.
Learning a Hidden Matching.
An Information Statistics Approach to Data Stream and Communication Complexity.
Static Optimality Theorem for External Memory String Access.
A Simple Algorithmic Characterization of Uniform Solvability.
Correlation Clustering.
Decoding Turbo-Like Codes via Linear Programming.
Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval.
LT Codes.
Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers.
Scheduling Over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data.
On-Line End-to-End Congestion Control.
Proving Integrality Gaps without Knowing the Linear Program.
Dependent Rounding in Bipartite Graphs.
A Constant-Factor Approximation Algorithm for the Multicommodity.
Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model.
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions.
Concurrent Zero Knowledge with Logarithmic Round-Complexity.
On the (non)Universality of the One-Time Pad.
Market Equilibrium via a Primal-Dual-Type Algorithm.
On the Hardness of Optimal Auctions.
Auctions with Severely Bounded Communication.
Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions.
Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States.
Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes.
Authentication of Quantum Messages.
imits on the Power of Quantum Statistical Zero-Knowledge.
Protocols and Impossibility Results for Gossip-Based Communication Mechanisms.
Covering Problems with Hard Capacities.
Packing 2-Dimensional Bins in Harmony.
Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems.
Quantum Lower Bounds for the Collision and the Element Distinctness Problems.
Quantum Computation and Lattice Problems.
On the Decidability of Self-Assembly of Infinite Ribbons.
The Parameterized Complexity of Counting Problems.
Dimension Reduction in the \ell _1 Norm.
On Approximating the Radii of Point Sets in High Dimensions.
Low-Dimensional Linear Programming with Violations.
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
Satisfiability, Branch-Width and Tseitin Tautologies.
A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution.
Dynamic Planar Convex Hull.
Optimal System of Loops on an Orientable Surface.
The Partition Technique for Overlays of Envelopes.
A Dichotomy Theorem for Constraints on a Three-Element Set.
Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps.
Power from Random Strings.
Improved Dynamic Reachability Algorithms for Directed Graphs.
Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks.
Global Information from Local Observation.
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows.
Spectral Gap and log-Sobolev Constant for Balanced Matroids.
Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties.
Graph Isomorphism is in SPP.
Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection.
Forbidden Information.
The 3-XORSAT Threshold.
The Asymptotic Order of the Random k -SAT Threshold.
On Random Symmetric Travelling Salesman Problems.
Load Balancing with Memory.
Erratum to "Vickrey Pricing and Shortest Paths: What is an Edge Worth?".
Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction.
Algorithmic Applications of Low-Distortion Geometric Embeddings.
Coding Theory: Tutorial and Survey.
Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions.
Approximate Shape Fitting via Linearization.
On the Complexity of Many Faces in Arrangements of Circles.
Clustering Motion.
A Replacement for Voronoi Diagrams of Near Linear Size.
How to Go Beyond the Black-Box Simulation Barrier.
Resettably-Sound Zero-Knowledge and its Applications.
On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates.
Universally Composable Security: A New Paradigm for Cryptographic Protocols.
Traveling with a Pez Dispenser (Or, Routing Issues in MPLS).
Simple Routing Strategies for Adversarial Systems.
Source Routing and Scheduling in Packet Networks.
The Natural Work-Stealing Algorithm is Stable.
Lower Bounds for Polynomial Calculus: Non-Binomial Case.
Counting Axioms Do Not Polynomially Simulate Counting Gates.
Resolution is Not Automatizable Unless W[P] is Tractable.
"Planar" Tautologies Hard for Resolution.
Planar Graphs, Negative Weight Edges, Shortest Paths, Near Linear Time.
Compact Oracles for Reachability and Approximate Distances in Planar Digraphs.
Vickrey Prices and Shortest Paths: What is an Edge Worth?.
Fully Dynamic All Pairs Shortest Paths with Real Edge Weights.
Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity.
How Powerful is Adiabatic Quantum Computation?.
Lower Bounds for Quantum Communication Complexity.
The Confluence of Ground Term Rewrite Systems is Decidable in Polynomial Time.
On the Average-Case Hardness of CVP.
Approximating Directed Multicuts.
Facility Location with Nonuniform Hard Capacities.
An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem.
Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems.
Lower Bounds for Matrix Product.
Deterministic Computation of the Frobenius Form.
The Complexity of Factors of Multivariate Polynomials.
Linear-time Recognition of Circular-arc Graphs.
A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems.
Designing Networks Incrementally.
Sorting and Selection with Structured Costs.
Online Facility Location.
Testing Subgraphs in Large Graphs.
Testing Random Variables for Independence and Identity.
Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication.
Three Theorems Regarding Testing Graph Properties.
Designing Networks for Selfish Users is Hard.
Truthful Mechanisms for One-Parameter Agents.
Building Low-Diameter P2P Networks.
Web Search via Hub Synthesis.
Random Evolution in Massive Graphs.
Tight Approximation Results for General Covering Integer Programs.
Spectral Partitioning of Random Graphs.
Sequential and Parallel Algorithms for Mixed Packing and Covering.
Unique Sink Orientations of Cubes.
Arc-Disjoint Paths in Expander Digraphs.
Glauber Dynamics on Trees and Hyperbolic Graphs.
Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree.
Distributions on Level-Sets with Applications to Approximation Algorithms.
Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring.
Query Efficient PCPs with Perfect Completeness.
Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications.
Extractors from Reed-Muller Codes.
Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator.
Expander-Based Constructions of Efficiently Decodable Codes.
Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors.
Universality and Tolerance.
Extracting Randomness via Repeated Condensing.
Extracting Randomness from Samplable Distributions.
Pseudorandom Generators in Propositional Proof Complexity.
Random graph models for the web graph.
Optimization Problems in Congestion Control.
Fairness Measures for Resource Allocation.
On the Approximability of Trade-offs and Optimal Access of Web Sources.
How Bad is Selfish Routing?
A polylogarithmic approximation of the minimum bisection.
Approximability and in-approximability results for no-wait shop scheduling.
Nested Graph Dissection and Approximation Algorithms.
Approximating the single source unsplittable min-cost flow problem.
Hardness of Approximate Hypergraph Coloring.
"Soft-decision" Decoding of Chinese Remainder Codes.
Super-linear time-space tradeoff lower bounds for randomized computation.
On the Hardness of Graph Isomorphism.
Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation.
New Data Structures for Orthogonal Range Searching.
Nearly Optimal Expected-Case Planar Point Location.
On Levels in Arrangements of Curves.
Detecting a Network Failure.
Testing of Clustering.
Testing of Functions that have small width Branching Programs.
Testing that distributions are close.
Using Upper Confidence Bounds for Online Learning.
Zaps and Their Applications.
Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation.
Lower Bounds on the Efficiency of Generic Cryptographic Constructions.
Concurrent Oblivious Transfer.
The Relationship between Public Key Encryption and Oblivious Transfer.
The Online Median Problem.
Polynomial Time Approximation Schemes for Geometric k-Clustering.
Clustering Data Streams.
On Clusterings - Good, Bad and Spectral.
Opportunistic Data Structures with Applications.
Cache-Oblivious B-Trees.
Using Expander Graphs to Find Vertex Connectivity.
On the boundary complexity of the union of fat triangles.
Straighting Polygonal Arcs and Convexifying Polygonal Cycles.
A Combinatorial Approach to Planar Non-colliding Robot Arm Motion Planning.
Topological Persistence and Simplification.
The Cover Time, the Blanket Time, and the Matthews Bound.
The product replacement algorithm is polynomial.
Efficient Algorithms for Universal Portfolios.
Sampling Adsorbing Staircase Walks Using a New Markov Chain Decomposition Method.
The Randomness Recycler: A New Technique for Perfect Sampling.
An Improved Quantum Fourier Transform Algorithm and Applications.
Fast parallel circuits for the quantum Fourier transform.
Succinct quantum proofs for properties of finite groups.
Private Quantum Channels.
The Quantum Complexity of Set Membership.
Randomized Rumor Spreading.
Fast Broadcasting and Gossiping in Radio Networks.
Linear Waste of Best Fit Bin Packing on Skewed Distributions.
Optimal myopic algorithms for random 3-SAT.
Hierarchical Placement and Network Design Problems.
Building Steiner Trees with Incomplete Global Knowledge.
Cost-Distance: Two Metric Network Design.
Combinatorial feature selection problems.
The Common Fragment of CTL and LTL.
On the Existence of Booster Types.
Existential Second-Order Logic over Graphs: Charting the Tractability Frontier.
Computing the Determinant and Smith Form of an Integer Matrix.
Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems.
Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields.
Approximating Fractional Multicommodity Flow Independent of the Number of Commodities.
Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates.
A 5/2 n<sup>2</sup>-Lower Bound for the Rank of n&#215;n Matrix Multiplication over Arbitrary Fields.
Improved Bounds for Sampling Colorings.
A Non-linear Time Lower Bound for Boolean Branching Programs.
Derandomizing Arthur-Merlin Games Using Hitting Sets.
Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs.
Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time.
Taking a Walk in a Planar Arrangement.
PSPACE Has Constant-Round Quantum Interactive Proof Systems.
Verifiable Random Functions.
How Asymmetry Helps Load Balancing.
Noncryptographic Selection Protocols.
A Sublinear Time Approximation Scheme for Clustering in Metric Spaces.
Efficient Regular Data Structures and Algorithms for Location and Proximity Problems.
Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings.
Near-Optimal Conversion of Hardness into Pseudo-Randomness.
Error Reduction for Extractors.
Primality and Identity Testing via Chinese Remaindering.
On Counting Independent Sets in Sparse Graphs.
Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics.
Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions.
Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain.
A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction.
ong-lived Adaptive Collect with Applications.
A Theoretical Framework for Memory-Adaptive Algorithms.
Cache-Oblivious Algorithms.
The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals.
Setting Parameters by Example.
Finding Double Euler Trails of Planar Graphs in Linear Time.
Edge-Disjoint Routing in Plane Switch Graphs in Linear Time.
On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes.
A Better Lower Bound for Quantum Algorithms Searching an Ordered List.
Bounds for Small-Error and Zero-Error Quantum Algorithms.
Optimal Lower Bounds for Quantum Automata and Random Access Codes.
Improved Combinatorial Algorithms for the Facility Location and k-Median Problems.
Lov&aacute;sz's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications.
Cuts, Trees and l<sub>1</sub>-Embeddings of Graphs.
A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems.
Random CNF's are Hard for the Polynomial Calculus.
A Study of Proof Search Algorithms for Resolution and Polynomial Calculus.
Online Scheduling to Minimize Average Stretch.
Weak Adversaries for the k-Server Problem.
Finely-Competitive Paging.
On the Complexity of SAT.
Hardness of Approximating Sigma<sub>2</sub><sup>p</sup> Minimization Problems.
Hardness of Approximating the Minimum Distance of a Linear Code.
On Universal and Fault-Tolerant Quantum Computing: A Novel Basis and a New Constructive Proof of Universality for Shor's Basis.
Satisfiability of Word Equations with Constants is in PSPACE.
An Approximate L<sup>1</sup>-Difference Algorithm for Massive Data Streams.
Algorithmic Aspects of Protein Structure Similarity.
Magic Functions.
Limits on the Efficiency of One-Way Permutation-Based Hash Functions.
Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security.
Non-Interactive CryptoComputing For NC<sup>1</sup>.
Fairness in Routing and Load Balancing.
Stochastic Load Balancing and Related Problems.
Reducing Network Congestion and Blocking Probability Through Balanced Allocation.
Finding Maximal Repetitions in a Word in Linear Time.
All Pairs Shortest Paths in Undirected Graphs with Integer Weights.
An Algorithmic Theory of Learning: Robust Concepts and Random Projection.
Boosting and Hard-Core Sets.
Learning Mixtures of Gaussians.
Regular Languages Are Testable with a Constant Number of Queries.
Efficient Testing of Large Graphs.
Geometric Computation and the Art of Sampling.
Theoretical Issues in Probabilistic Artificial Intelligence.
Information Retrieval on the Web.
A Tight Characterization of NP with 3 Query PCPs.
Probabilistically Checkable Proofs with Low Amortized Query Complexity.
Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes.
The Access Network Design Problem.
Jitter Control in QoS Networks.
Stability of Adversarial Queues via Fluid Models.
Delayed Information and Action in On-line Algorithms.
The Complexity of the Approximation of the Bandwidth Problem.
The Shortest Vector in a Lattice is Hard to Approximate to Within Some Constant.
Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard.
Satisfiability of Word Equations with Constants is in Exponential Space.
Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree.
A Primitive Recursive Algorithm for the General Petri Net Reachability Problem.
Algorithms to Tile the Infinite Grid with Finite Clusters.
On Approximate Nearest Neighbors in Non-Euclidean Spaces.
Pattern Matching for Spatial Point Sets.
Faster Algorithms for String Matching Problems: Matching the Convolution Bound.
Overcoming the Memory Bottleneck in Suffix Tree Construction.
Bivariate Polynomial Multiplication.
A Unified Superfast Algorithm for Boundary Rational Tangential Interpolation Problems and for Inversion and Factorization of Dense Structured Matrices.
Unsatisfiable Systems of Equations, Over a Finite Field.
Multiplicative Complexity of Taylor Shifts and a New Twist of the Substitution Method.
Local Search in Smooth Convex Sets.
A TDI System and its Application to Approximation Algorithms.
Geometric Separator Theorems &amp; Applications.
Approximation of Diameters: Randomization Doesn't Help.
Time-Space Tradeoffs for Branching Programs.
Optimal Time-Space Trade-Offs for Sorting.
Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields.
Lower Bounds for (MOD p - MOD m) Circuits.
On the Single-Source Unsplittable Flow Problem.
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems.
All Pairs Shortest Paths in Weighted Directed Graphs &#190; Exact and Almost Exact Algorithms.
A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane.
1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations.
The Quantum Communication Complexity of Sampling.
Quantum Lower Bounds by Polynomials.
Quantum Oracle Interrogation: Getting All Information for Almost Half the Price.
Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations.
Approximating a Finite Metric by a Small Number of Tree Metrics.
Random Projection: A New Approach to VLSI Layout.
Map Graphs in Polynomial Time.
On Learning Monotone Boolean Functions.
Orchestrating Quartets: Approximation and Data Correction.
Testing Monotonicity.
Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model.
Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem.
The Finite Capacity Dial-A-Ride Problem.
A Randomized Approximation Scheme for Metric MAX-CUT.
Semidefinite Relaxations for Parallel Machine Scheduling.
Lower Bounds for Zero Knowledge on the Internet.
Oblivious Transfer with a Memory-Bounded Receiver.
Quantum Cryptography with Imperfect Apparatus.
The Security of Individual RSA Bits.
Protocols for Asymmetric Communication Channels.
Marked Ancestor Problems.
Towards an Optimal Bit-Reversal Permutation Program.
The Minimum Equivalent DNF Problem and Shortest Implicants.
Concurrent Reachability Games.
Perfect Information Leader Election in log*<i>n</i> + <i>O</i>(1) Rounds.
Sampling, Halfspace Range Reporting, and Construction of (&lt;= k)-Levels in Three Dimensions.
Parametric and Kinetic Minimum Spanning Trees.
On the Combinatorial and Topological Complexity of a Single Cell.
Which Crossing Number is it, Anyway?
An Improved Exponential-Time Algorithm for <i>k</i>-SAT.
Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems.
Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs.
Which Problems Have Strongly Exponential Complexity?
Recommendation Systems: A Probabilistic Analysis.
Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs.
Improved Bounds and Algorithms for Hypergraph Two-Coloring.
Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes.
The Complexity of Acyclic Conjunctive Queries.
A Characterization of NC by Tree Recurrence.
A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time.
Randomness vs. Time: De-Randomization under a Uniform Assumption.
Beyond the Flow Decomposition Barrier.
Undirected Single Source Shortest Path in Linear Time.
A Faster Deterministic Algorithm for Minimum Spanning Trees.
Flows in Undirected Unit Capacity Networks.
Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties.
Deciding Properties of Polynomials Without Factoring.
An Improved Algorithm for Quantifier Elimination Over Real Closed Fields.
On the Power of Quantum Finite State Automata.
Two Decades of Temporal Logic: Achievements and Challenges (Abstract).
Computable Obstructions to Wait-free Computability.
Reliable Cellular Automata with Self-Organization.
Alternating-time Temporal Logic.
On the Complexity of a Set-Union Problem.
Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs.
Deterministic Superimposed Coding with Applications to Pattern Matching.
Optimal Suffix Tree Construction with Large Alphabets.
Pattern Matching with Swaps.
Improved Bounds on Planar k-sets and k-levels.
Computing Integral Points in Convex Semi-algebraic Sets.
The Computational Complexity of Knot and Link Problems.
Approximating Shortest Paths on an Nonconvex Polyhedron.
Randomized Allocation Processes.
The Analysis of a List-Coloring Algorithm on a Random Graph.
Contention Resolution with Guaranteed Constant Expected Delay.
Path Coupling: A Technique for Proving Rapid Mixing in Markov Chains.
Separation of the Monotone NC Hierarchy.
Making Nondeterminism Unambiguous.
No Feasible Interpolation for TC0-Frege Proofs.
Weak Random Sources, Hitting Sets, and BPP Simulations.
Parallelizing Elimination Orders with Linear Fill.
Exploiting Locality for Data Management in Systems of Limited Bandwidth.
General Dynamic Routing with Per-Packet Delay Guarantees of O(distance + 1 / session rate).
Global Optimization Using Local Information with Applications to Flow Control.
New Directions in Cryptography: Twenty Some Years Later.
Truly Online Paging with Locality of Reference.
The Competitive Analysis of Risk Taking with Applications to Online Trading.
Minimizing Flow Time Nonclairvoyantly.
Storage Management for Evolving Databases.
Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval.
Does Parallel Repetition Lower the Error in Computationally Sound Protocols?
Optimal Resilience Proactive Public-Key Cryptosystems.
A Concrete Security Treatment of Symmetric Encryption.
A 7/8-Approximation Algorithm for MAX 3SAT?
Improved Approximations for Edge-Disjoint Paths, Unsplittable Flow, and Related Routing Problems.
Improved Approximation Algorithms for Unsplittable Flow Problems.
Lower Bounds for the Signature Size of Incremental Schemes.
A Complete Promise Problem for Statistical Zero-Knowledge.
Number-theoretic Constructions of Efficient Pseudo-random Functions.
An Improved Worst-Case to Average-Case Connection for Lattice Problems.
Finding an Even Hole in a Graph.
Edge-Connectivity Augmentation Preserving Simplicity.
Hamiltonian Cycles in Solid Grid Graphs.
A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces.
Learning Noisy Perceptrons by a Perceptron in Polynomial Time.
Nearly Tight Bounds on the Learnability of Evolution.
Improved Approximations for Shallow-Light Spanning Trees.
Buy-at-Bulk Network Design.
A 2-Approximation Algorithm for the Directed Multiway Cut Problem.
Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems.
Satisfiability Coding Lemma.
The Minimization Problem for Boolean Formulas.
Tight Bounds for Depth-two Superconcentrators.
Constant Depth Circuits and the Lutz Hypothesis.