LEADER 06897oam 2200421zu 450 001 996198560903316 005 20210807003354.0 035 $a(CKB)111085500343004 035 $a(SSID)ssj0000451601 035 $a(PQKBManifestationID)12155642 035 $a(PQKBTitleCode)TC0000451601 035 $a(PQKBWorkID)10463265 035 $a(PQKB)11076442 035 $a(NjHacI)99111085500343004 035 $a(EXLCZ)99111085500343004 100 $a20160829d2002 uy 101 0 $aeng 135 $aur||||||||||| 181 $ctxt 182 $cc 183 $acr 200 10$a43rd Symposium on Foundations of Computer Science (FOCS 2002) 210 31$a[Place of publication not identified]$cIEEE Computer Society Press$d2002 215 $a1 online resource (xvi, 813 pages) $cillustrations 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a0-7695-1822-2 327 $aForeword -- Program Committee -- Reviewers -- TUTORIAL 1 -- Zero-Knowledge -- TUTORIAL 2 -- Approximation Algorithms -- TUTORIAL 3 -- Randomness Extractors and Their Many Guises -- SESSION 1A -- Locally Testable Codes and PCPs of Almost-Linear Length -- Hardness Results for Coloring 3-Colorable 3-Uniform Hypergraphs -- The Hardness of 3-Uniform Hypergraph Coloring -- SESSION 1B -- Minimizing Congestion in General Networks -- Small Induced-Universal Graphs and Compact Implicit Graph Representations -- Deterministic Broadcasting Time in Radio Networks of Unknown Topology -- Explicit Unique-Neighbor Expanders -- SESSION 2A -- Abstract Combinatorial Programs and Efficient Property Testers -- A Lower Bound for Testing 3-Colorability in Bounded-Degree Graphs -- Testing Juntas -- A Spectral Algorithm for Learning Mixtures of Distributions -- Equivalence between Priority Queues and Sorting -- Implicit B-Trees: New Results for the Dictionary Problem -- An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree Verification Problem -- PAC = PAExact and Other Equivalent Models in Learning -- Learning Intersections and Thresholds of Halfspaces -- On-Line Confidence Machines Are Well-Calibrated -- Learning a Hidden Matching -- An Information Statistics Approach to Data Stream and Communication Complexity -- Correlation Clustering -- SESSION 4A -- Decoding Turbo-Like Codes via Linear Programming -- Breaking the O(n1/2k-1) Barrier for Information-Theoretic Private Information Retrieval -- SESSION 4B -- Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers -- Scheduling over a Time-Varying User-Dependent Channel with Applications to High Speed Wireless Data -- SESSION 1A -- David Shmoys -- Proving Integrality Gaps without Knowing the Linear Program -- Dependent Rounding in Bipartite Graphs -- A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem -- SESSION 1B -- Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model -- Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions -- Concurrent Zero Knowledge with Logarithmic Round-Complexity -- On the (non)Universality of the One-Time Pad -- Market Equilibrium via a Primal-Dual-Type Algorithm -- On the Hardness of Optimal Auctions -- Auctions with Severely Bounded Communication -- Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions -- SESSION 2B -- Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States -- Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes -- Authentication of Quantum Messages -- Limits on the Power of Quantum Statistical Zero-Knowledge -- SESSION 3A -- Protocols and Impossibility Results for Gossip-Based Communication Mechanisms -- Covering Problems with Hard Capacities -- Packing 2-Dimensional Bins in Harmony -- Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems -- SESSION 3B -- Quantum Lower Bounds for the Collision and the Element Distinctness Problems -- Quantum Computation and Lattice Problems -- On the Decidability of Self-Assembly of Infinite Ribbons -- The Parameterized Complexity of Counting Problems -- SESSION 4A -- Dimension Reduction in the l1 Norm -- On Approximating the Radii of Point Sets in High Dimensions -- Low-Dimensional Linear Programming with Violations -- Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles -- Satisfiability, Branch-Width and Tseitin Tautologies -- A Switching Lemma for Small Restrictions and Lower Bounds for k-DNF Resolution -- SESSION 1A -- Dynamic Planar Convex Hull -- Optimal System of Loops on an Orientable Surface -- SESSION 1B -- A Dichotomy Theorem for Constraints on a Thre-Element Set -- Lower Bounds on the Bounded Coefficient Complexity of Bilinear Maps -- Power from Random Strings -- Improved Dynamic Reachability Algorithms for Directed Graphs -- SESSION 2A -- Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks -- Global Information from Local Observation -- Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows -- Spectral Gap and log-Sobolev Constant for Balanced Matroids -- SESSION 2B -- Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties -- Graph Isomorphism is in SPP -- Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection -- Forbidden Information -- SESSION 3 -- The 3-Xorsat Threshold -- The Asymptotic Order of the Random k-SAT Threshold -- On Random Symmetric Travelling Salesman Problems -- Load Balancing with Memory -- Erratum to "Vickrey Pricing and Shortest Paths: What Is an Edge Worth?" -- Author Index. 330 $aCollects the 77 papers presented during the November 2002 symposium on the mathematical foundations of computing. Among the topics are abstract combinatorial programs and efficient property testers, a lower bound for testing 3-colorability in bounded degree graphs, a spectral algorithm for learning mixtures of distributions, and concurrent zero knowledge with logarithmic round complexity. Other topics include minimizing congestion in general networks, decoding turbo-like codes via linear programming, the parameterized complexity of counting problems, and a partition technique for overlays of envelopes. No subject index. Annotation copyrighted by Book News, Inc., Portland, OR. 606 $aComputer science$vCongresses 606 $aMachine theory$vCongresses 615 0$aComputer science 615 0$aMachine theory 676 $a004 801 0$bPQKB 906 $aPROCEEDING 912 $a996198560903316 996 $a43rd Symposium on Foundations of Computer Science (FOCS 2002)$92356127 997 $aUNISA