default search action
36th STOC 2004: Chicago, IL, USA
- László Babai:
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004. ACM 2004, ISBN 1-58113-852-0
Session 1A
- Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha
, Madhu Sudan, Salil P. Vadhan:
Robust pcps of proximity, shorter pcps and applications to coding. 1-10 - Jonas Holmerin, Subhash Khot:
A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. 11-20 - Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor:
Asymmetric k-center is log* n-hard to approximate. 21-27 - Julia Chuzhoy, Joseph Naor:
New hardness results for congestion minimization and machine scheduling. 28-34 - Susanne Albers, Markus Schmidt:
On the performance of greedy algorithms in packet buffering. 35-44
Session 1B
- Baruch Awerbuch, Robert D. Kleinberg:
Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. 45-53 - Gurmeet Singh Manku, Moni Naor, Udi Wieder:
Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks. 54-63 - Yossi Azar, Yossi Richter:
The zero-one principle for switching networks. 64-71
Session 2A
- Noga Alon, Assaf Naor:
Approximating the cut-norm via Grothendieck's inequality. 72-80 - Daniel A. Spielman, Shang-Hua Teng:
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. 81-90
Session 2B
- Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein:
Dictionary matching and indexing with errors and don't cares. 91-100 - Irene Finocchi, Giuseppe F. Italiano:
Sorting and searching in the presence of memory faults (without redundancy). 101-110 - Andris Ambainis:
Quantum algorithms a decade after shor. 111
Session 4A
- Andrew Chi-Chih Yao:
Graph entropy and quantum sorting problems. 112-117 - Scott Aaronson:
Multilinear formulas and skepticism of quantum computing. 118-127 - Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis:
Exponential separation of quantum and classical one-way communication complexity. 128-137
Session 4B
- Guy Kortsarz, Zeev Nutov:
Approximation algorithm for k-node connected subgraphs via critical graphs. 138-145 - Daniel Bienstock, Garud Iyengar:
Solving fractional packing problems in Oast(1/?) iterations. 146-155 - Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd:
The all-or-nothing multicommodity flow problem. 156-165
Session 5A
- Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson:
Approximation algorithms for deadline-TSP and vehicle routing with time-windows. 166-174 - Artur Czumaj, Christian Sohler
Estimating the weight of metric minimum spanning trees in sublinear-time. 175-183 - Liam Roditty, Uri Zwick:
A fully dynamic reachability algorithm for directed graphs with an almost linear update time. 184-191
Session 5B
- Alexander Healy, Salil P. Vadhan, Emanuele Viola:
Using nondeterminism to amplify hardness. 192-201 - Rajeev Alur, P. Madhusudan:
Visibly pushdown languages. 202-211 - Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia:
Linear FPT reductions and computational lower bounds. 212-221 - Sanjeev Arora, Satish Rao, Umesh V. Vazirani:
Expander flows, geometric embeddings and graph partitioning. 222-231
Session 7A
- Rafael Pass
Bounded-concurrent secure multi-party computation with a dishonest majority. 232-241 - Manoj Prabhakaran, Amit Sahai:
New notions of security: achieving universal composability without trusted setup. 242-251 - Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen:
Completeness in two-party secure computation: a computational view. 252-261 - Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai:
Batch codes and their applications. 262-271
Session 7B
- Claire Kenyon, Yuval Rabani
Low distortion maps between point sets. 272-280 - Kunal Talwar:
Bypassing the embedding: algorithms for low dimensional metrics. 281-290 - Sariel Har-Peled
On coresets for k-means and k-median clustering. 291-300 - Jean-Daniel Boissonnat, David Cohen-Steiner, Gert Vegter:
Isotopic implicit surface meshing. 301-309
Session 8A
- László Lovász, Santosh S. Vempala:
Hit-and-run from a corner. 310-314 - John Dunagan, Santosh S. Vempala:
A simple polynomial-time rescaling algorithm for solving linear programs. 315-320
Session 8B
- Bogdan S. Chlebus, Dariusz R. Kowalski, Alexander A. Shvartsman:
Collective asynchronous reading with polylogarithmic worst-case overhead. 321-330 - Michael Elkin:
Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. 331-340 - Éva Tardos:
Network games. 341-342
Session 10A
- René Beier, Berthold Vöcking:
Typical properties of winners and losers in discrete optimization. 343-352 - Retsef Levi, Robin Roundy, David B. Shmoys
Primal-dual algorithms for deterministic inventory problems. 353-362 - Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar
Multi-processor scheduling to minimize flow time with epsilon resource augmentation. 363-372
Session 10B
- Piotr Indyk:
Algorithms for dynamic geometric problems over data streams. 373-380 - Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld:
Sublinear algorithms for testing monotone and unimodal distributions. 381-390 - Eldar Fischer:
The difficulty of testing for isomorphism against a graph that is given in advance. 391-397
Session 11A
- José R. Correa, Michel X. Goemans:
An approximate König's theorem for edge-coloring weighted bipartite graphs. 398-406 - Harold N. Gabow:
Finding paths and cycles of superpolylogarithmic length. 407-416 - Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha:
Boosted sampling: approximation algorithms for stochastic optimization. 417-426
Session 11B
- Amir Shpilka
Derandomizing homomorphism testing in general groups. 427-435 - Venkatesan Guruswami:
Better extractors for better codes? 436-444 - Eyal Rozenman, Aner Shalev, Avi Wigderson:
A new family of Cayley expanders (?). 445-454 - Jonathan A. Kelner:
Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. 455-464 - Scott Aaronson:
Lower bounds for local search by quantum arguments. 465-474 - Peter Bürgisser, Felipe Cucker:
Counting complexity classes for numeric computations II: algebraic and semialgebraic sets. 475-485
Session 14A
- Miklós Ajtai:
A conjecture about polynomial time computable lattice-lattice functions. 486-493 - Miklos Santha, Mario Szegedy:
Quantum and classical query complexities of local search are polynomially related. 494-501 - Ben Reichardt:
The quantum adiabatic optimization algorithm and local minima. 502-510 - Rahul Garg, Sanjiv Kapoor:
Auction algorithms for market equilibrium. 511-518
Session 14B
- Nikhil R. Devanur:
The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results. 519-528 - Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta:
(Almost) tight bounds and existence theorems for confluent flows. 529-538 - Kenji Obata:
Approximate max-integral-flow/min-multicut theorems. 539-545
Session 15A
- Mihai Patrascu, Erik D. Demaine:
Lower bounds for dynamic connectivity. 546-553 - Nir Ailon, Bernard Chazelle:
Lower bounds for linear degeneracy testing. 554-560
Session 15B
- David Kempe, Frank McSherry:
A decentralized algorithm for spectral analysis. 561-568 - Jon M. Kleinberg, Mark Sandler:
Using mixture models for collaborative filtering. 569-578 - Avi Wigderson:
Depth through breadth, or why should we attend talks in other areas? 579
Session 17A
- Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari:
Sharp thresholds For monotone properties in random geometric graphs. 580-586 - Dimitris Achlioptas, Assaf Naor:
The two possible values of the chromatic number of a random graph. 587-593 - Uriel Feige:
On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. 594-603 - Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar:
The complexity of pure Nash equilibria. 604-612
Session 17B
- Martin Gairing, Thomas Lücking, Marios Mavronicolas
Computing Nash equilibria for scheduling on restricted parallel links. 613-622 - Joseph Y. Halpern, Vanessa Teague:
Rational secret sharing and multiparty computation: extended abstract. 623-632 - Ran Raz
Multi-linear formulas for permanent and determinant are of super-polynomial size. 633-641
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-01 00:16 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: