Conferences in DBLP
Oded Goldreich Zero-Knowledge. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:3-0 [Conf ] Salil P. Vadhan Randomness Extractors and their Many Guises. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:9-0 [Conf ] Oded Goldreich , Madhu Sudan Locally Testable Codes and PCPs of Almost-Linear Length. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:13-22 [Conf ] Subhash Khot Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:23-32 [Conf ] Irit Dinur , Oded Regev , Clifford D. Smyth The Hardness of 3 - Uniform Hypergraph Coloring. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:33-0 [Conf ] Harald Räcke Minimizing Congestion in General Networks. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:43-52 [Conf ] Stephen Alstrup , Theis Rauhe Small Induced-Universal Graphs and Compact Implicit Graph Representations. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:53-62 [Conf ] Dariusz R. Kowalski , Andrzej Pelc Deterministic Broadcasting Time in Radio Networks of Unknown Topology. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:63-72 [Conf ] Noga Alon , Michael R. Capalbo Explicit Unique-Neighbor Expanders. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:73-0 [Conf ] Artur Czumaj , Christian Sohler Abstract Combinatorial Programs and Efficient Property Testers. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:83-92 [Conf ] Andrej Bogdanov , Kenji Obata , Luca Trevisan A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:93-102 [Conf ] Eldar Fischer , Guy Kindler , Dana Ron , Shmuel Safra , Alex Samorodnitsky Testing Juntas. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:103-112 [Conf ] Santosh Vempala , Grant Wang A Spectral Algorithm for Learning Mixtures of Distributions. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:113-0 [Conf ] Mikkel Thorup Equivalence between Priority Queues and Sorting. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:125-134 [Conf ] Yijie Han , Mikkel Thorup Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:135-144 [Conf ] Gianni Franceschini , Roberto Grossi , J. Ian Munro , Linda Pagli Implicit B-Trees: New Results for the Dictionary Problem. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:145-154 [Conf ] Seth Pettie An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:155-0 [Conf ] Nader H. Bshouty , Dmitry Gavinsky PAC = PAExact and Other Equivalent Models in Learning. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:167-176 [Conf ] Adam Klivans , Ryan O'Donnell , Rocco A. Servedio Learning Intersections and Thresholds of Halfspaces. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:177-186 [Conf ] Vladimir Vovk On-Line Confidence Machines Are Well-Calibrated. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:187-196 [Conf ] Noga Alon , Richard Beigel , Simon Kasif , Steven Rudich , Benny Sudakov Learning a Hidden Matching. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:197-0 [Conf ] Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar An Information Statistics Approach to Data Stream and Communication Complexity. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:209-218 [Conf ] Valentina Ciriani , Paolo Ferragina , Fabrizio Luccio , S. Muthukrishnan Static Optimality Theorem for External Memory String Access. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:219-227 [Conf ] Eli Gafni A Simple Algorithmic Characterization of Uniform Solvability. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:228-237 [Conf ] Nikhil Bansal , Avrim Blum , Shuchi Chawla Correlation Clustering. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:238-0 [Conf ] Jon Feldman , David R. Karger Decoding Turbo-Like Codes via Linear Programming. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:251-260 [Conf ] Amos Beimel , Yuval Ishai , Eyal Kushilevitz , Jean-François Raymond Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:261-270 [Conf ] Michael Luby LT Codes. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:271-0 [Conf ] Uriel Feige , Michael Langberg , Gideon Schechtman Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:283-292 [Conf ] Matthew Andrews , Lisa Zhang Scheduling Over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:293-302 [Conf ] Naveen Garg , Neal E. Young On-Line End-to-End Congestion Control. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:303-312 [Conf ] Sanjeev Arora , Béla Bollobás , László Lovász Proving Integrality Gaps without Knowing the Linear Program. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:313-322 [Conf ] Rajiv Gandhi , Samir Khuller , Srinivasan Parthasarathy 0002 , Aravind Srinivasan Dependent Rounding in Bipartite Graphs. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:323-332 [Conf ] Amit Kumar , Anupam Gupta , Tim Roughgarden A Constant-Factor Approximation Algorithm for the Multicommodity. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:333-0 [Conf ] Boaz Barak Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:345-355 [Conf ] Daniele Micciancio Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:356-365 [Conf ] Manoj Prabhakaran , Alon Rosen , Amit Sahai Concurrent Zero Knowledge with Logarithmic Round-Complexity. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:366-375 [Conf ] Yevgeniy Dodis , Joel Spencer On the (non)Universality of the One-Time Pad. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:376-0 [Conf ] Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , Vijay V. Vazirani Market Equilibrium via a Primal-Dual-Type Algorithm. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:389-395 [Conf ] Amir Ronen , Amin Saberi On the Hardness of Optimal Auctions. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:396-405 [Conf ] Liad Blumrosen , Noam Nisan Auctions with Severely Bounded Communication. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:406-415 [Conf ] Adrian Vetta Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:416-0 [Conf ] Rahul Jain , Jaikumar Radhakrishnan , Pranab Sen Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:429-438 [Conf ] Michael Alekhnovich Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:439-448 [Conf ] Howard Barnum , Claude Crépeau , Daniel Gottesman , Adam Smith , Alain Tapp Authentication of Quantum Messages. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:449-458 [Conf ] John Watrous imits on the Power of Quantum Statistical Zero-Knowledge. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:459-0 [Conf ] David Kempe , Jon M. Kleinberg Protocols and Impossibility Results for Gossip-Based Communication Mechanisms. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:471-480 [Conf ] Julia Chuzhoy , Joseph Naor Covering Problems with Hard Capacities. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:481-489 [Conf ] Alberto Caprara Packing 2-Dimensional Bins in Harmony. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:490-499 [Conf ] Naveen Garg , Rohit Khandekar Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:500-0 [Conf ] Yaoyun Shi Quantum Lower Bounds for the Collision and the Element Distinctness Problems. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:513-519 [Conf ] Oded Regev Quantum Computation and Lattice Problems. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:520-529 [Conf ] Leonard M. Adleman , Jarkko Kari , Lila Kari , Dustin Reishus On the Decidability of Self-Assembly of Infinite Ribbons. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:530-537 [Conf ] Jörg Flum , Martin Grohe The Parameterized Complexity of Counting Problems. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:538-0 [Conf ] Moses Charikar , Amit Sahai Dimension Reduction in the \ell _1 Norm. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:551-560 [Conf ] Kasturi R. Varadarajan , Srinivasan Venkatesh , Jiawei Zhang On Approximating the Radii of Point Sets in High Dimensions. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:561-569 [Conf ] Timothy M. Chan Low-Dimensional Linear Programming with Violations. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:570-0 [Conf ] Josh Buresh-Oppenheim , Paul Beame , Toniann Pitassi , Ran Raz , Ashish Sabharwal Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:583-592 [Conf ] Michael Alekhnovich , Alexander A. Razborov Satisfiability, Branch-Width and Tseitin Tautologies. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:593-603 [Conf ] Nathan Segerlind , Samuel R. Buss , Russell Impagliazzo A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:604-0 [Conf ] Gerth Stølting Brodal , Riko Jacob Dynamic Planar Convex Hull. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:617-626 [Conf ] Éric Colin de Verdière , Francis Lazarus Optimal System of Loops on an Orientable Surface. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:627-636 [Conf ] Vladlen Koltun , Micha Sharir The Partition Technique for Overlays of Envelopes. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:637-0 [Conf ] Andrei A. Bulatov A Dichotomy Theorem for Constraints on a Three-Element Set. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:649-658 [Conf ] Peter Bürgisser , Martin Lotz Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:659-668 [Conf ] Eric Allender , Harry Buhrman , Michal Koucký , Dieter van Melkebeek , Detlef Ronneburger Power from Random Strings. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:669-678 [Conf ] Liam Roditty , Uri Zwick Improved Dynamic Reachability Algorithms for Directed Graphs. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:679-0 [Conf ] Guy Even , Zvi Lotker , Dana Ron , Shakhar Smorodinsky Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:691-700 [Conf ] Itai Benjamini , László Lovász Global Information from Local Observation. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:701-710 [Conf ] 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. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:711-720 [Conf ] Mark Jerrum , Jung-Bae Son Spectral Gap and log-Sobolev Constant for Balanced Matroids. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:721-0 [Conf ] Miklós Ajtai Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:733-742 [Conf ] Vikraman Arvind , Piyush P. Kurur Graph Isomorphism is in SPP. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:743-750 [Conf ] Nikolai K. Vereshchagin , Paul M. B. Vitányi Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:751-760 [Conf ] Leonid A. Levin Forbidden Information. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:761-0 [Conf ] Olivier Dubois , Jacques Mandler The 3-XORSAT Threshold. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:769-778 [Conf ] Dimitris Achlioptas , Cristopher Moore The Asymptotic Order of the Random k -SAT Threshold. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:779-788 [Conf ] Alan M. Frieze On Random Symmetric Travelling Salesman Problems. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:789-798 [Conf ] Michael Mitzenmacher , Balaji Prabhakar , Devavrat Shah Load Balancing with Memory. [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:799-808 [Conf ] John Hershberger , Subhash Suri Erratum to "Vickrey Pricing and Shortest Paths: What is an Edge Worth?". [Citation Graph (0, 0)][DBLP ] FOCS, 2002, pp:809-0 [Conf ]