22 Recognizing string graphs in NP.
7 Dynamic subgraph connectivity with geometric applications.
50 New results on monotone dualization and generating hypergraph transversals.
31 Combinatorial optimization problems in self-assembly.
95 The importance of being biased.
7 On the advantage over a random assignment.
10 The complexity of choosing an H-colouring (nearly) uniformly at random.
8 Random sampling in residual graphs.
106 On the complexity of equilibria.
80 Competitive generalized auctions.
29 Competitive recommendation systems.
0 The Glauber dynamics on colourings of a graph with high girth and maximum degree.
8 Clairvoyant scheduling of random walks.
28 Solving convex programs by random walks.
3 The Joy of Theory.
18 Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths.
5 Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines.
18 On randomized online scheduling.
19 On the complexity of matrix product.
40 Near-optimal sparse fourier representations via sampling.
3 Fitting algebraic curves to noisy data.
18 A new average case analysis for completion time scheduling.
12 A unified analysis of hot video schedulers.
40 Optimal rate-based scheduling on multiprocessors.
28 Almost all graphs with average degree 4 are 3-colorable.
15 Models and thresholds for random constraint satisfaction problems.
0 Reimer's inequality and tardos' conjecture.
11 Clifford algebras and approximating the permanent.
40 Random sampling and approximation of MAX-CSP problems.
11 A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant.
81 Approximate clustering via core-sets.
7 On paging with locality of reference.
47 Cache-oblivious priority queue and graph algorithm applications.
8 Average case analysis for batched disk scheduling and increasing subsequences.
64 Selfish traffic allocation for server farms.
33 Approximation schemes for preemptive weighted flow time.
46 Approximation algorithms for minimum-cost k-vertex connected subgraphs.
28 Equitable cost allocations via primal-dual-type algorithms.
13 2-round zero knowledge and proof auditors.
24 Concurrent zero-knowledge with timing, revisited.
16 Tight security proofs for the bounded-storage model.
36 Hardness results for approximate hypergraph coloring.
30 Space lower bounds for distance approximation in the data stream model.
24 Approximate counting of inversions in a data stream.
60 Similarity estimation techniques from rounding algorithms.
122 Fast, small-space algorithms for approximate histogram maintenance.
19 Stability of load balancing algorithms in dynamic adversarial systems.
60 Tradeoffs in probabilistic packet marking for IP traceback.
17 Crawling on web graphs.
117 The price of anarchy is independent of the network topology.
15 Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem.
10 An exponential separation between regular and general resolution.
11 Size space tradeoffs for resolution.
8 Exact learning of DNF formulas using DNF hypotheses.
35 Monotonicity testing over general poset domains.
33 Strict polynomial-time in simulation and extraction.
94 Universally composable two-party and multi-party secure computation.
5 The invasiveness of off-line memory checking.
28 On the composition of authenticated byzantine agreement.
27 Wait-free consensus with infinite arrivals.
81 Relations between average case complexity and approximation complexity.
0 Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon.
44 Resolution lower bounds for the weak pigeonhole principle.
14 Hard examples for bounded depth frege.
11 Meldable heaps and boolean union-find.
14 Optimal finger search trees in the pointer machine.
18 Verifying candidate matches in sparse and wildcard matching.
24 Deterministic sorting in O(nlog log n) time and linear space.
15 Improved cryptographic hash functions with worst-case/average-case connection.
17 Algorithmic derandomization via complexity theory.
38 Pseudo-random generators for all hardnesses.
67 Quantum lower bound for the collision problem.
20 Secure multi-party quantum computation.
78 Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem.
32 Randomness conductors and constant-degree lossless expanders.
10 Expanders from symmetric codes.
9 The complexity of approximating entropy.
26 Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems.
12 On communication over an entanglement-assisted quantum channel.
17 Girth and euclidean distortion.
0 Computing the betti numbers of arrangements.
15 Space-efficient approximate Voronoi diagrams.
95 A new greedy approach for facility location problems.
117 Finding nearest neighbors in growth-restricted metrics.
9 Hardness amplification within NP.
0 3-manifold knot genus is NP-complet.
74 On the power of unique 2-prover 1-round games.
0 Learnability beyond AC0.
12 Huffman coding with unequal letter costs.
26 Approximating the smallest grammar: Kolmogorov complexity in natural models.
8 Limits to list decodability of linear codes.
33 Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets.