43. FOCS 2002: Vancouver, BC, Canada

43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings. IEEE Computer Society 2002, ISBN 0-7695-1822-2 BibTeX

@proceedings{DBLP:conf/focs/2002,
  title     = {43rd Symposium on Foundations of Computer Science (FOCS 2002),
               16-19 November 2002, Vancouver, BC, Canada, Proceedings},
  booktitle = {FOCS},
  publisher = {IEEE Computer Society},
  year      = {2002},
  isbn      = {0-7695-1822-2},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Tutorial 1

Oded Goldreich:
Zero-Knowledge. 3-
Electronic Edition (link) BibTeX

Tutorial 3

Salil P. Vadhan:
Randomness Extractors and their Many Guises. 9-
Electronic Edition (link) BibTeX

Session 1A

Oded Goldreich, Madhu Sudan:
Locally Testable Codes and PCPs of Almost-Linear Length. 13-22
Electronic Edition (link) BibTeX
Subhash Khot:
Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs. 23-32
Electronic Edition (link) BibTeX
Irit Dinur, Oded Regev, Clifford D. Smyth:
The Hardness of 3 - Uniform Hypergraph Coloring. 33-
Electronic Edition (link) BibTeX

Session 1B

Harald Räcke:
Minimizing Congestion in General Networks. 43-52
Electronic Edition (link) BibTeX
Stephen Alstrup, Theis Rauhe:
Small Induced-Universal Graphs and Compact Implicit Graph Representations. 53-62
Electronic Edition (link) BibTeX
Dariusz R. Kowalski, Andrzej Pelc:
Deterministic Broadcasting Time in Radio Networks of Unknown Topology. 63-72
Electronic Edition (link) BibTeX
Noga Alon, Michael R. Capalbo:
Explicit Unique-Neighbor Expanders. 73-
Electronic Edition (link) BibTeX

Session 2A

Artur Czumaj, Christian Sohler:
Abstract Combinatorial Programs and Efficient Property Testers. 83-92
Electronic Edition (link) BibTeX
Andrej Bogdanov, Kenji Obata, Luca Trevisan:
A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. 93-102
Electronic Edition (link) BibTeX
Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky:
Testing Juntas. 103-112
Electronic Edition (link) BibTeX
Santosh Vempala, Grant Wang:
A Spectral Algorithm for Learning Mixtures of Distributions. 113-
Electronic Edition (link) BibTeX

Session 2B

Mikkel Thorup:
Equivalence between Priority Queues and Sorting. 125-134
Electronic Edition (link) BibTeX
Yijie Han, Mikkel Thorup:
Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space. 135-144
Electronic Edition (link) BibTeX
Gianni Franceschini, Roberto Grossi, J. Ian Munro, Linda Pagli:
Implicit B-Trees: New Results for the Dictionary Problem. 145-154
Electronic Edition (link) BibTeX
Seth Pettie:
An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree. 155-
Electronic Edition (link) BibTeX

Session 3A

Nader H. Bshouty, Dmitry Gavinsky:
PAC = PAExact and Other Equivalent Models in Learning. 167-176
Electronic Edition (link) BibTeX
Adam Klivans, Ryan O'Donnell, Rocco A. Servedio:
Learning Intersections and Thresholds of Halfspaces. 177-186
Electronic Edition (link) BibTeX
Vladimir Vovk:
On-Line Confidence Machines Are Well-Calibrated. 187-196
Electronic Edition (link) BibTeX
Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov:
Learning a Hidden Matching. 197-
Electronic Edition (link) BibTeX

Session 3B

Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar:
An Information Statistics Approach to Data Stream and Communication Complexity. 209-218
Electronic Edition (link) BibTeX
Valentina Ciriani, Paolo Ferragina, Fabrizio Luccio, S. Muthukrishnan:
Static Optimality Theorem for External Memory String Access. 219-227
Electronic Edition (link) BibTeX
Eli Gafni:
A Simple Algorithmic Characterization of Uniform Solvability. 228-237
Electronic Edition (link) BibTeX
Nikhil Bansal, Avrim Blum, Shuchi Chawla:
Correlation Clustering. 238-
Electronic Edition (link) BibTeX

Session 4A

Jon Feldman, David R. Karger:
Decoding Turbo-Like Codes via Linear Programming. 251-260
Electronic Edition (link) BibTeX
Amos Beimel, Yuval Ishai, Eyal Kushilevitz, Jean-François Raymond:
Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval. 261-270
Electronic Edition (link) BibTeX
Michael Luby:
LT Codes. 271-
Electronic Edition (link) BibTeX

Session 4B

Uriel Feige, Michael Langberg, Gideon Schechtman:
Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. 283-292
Electronic Edition (link) BibTeX
Matthew Andrews, Lisa Zhang:
Scheduling Over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data. 293-302
Electronic Edition (link) BibTeX
Naveen Garg, Neal E. Young:
On-Line End-to-End Congestion Control. 303-312
Electronic Edition (link) BibTeX

Session 1A

Sanjeev Arora, Béla Bollobás, László Lovász:
Proving Integrality Gaps without Knowing the Linear Program. 313-322
Electronic Edition (link) BibTeX
Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan:
Dependent Rounding in Bipartite Graphs. 323-332
Electronic Edition (link) BibTeX
Amit Kumar, Anupam Gupta, Tim Roughgarden:
A Constant-Factor Approximation Algorithm for the Multicommodity. 333-
Electronic Edition (link) BibTeX

Session 1B

Boaz Barak:
Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model. 345-355
Electronic Edition (link) BibTeX
Daniele Micciancio:
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions. 356-365
Electronic Edition (link) BibTeX
Manoj Prabhakaran, Alon Rosen, Amit Sahai:
Concurrent Zero Knowledge with Logarithmic Round-Complexity. 366-375
Electronic Edition (link) BibTeX
Yevgeniy Dodis, Joel Spencer:
On the (non)Universality of the One-Time Pad. 376-
Electronic Edition (link) BibTeX

Session 2A

Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani:
Market Equilibrium via a Primal-Dual-Type Algorithm. 389-395
Electronic Edition (link) BibTeX
Amir Ronen, Amin Saberi:
On the Hardness of Optimal Auctions. 396-405
Electronic Edition (link) BibTeX
Liad Blumrosen, Noam Nisan:
Auctions with Severely Bounded Communication. 406-415
Electronic Edition (link) BibTeX
Adrian Vetta:
Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions. 416-
Electronic Edition (link) BibTeX

Session 2B

Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen:
Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States. 429-438
Electronic Edition (link) BibTeX
Michael Alekhnovich:
Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes. 439-448
Electronic Edition (link) BibTeX
Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith, Alain Tapp:
Authentication of Quantum Messages. 449-458
Electronic Edition (link) BibTeX
John Watrous:
imits on the Power of Quantum Statistical Zero-Knowledge. 459-
Electronic Edition (link) BibTeX

Session 3A

David Kempe, Jon M. Kleinberg:
Protocols and Impossibility Results for Gossip-Based Communication Mechanisms. 471-480
Electronic Edition (link) BibTeX
Julia Chuzhoy, Joseph Naor:
Covering Problems with Hard Capacities. 481-489
Electronic Edition (link) BibTeX
Alberto Caprara:
Packing 2-Dimensional Bins in Harmony. 490-499
Electronic Edition (link) BibTeX
Naveen Garg, Rohit Khandekar:
Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems. 500-
Electronic Edition (link) BibTeX

Session 3B

Yaoyun Shi:
Quantum Lower Bounds for the Collision and the Element Distinctness Problems. 513-519
Electronic Edition (link) BibTeX
Oded Regev:
Quantum Computation and Lattice Problems. 520-529
Electronic Edition (link) BibTeX
Leonard M. Adleman, Jarkko Kari, Lila Kari, Dustin Reishus:
On the Decidability of Self-Assembly of Infinite Ribbons. 530-537
Electronic Edition (link) BibTeX
Jörg Flum, Martin Grohe:
The Parameterized Complexity of Counting Problems. 538-
Electronic Edition (link) BibTeX

Session 4A

Moses Charikar, Amit Sahai:
Dimension Reduction in the \ell _1 Norm. 551-560
Electronic Edition (link) BibTeX
Kasturi R. Varadarajan, Srinivasan Venkatesh, Jiawei Zhang:
On Approximating the Radii of Point Sets in High Dimensions. 561-569
Electronic Edition (link) BibTeX
Timothy M. Chan:
Low-Dimensional Linear Programming with Violations. 570-
Electronic Edition (link) BibTeX

Session 4B

Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal:
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. 583-592
Electronic Edition (link) BibTeX
Michael Alekhnovich, Alexander A. Razborov:
Satisfiability, Branch-Width and Tseitin Tautologies. 593-603
Electronic Edition (link) BibTeX
Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo:
A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. 604-
Electronic Edition (link) BibTeX

Session 1A

Gerth Stølting Brodal, Riko Jacob:
Dynamic Planar Convex Hull. 617-626
Electronic Edition (link) BibTeX
Éric Colin de Verdière, Francis Lazarus:
Optimal System of Loops on an Orientable Surface. 627-636
Electronic Edition (link) BibTeX
Vladlen Koltun, Micha Sharir:
The Partition Technique for Overlays of Envelopes. 637-
Electronic Edition (link) BibTeX

Session 1B

Andrei A. Bulatov:
A Dichotomy Theorem for Constraints on a Three-Element Set. 649-658
Electronic Edition (link) BibTeX
Peter Bürgisser, Martin Lotz:
Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps. 659-668
Electronic Edition (link) BibTeX
Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, Detlef Ronneburger:
Power from Random Strings. 669-678
Electronic Edition (link) BibTeX
Liam Roditty, Uri Zwick:
Improved Dynamic Reachability Algorithms for Directed Graphs. 679-
Electronic Edition (link) BibTeX

Session 2A

Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky:
Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks. 691-700
Electronic Edition (link) BibTeX
Itai Benjamini, László Lovász:
Global Information from Local Observation. 701-710
Electronic Edition (link) BibTeX
Mary Cryan, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell A. Martin:
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. 711-720
Electronic Edition (link) BibTeX
Mark Jerrum, Jung-Bae Son:
Spectral Gap and log-Sobolev Constant for Balanced Matroids. 721-
Electronic Edition (link) BibTeX

Session 2B

Miklós Ajtai:
Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties. 733-742
Electronic Edition (link) BibTeX
Vikraman Arvind, Piyush P. Kurur:
Graph Isomorphism is in SPP. 743-750
Electronic Edition (link) BibTeX
Nikolai K. Vereshchagin, Paul M. B. Vitányi:
Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. 751-760
Electronic Edition (IEEE Computer Society DL) BibTeX
Leonid A. Levin:
Forbidden Information. 761-
Electronic Edition (link) BibTeX

Session 3

Olivier Dubois, Jacques Mandler:
The 3-XORSAT Threshold. 769-778
Electronic Edition (link) BibTeX
Dimitris Achlioptas, Cristopher Moore:
The Asymptotic Order of the Random k -SAT Threshold. 779-788
Electronic Edition (link) BibTeX
Alan M. Frieze:
On Random Symmetric Travelling Salesman Problems. 789-798
Electronic Edition (link) BibTeX
Michael Mitzenmacher, Balaji Prabhakar, Devavrat Shah:
Load Balancing with Memory. 799-808
Electronic Edition (link) BibTeX
John Hershberger, Subhash Suri:
Erratum to "Vickrey Pricing and Shortest Paths: What is an Edge Worth?". 809-
Electronic Edition (link) BibTeX