default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID43rd FOCS 2002: Vancouver, BC, Canada
- 43rd Symposium on Foundations of Computer Science, FOCS 2002, Vancouver, BC, Canada, November 16-19, 2002, 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 S. 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 R. 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 Rent-or-Buy Problem. 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 D. 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-
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-05 22:23 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
