Document Search Results

The two possible values of the chromatic number of a random graph. (English) Zbl 1192.05140

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 587-593, electronic only (2004).

MSC: 05C80 05C15

Cite Review PDF

Full Text: DOI arXiv

Goel, Ashish; Rai, Sanatan; Krishnamachari, Bhaskar

Sharp thresholds for monotone properties in random geometric graphs. (English) Zbl 1192.05145

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 580-586, electronic only (2004).

MSC: 05C80

Cite Review PDF

Full Text: DOI arXiv

Obata, Kenji

Approximate max-integral-flow/min-multicut theorems. (English) Zbl 1192.90236

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 539-545, electronic only (2004).

MSC: 90C35 05C85

Cite Review PDF

Full Text: DOI

Chen, Jiangzhuo; Kleinberg, Robert D.; Lovász, László; Rajaraman, Rajmohan; Sundaram, Ravi; Vetta, Adrian

({A}lmost) tight bounds and existence theorems for confluent flows. (English) Zbl 1192.90022

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 529-538, electronic only (2004).

MSC: 90B10 05C85 68M10 68R10

Cite Review PDF

Full Text: DOI

Devanur, Nikhil R.

The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results. (English) Zbl 1192.91101

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 519-528, electronic only (2004).

MSC: 91B26 90C47

Cite Review PDF

Full Text: DOI

Garg, Rahul; Kapoor, Sanjiv

Auction algorithms for market equilibrium. (English) Zbl 1192.91011

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 511-518, electronic only (2004).

MSC: 91-04 90C05 91B26

Cite Review PDF

Full Text: DOI

Reichardt, Ben W.

The quantum adiabatic optimization algorithm and local minima. (English) Zbl 1192.81098

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 502-510, electronic only (2004).

MSC: 81P68 68Q05

Cite Review PDF

Full Text: DOI

Kelner, Jonathan A.

Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. (English) Zbl 1192.05162

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 455-464, electronic only (2004).

MSC: 05C85 05C10 05C40 05C50 68R10 68W40 68Q25 68W05

Cite Review PDF

Full Text: DOI Link

Gabow, Harold N.

Finding paths and cycles of superpolylogarithmic length. (English) Zbl 1192.68361

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 407-416, electronic only (2004).

MSC: 68Q25 05C38

Cite Review PDF

Full Text: DOI

Correa, José R.; Goemans, Michel X.

An approximate König’s theorem for edge-coloring weighted bipartite graphs. (English) Zbl 1192.05046

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 398-406, electronic only (2004).

MSC: 05C15 05B40 05C85 68R10

Cite Review PDF

Full Text: DOI

Levi, Retsef; Roundy, Robin; Shmoys, David B.

Primal-dual algorithms for deterministic inventory problems. (English) Zbl 1192.90010

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 353-362, electronic only (2004).

MSC: 90B05 90-04

Cite Review PDF

Full Text: DOI Link

Beier, Rene; Vöcking, Berthold

Typical properties of winners and losers in discrete optimization. (English) Zbl 1192.90156

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 343-352, electronic only (2004).

MSC: 90C27 90C10 68W40 90C60

Cite Review PDF

Full Text: DOI

Dunagan, John; Vempala, Santosh

A simple polynomial-time rescaling algorithm for solving linear programs. (English) Zbl 1192.90116

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 315-320, electronic only (2004).

MSC: 90C05 90C60 90-04

Cite Review PDF

Full Text: DOI

Harnik, Danny; Naor, Moni; Reingold, Omer; Rosen, Alon

Completeness in two-party secure computation: a computational view. (English) Zbl 1192.94120

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 252-261, electronic only (2004).

MSC: 94A62 68P25

Cite Review PDF

Full Text: DOI

Prabhakaran, Manoj; Sahai, Amit

New notions of security: achieving universal composability without trusted setup. (English) Zbl 1192.94124

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 242-251, electronic only (2004).

MSC: 94A62 68M12 68P25

Cite Review PDF

Full Text: DOI

Aaronson, Scott

Multilinear formulas and skepticism of quantum computing. (English) Zbl 1192.81045

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 118-127, electronic only (2004).

MSC: 81P68 81P05

Cite Review PDF

Full Text: DOI

Yao, Andrew Chi-Chih

