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