43rd Symposium on Foundations of Computer Science (FOCS 2002)

• Record Nr.: UNISA996198560903316
• Pubbl/distr/stampa: [Place of publication not identified], : IEEE Computer Society Press, 2002
• Descrizione fisica: 1 online resource (xvi, 813 pages) : illustrations
• Disciplina: 004
• Soggetti: Computer science; Machine theory
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: Foreword -- 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.
• Sommario/riassunto: Collects 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.