Graph entropy and quantum sorting problems. (English) Zbl 1192.81109

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 112-117, electronic only (2004).

MSC: 81P68 68P10 68Q05 68Q25

Cite Review PDF

Full Text: DOI

Raz, Ran

Multi-linear formulas for permanent and determinant are of super-polynomial size. (English) Zbl 1192.68328

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 633-641, electronic only (2004).

MSC: 68Q17 15A15

Cite Review PDF

Full Text: DOI

Wigderson, Avi

Depth through breadth, or why should we attend talks in other areas? (English) Zbl 1192.68254

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 579, electronic only (2004).

MSC: 68Q01

Cite Review PDF

Full Text: DOI

Kleinberg, Jon; Sandler, Mark

Using mixture models for collaborative filtering. (English) Zbl 1192.68685

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 569-578, electronic only (2004).

MSC: 68T37 68P20 68U35

Cite Review PDF

Full Text: DOI

Kempe, David; McSherry, Frank

A decentralized algorithm for spectral analysis. (English) Zbl 1192.68848

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 561-568, electronic only (2004).

MSC: 68W15 65F15 90C35 68Q25

Cite Review PDF

Full Text: DOI

Ailon, Nir; Chazelle, Bernard

Lower bounds for linear degeneracy testing. (English) Zbl 1192.68306

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 554-560, electronic only (2004).

MSC: 68Q17 68U05

Cite Review PDF

Full Text: DOI Link

Pǎtraşcu, Mihai; Demaine, Erik D.

Lower bounds for dynamic connectivity. (English) Zbl 1192.68185

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 546-553, electronic only (2004).

MSC: 68P05 68R10

Cite Review PDF

Full Text: DOI

Santha, Miklos; Szegedy, Mario

Quantum and classical query complexities of local search are polynomially related. (English) Zbl 1192.68266

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 494-501, electronic only (2004).

MSC: 68Q05 68Q10 68Q25 81P68

Cite Review PDF

Full Text: DOI

Ajtai, Miklós

A conjecture about polynomial time computable lattice-lattice functions. (English) Zbl 1192.68335

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 486-493, electronic only (2004).

MSC: 68Q25 03E25 06E30

Cite Review PDF

Full Text: DOI

Bürgisser, Peter; Cucker, Felipe

Counting complexity classes for numeric computations. II. Algebraic and semialgebraic sets. (English) Zbl 1192.68289

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 475-485, electronic only (2004).

MSC: 68Q15 65Y20 68Q05

Cite Review PDF

Full Text: DOI

Aaronson, Scott

Lower bounds for local search by quantum arguments. (English) Zbl 1192.68256

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 465-474, electronic only (2004).

MSC: 68Q05 68Q17 81P68

Cite Review PDF

Full Text: DOI arXiv

Rozenman, Eyal; Shalev, Aner; Wigderson, Avi

A new family of Cayley expanders (?). (English) Zbl 1192.68862

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 445-454, electronic only (2004).

MSC: 68W20 68R10

Cite Review PDF

Full Text: DOI

Guruswami, Venkatesan

Better extractors for better codes? (English) Zbl 1192.68363

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 436-444, electronic only (2004).

MSC: 68Q25 68W20 94B35

Cite Review PDF

Full Text: DOI

Shpilka, Amir; Wigderson, Avi

Derandomizing homomorphism testing in general groups. (English) Zbl 1192.68378

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 427-435, electronic only (2004).

MSC: 68Q25 20-04 68Q15 68W20

Cite Review PDF

Full Text: DOI

Gupta, Anupam; Pál, Martin; Ravi, R.; Sinha, Amitabh

Boosted sampling: approximation algorithms for stochastic optimization. (English) Zbl 1192.90171

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 417-426, electronic only (2004).

MSC: 90C27 90C15 68W25

Cite Review PDF

Full Text: DOI

Fischer, Eldar

The difficulty of testing for isomorphism against a graph that is given in advance. (English) Zbl 1192.68857

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 391-397, electronic only (2004).

MSC: 68W20 05C85 05C60

Cite Review PDF

Full Text: DOI

Batu, Tugkan; Kumar, Ravi; Rubinfeld, Ronitt

Sublinear algorithms for testing monotone and unimodal distributions. (English) Zbl 1192.68345

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 381-390, electronic only (2004).

