8 Quantum Weak Coin-Flipping with Bias of 0.192.
20 Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs.
76 Quantum Walk Algorithm for Element Distinctness.
18 Quantum Speed-Up of Markov Chain Based Algorithms.
65 Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation.
28 Maximizing Quadratic Programs: Extending Grothendieck's Inequality.
14 An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem.
11 Edge-Disjoint Paths in Planar Graphs.
4 Machine Minimization for Scheduling Jobs with Interval Constraints.
9 Random Edge Can Be Exponential on Abstract Cubes.
3 On the Integrality Ratio for Asymmetric TSP.
5 The Hardness of Metric Labeling.
19 Hardness of Buy-at-Bulk Network Design.
29 Hardness of Approximating the Shortest Vector Problem in Lattices.
26 Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique.
44 Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
13 Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem.
19 Cryptography in NC<sup>0</sup>.
12 An Unconditional Study of Computational Zero Knowledge.
17 Universally Composable Protocols with Relaxed Set-Up Assumptions.
8 On the (Im)possibility of Cryptography with Imperfect Randomness.
26 Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity.
16 An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design.
32 Stochastic Optimization is (Almost) as easy as Deterministic Optimization.
1 0(sqrt (log n)) Approximation to SPARSEST CUT in &Otilde;(n<sup>2</sup>) Time.
19 Maximum Matchings via Gaussian Elimination.
41 Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game.
15 Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users.
16 Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games.
36 A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities.
42 The Price of Stability for Network Design with Fair Cost Allocation.
15 Holographic Algorithms .
16 Hierarchy Theorems for Probabilistic Polynomial Time.
14 Private Codes or Succinct Random Codes That Are (Almost) Perfect.
7 On the List and Bounded Distance Decodibility of the Reed-Solomon Codes .
7 Multilinear-NC neq Multilinear-NC.
1 Algebras with Polynomial Identities and Computing the Determinant.
20 Lattice Problems in NP cap coNP.
21 Worst-Case to Average-Case Reductions Based on Gaussian Measures.
19 Extracting Randomness Using Few Independent Sources.
14 Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed.
5 Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap.
8 Testing Polynomials over General Fields.
5 Testing Low-Degree Polynomials over Prime Fields.
46 Measured Descent: A New Embedding Method for Finite Metrics.
34 Triangulation and Embedding Using Small Sets of Beacons.
30 A Simple Linear Time (1+ ) -Approximation Algorithm for k-Means Clustering in Any Dimensions.
1 On the Power of Discrete and of Lexicographic Helly-Type Theorems.
16 An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching.
11 Dynamic Optimality -- Almost.
3 No Sorting? Better Searching!
6 Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs.
13 Dynamic Transitive Closure via Dynamic Matrix Inverse .
23 Dynamic Speed Scaling to Manage Energy and Temperature.
10 Optimal Power-Down Strategies.
20 On the Streaming Model Augmented with a Sorting Primitive.
11 Approximating Edit Distance Efficiently.
16 Strong Spatial Mixing for Lattice Graphs with Fewer Colours.
5 Shuffling by Semi-Random Transpositions.
20 Randomly Coloring Constant Degree Graphs.
0 The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem.
4 Spectral Analysis of Random Graphs with Skewed Degree Distributions.
0 Learning with Errors in Answers to Membership Queries.
10 Learnability and Automatizability.