43. FOCS 2002: Vancouver, BC, Canada

@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-
  

Tutorial 3

• Salil P. Vadhan:
  Randomness Extractors and their Many Guises. 9-
  

Session 1A

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

Session 1B

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

Session 2A

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

Session 2B

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

Session 3A

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

Session 3B

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

Session 4A

• Jon Feldman, David R. Karger:
  Decoding Turbo-Like Codes via Linear Programming. 251-260
  
• 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
  
• Michael Luby:
  LT Codes. 271-
  

Session 4B

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

Session 1A

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

Session 1B

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

Session 2A

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

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
  
• Michael Alekhnovich:
  Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes. 439-448
  
• Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith, Alain Tapp:
  Authentication of Quantum Messages. 449-458
  
• John Watrous:
  imits on the Power of Quantum Statistical Zero-Knowledge. 459-
  

Session 3A

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

Session 3B

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

Session 4A

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

Session 4B

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

Session 1A

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

Session 1B

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

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
  
• Itai Benjamini, László Lovász:
  Global Information from Local Observation. 701-710
  
• 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
  
• Mark Jerrum, Jung-Bae Son:
  Spectral Gap and log-Sobolev Constant for Balanced Matroids. 721-
  

Session 2B

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

Session 3

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