MSC: 68Q25

Cite Review PDF

Full Text: DOI

Indyk, Piotr

Algorithms for dynamic geometric problems over data streams. (English) Zbl 1192.68179

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 373-380, electronic only (2004).

MSC: 68P05 68W25

Cite Review PDF

Full Text: DOI

Chekuri, Chandra; Goel, Ashish; Khanna, Sanjeev; Kumar, Amit

Multi-processor scheduling to minimize flow time with \(\epsilon\) resource augmentation. (English) Zbl 1192.68096

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 363-372, electronic only (2004).

MSC: 68M20 68W40

Cite Review PDF

Full Text: DOI Link

Tardos, Éva

Network games. (English) Zbl 1192.91046

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 341-342, electronic only (2004).

MSC: 91A43 68M10 91A80

Cite Review PDF

Full Text: DOI

Elkin, Michael

Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. (English) Zbl 1192.68319

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 331-340, electronic only (2004).

MSC: 68Q17 68W15

Cite Review PDF

Full Text: DOI

Chlebus, Bogdan S.; Kowalski, Dariusz R.; Shvartsman, Alexander A.

Collective asynchronous reading with polylogarithmic worst-case overhead. (English) Zbl 1192.68079

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 321-330, electronic only (2004).

MSC: 68M14 68M10

Cite Review PDF

Full Text: DOI

Lovász, László; Vempala, Santosh

Hit-and-run from a corner. (English) Zbl 1192.68371

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 310-314, electronic only (2004).

MSC: 68Q25 60G50

Cite Review PDF

Full Text: DOI

Boissonnat, Jean-Daniel; Cohen-Steiner, David; Vegter, Gert

Isotopic implicit surface meshing. (English) Zbl 1192.65016

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 301-309, electronic only (2004).

MSC: 65D17 68U05

Cite Review PDF

Full Text: DOI Link

Har-Peled, Sariel; Mazumdar, Soham

On coresets for \(k\)-means and \(k\)-median clustering. (English) Zbl 1192.68904

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 291-300, electronic only (2004).

MSC: 68W25 68Q25 62P99

Cite Review PDF

Full Text: DOI

Talwar, Kunal

Bypassing the embedding: algorithms for low dimensional metrics. (English) Zbl 1192.68918

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 281-290, electronic only (2004).

MSC: 68W25

Cite Review PDF

Full Text: DOI

Kenyon, Claire; Rabani, Yuval; Sinclair, Alistair

Low distortion maps between point sets. (English) Zbl 1192.68366

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 272-280, electronic only (2004).

MSC: 68Q25 68U05 68U10 68T10

Cite Review PDF

Full Text: DOI

Ishai, Yuval; Kushilevitz, Eyal; Ostrovsky, Rafail; Sahai, Amit

Batch codes and their applications. (English) Zbl 1192.94100

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 262-271, electronic only (2004).

MSC: 94B60 68P30 68R05

Cite Review PDF

Full Text: DOI

Pass, Rafael

Bounded-concurrent secure multi-party computation with a dishonest majority. (English) Zbl 1192.68077

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 232-241, electronic only (2004).

MSC: 68M12 68Q85 68M14

Cite Review PDF

Full Text: DOI

Arora, Sanjeev; Rao, Satish; Vazirani, Umesh

Expander flows, geometric embeddings and graph partitioning. (English) Zbl 1192.68467

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 222-231, electronic only (2004).

MSC: 68R10 05C70 05C85 68W25 90C35

Cite Review PDF

Full Text: DOI

Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge

Linear FPT reductions and computational lower bounds. (English) Zbl 1192.68313

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 212-221, electronic only (2004).

MSC: 68Q17 68Q15 68Q25 68W25

Cite Review PDF

Full Text: DOI

Alur, Rajeev; Madhusudan, P.

Visibly pushdown languages. (English) Zbl 1192.68396

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 202-211, electronic only (2004).

MSC: 68Q42 68Q60 68Q45

Cite Review PDF

Full Text: DOI Link

Healy, Alexander; Vadhan, Salil; Viola, Emanuele

Using nondeterminism to amplify hardness. (English) Zbl 1192.68294

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 192-201, electronic only (2004).

MSC: 68Q15

