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

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-

Last update Sat May 25 02:54:13 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page