Cite Review PDF

Full Text: DOI

Roditty, Liam; Zwick, Uri

A fully dynamic reachability algorithm for directed graphs with an almost linear update time. (English) Zbl 1192.90238

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 184-191, electronic only (2004).

MSC: 90C35 05C85 68R10 68W40

Cite Review PDF

Full Text: DOI

Czumaj, Artur; Sohler, Christian

Estimating the weight of metric minimum spanning trees in sublinear-time. (English) Zbl 1192.68888

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 175-183, electronic only (2004).

MSC: 68W25 05C05 68W20

Cite Review PDF

Full Text: DOI Link

Bansal, Nikhil; Blum, Avrim; Chawla, Shuchi; Meyerson, Adam

Approximation algorithms for deadline-TSP and vehicle routing with time-windows. (English) Zbl 1192.90216

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 166-174, electronic only (2004).

MSC: 90C35 90B06 68W25

Cite Review PDF

Full Text: DOI

Chekuri, Chandra; Khanna, Sanjeev; Shepherd, F. Bruce

The all-or-nothing multicommodity flow problem. (English) Zbl 1192.68878

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 156-165, electronic only (2004).

MSC: 68W25 68Q25 90B10

Cite Review PDF

Full Text: DOI Link

Kortsarz, G.; Nutov, Z.

Approximation algorithm for \(k\)-node connected subgraphs via critical graphs. (English) Zbl 1192.90233

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 138-145, electronic only (2004).

MSC: 90C35 68W25 05C85 68R10

Cite Review PDF

Full Text: DOI

Bar-Yossef, Ziv; Jayram, T. S.; Kerenidis, Iordanis

Exponential separation of quantum and classical one-way communication complexity. (English) Zbl 1192.81052

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 128-137, electronic only (2004).

MSC: 81P68 68Qxx 68M12

Cite Review PDF

Full Text: DOI

Finocchi, Irene; Italiano, Giuseppe F.

Sorting and searching in the presence of memory faults (without redundancy). (English) Zbl 1192.68958

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 101-110, electronic only (2004).

MSC: 68W40 68W01 68P10

Cite Review PDF

Full Text: DOI

Cole, Richard; Gottlieb, Lee-Ad; Lewenstein, Moshe

Dictionary matching and indexing with errors and don’t cares. (English) Zbl 1192.68818

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 91-100, electronic only (2004).

MSC: 68W05 68P05 68W40

Cite Review PDF

Full Text: DOI

Azar, Yossi; Richter, Yossi

The zero-one principle for switching networks. (English) Zbl 1192.68021

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 64-71, electronic only (2004).

MSC: 68M10 68W40

Cite Review PDF

Full Text: DOI

Manku, Gurmeet Singh; Naor, Moni; Wieder, Udi

Know thy neighbor’s neighbor: the power of lookahead in randomized P2P networks. (English) Zbl 1192.68048

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 54-63, electronic only (2004).

MSC: 68M10 05C85 68R10

Cite Review PDF

Full Text: DOI

Awerbuch, Baruch; Kleinberg, Robert D.

Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. (English) Zbl 1192.68020

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 45-53, electronic only (2004).

MSC: 68M10 90C35

Cite Review PDF

Full Text: DOI

Albers, Susanne; Schmidt, Markus

On the performance of greedy algorithms in packet buffering. (English) Zbl 1192.68938

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 35-44, electronic only (2004).

MSC: 68W40 68Q10 68W20

Cite Review PDF

Full Text: DOI

Chuzhoy, Julia; Naor, Joseph

New hardness results for congestion minimization and machine scheduling. (English) Zbl 1192.90254

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 28-34, electronic only (2004).

MSC: 90C60 90B35 68Q17 68W25

Cite Review PDF

Full Text: DOI

Chuzhoy, Julia; Guha, Sudipto; Halperin, Eran; Khanna, Sanjeev; Kortsarz, Guy; Naor, Joseph

**Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate.** (English) Zbl 1192.68314

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 21-27, electronic only (2004).

MSC: 68Q17 68W25 90C60 90C35

Cite Review PDF

Full Text: DOI

Holmerin, Jonas; Khot, Subhash

A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. (English) Zbl 1192.68324

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 11-20, electronic only (2004).

MSC: 68Q17 68Q15

Cite Review PDF

Full Text: DOI

Ben-Sasson, Eli; Goldreich, Oded; Harsha, Prahladh; Sudan, Madhu; Vadhan, Salil

Robust PSPs of proximity, shorter PSPs and applications to coding. (English) Zbl 1192.68286

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 1-10, electronic only (2004).

MSC: 68Q15 94A60 94B60 68P30

Cite Review PDF

Full Text: DOI

Halpern, Joseph; Teague, Vanessa

Rational secret sharing and multiparty computation. (English) Zbl 1192.94119

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 623-632, electronic only (2004).

MSC: 94A62 91A80 68M12

Cite Review PDF

Full Text: DOI

Gairing, Martin; Lücking, Thomas; Mavronicolas, Marios; Monien, Burkhard

Computing Nash equilibria for scheduling on restricted parallel links. (English) Zbl 1192.90072

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 613-622, electronic only (2004).

MSC: 90B35 68W25 91A10

Cite Review PDF

Full Text: DOI Link

Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal

The complexity of pure Nash equilibria. (English) Zbl 1192.91042

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 604-612, electronic only (2004).

MSC: 91A43 68Q17 91-04 91A06

Cite Review PDF

Full Text: DOI

Feige, Uriel

On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. (English) Zbl 1192.60021

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 594-603, electronic only (2004).

MSC: 60C05 05C07 68W25

Cite Review PDF

Full Text: DOI

Ambainis, Andris

Quantum algorithms a decade after Shor. (English) Zbl 1192.81049

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 111, electronic only (2004).

MSC: 81P68 68Q05

Cite Review PDF

Full Text: DOI

Spielman, Daniel A.; Teng, Shang-Hua

Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. (English) Zbl 1192.65048

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 81-90, electronic only (2004).

MSC: 65F30 15A06 05C85 05C70 68R10

Cite Review PDF

Full Text: DOI arXiv

Alon, Noga; Naor, Assaf

Approximating the cut-norm via Grothendieck’s inequality. (English) Zbl 1192.68866

Proceedings of the 36th annual ACM symposium on theory of computing (STOC 2004), Chicago, IL, USA, June 13 - 15, 2004. New York, NY: ACM Press (ISBN 1-58113-852-0). 72-80, electronic only (2004).

MSC: 68W25 15A60 65D15 90C22 90C27

Cite Review PDF

Full Text: DOI

Found 72 Documents (Results 1–72)

The two possible values of the chromatic number of a random graph. (English) Zbl 1192.05140

Sharp thresholds for monotone properties in random geometric graphs. (English) Zbl 1192.05145

Approximate max-integral-flow/min-multicut theorems. (English) Zbl 1192.90236

({A}lmost) tight bounds and existence theorems for confluent flows. (English) Zbl 1192.90022

The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results. (English) Zbl 1192.91101

Auction algorithms for market equilibrium. (English) Zbl 1192.91011

The quantum adiabatic optimization algorithm and local minima. (English) Zbl 1192.81098

Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. (English) Zbl 1192.05162

Finding paths and cycles of superpolylogarithmic length. (English) Zbl 1192.68361

An approximate König’s theorem for edge-coloring weighted bipartite graphs. (English) Zbl 1192.05046

Primal-dual algorithms for deterministic inventory problems. (English) Zbl 1192.90010

Typical properties of winners and losers in discrete optimization. (English) Zbl 1192.90156

A simple polynomial-time rescaling algorithm for solving linear programs. (English) Zbl 1192.90116

Completeness in two-party secure computation: a computational view. (English) Zbl 1192.94120

New notions of security: achieving universal composability without trusted setup. (English) Zbl 1192.94124

Multilinear formulas and skepticism of quantum computing. (English) Zbl 1192.81045

Graph entropy and quantum sorting problems. (English) Zbl 1192.81109

Multi-linear formulas for permanent and determinant are of super-polynomial size. (English) Zbl 1192.68328

Depth through breadth, or why should we attend talks in other areas? (English) Zbl 1192.68254

Using mixture models for collaborative filtering. (English) Zbl 1192.68685

A decentralized algorithm for spectral analysis. (English) Zbl 1192.68848

Lower bounds for linear degeneracy testing. (English) Zbl 1192.68306

Lower bounds for dynamic connectivity. (English) Zbl 1192.68185

Quantum and classical query complexities of local search are polynomially related. (English) Zbl 1192.68266

A conjecture about polynomial time computable lattice-lattice functions. (English) Zbl 1192.68335

Counting complexity classes for numeric computations. II. Algebraic and semialgebraic sets. (English) Zbl 1192.68289

Lower bounds for local search by quantum arguments. (English) Zbl 1192.68256

A new family of Cayley expanders (?). (English) Zbl 1192.68862

Better extractors for better codes? (English) Zbl 1192.68363

Derandomizing homomorphism testing in general groups. (English) Zbl 1192.68378

Boosted sampling: approximation algorithms for stochastic optimization. (English) Zbl 1192.90171

The difficulty of testing for isomorphism against a graph that is given in advance. (English) Zbl 1192.68857

Sublinear algorithms for testing monotone and unimodal distributions. (English) Zbl 1192.68345

Algorithms for dynamic geometric problems over data streams. (English) Zbl 1192.68179

Multi-processor scheduling to minimize flow time with \(\epsilon\) resource augmentation. (English) Zbl 1192.68096

Network games. (English) Zbl 1192.91046

Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. (English) Zbl 1192.68319

Collective asynchronous reading with polylogarithmic worst-case overhead. (English) Zbl 1192.68079

Hit-and-run from a corner. (English) Zbl 1192.68371

Isotopic implicit surface meshing. (English) Zbl 1192.65016

On coresets for \(k\)-means and \(k\)-median clustering. (English) Zbl 1192.68904

Bypassing the embedding: algorithms for low dimensional metrics. (English) Zbl 1192.68918

Low distortion maps between point sets. (English) Zbl 1192.68366

Batch codes and their applications. (English) Zbl 1192.94100

Bounded-concurrent secure multi-party computation with a dishonest majority. (English) Zbl 1192.68077

Expander flows, geometric embeddings and graph partitioning. (English) Zbl 1192.68467

Linear FPT reductions and computational lower bounds. (English) Zbl 1192.68313

Visibly pushdown languages. (English) Zbl 1192.68396

Using nondeterminism to amplify hardness. (English) Zbl 1192.68294

A fully dynamic reachability algorithm for directed graphs with an almost linear update time. (English) Zbl 1192.90238

Estimating the weight of metric minimum spanning trees in sublinear-time. (English) Zbl 1192.68888

Approximation algorithms for deadline-TSP and vehicle routing with time-windows. (English) Zbl 1192.90216

The all-or-nothing multicommodity flow problem. (English) Zbl 1192.68878

Approximation algorithm for \(k\)-node connected subgraphs via critical graphs. (English) Zbl 1192.90233

Exponential separation of quantum and classical one-way communication complexity. (English) Zbl 1192.81052

Sorting and searching in the presence of memory faults (without redundancy). (English) Zbl 1192.68958

Dictionary matching and indexing with errors and don’t cares. (English) Zbl 1192.68818

The zero-one principle for switching networks. (English) Zbl 1192.68021

Know thy neighbor’s neighbor: the power of lookahead in randomized P2P networks. (English) Zbl 1192.68048

Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. (English) Zbl 1192.68020

On the performance of greedy algorithms in packet buffering. (English) Zbl 1192.68938

New hardness results for congestion minimization and machine scheduling. (English) Zbl 1192.90254

Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate. (English) Zbl 1192.68314

A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. (English) Zbl 1192.68324

Robust PSPs of proximity, shorter PSPs and applications to coding. (English) Zbl 1192.68286

Rational secret sharing and multiparty computation. (English) Zbl 1192.94119

Computing Nash equilibria for scheduling on restricted parallel links. (English) Zbl 1192.90072

The complexity of pure Nash equilibria. (English) Zbl 1192.91042

On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. (English) Zbl 1192.60021

Quantum algorithms a decade after Shor. (English) Zbl 1192.81049

Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. (English) Zbl 1192.65048

Approximating the cut-norm via Grothendieck’s inequality. (English) Zbl 1192.68866

Filter Results by …

Author

Main Field

Software

**Asymmetric \(k\)-center is \(\log{^*}{n}\)-hard to approximate.** (English) Zbl 1192.68314