{"text_format":"2","workbook":"xls","n_sheets":1,"sheets":["report2"],"not_rendered":{"charts":0,"images":0,"macros":0,"external_links":1,"defined_names":1,"comments":0,"pivot_tables":0},"unopened":[],"bounds":{"document_bytes":16777216,"sheet_cells":100000,"run_cost":"one","rows_first":2000,"rows_last":500,"rows_between":2000,"halvings":0,"cell_chars":16384,"cell_head_chars":4096},"cells_cut":0,"cells_raw":0,"read":"whole","date_system":"1900","formulas":"cached_only"}

{"sheet":"report2","index":0,"n_rows":15,"n_cols":5,"rows_kept":15,"cut":false,"hidden":false,"merged":[[0,2,0,3],[0,4,0,5],[1,2,1,3],[1,4,1,5],[2,2,2,3],[3,2,3,3],[4,2,4,3],[5,2,5,3],[7,2,7,3],[8,2,8,3],[11,2,11,3]],"flags":["formulas_cached_only"]}
[null,"1.","Record Nr.",null,"UNINA9910872917503321"]
[null,null,"Titolo",null,"43rd Symposium on Foundations of Computer Science (FOCS 2002)"]
[null,null,"Pubbl/distr/stampa",null,"[Place of publication not identified], : IEEE Computer Society Press, 2002"]
[null,null,"Descrizione fisica",null,"1 online resource (xvi, 813 pages) : illustrations"]
[null,null,"Disciplina",null,"004"]
[null,null,"Soggetti",null,"Computer science"]
[{"$nulls":4},"Machine theory"]
[null,null,"Lingua di pubblicazione",null,"Inglese"]
[null,null,"Formato",null,"Materiale a stampa"]
[null,null,null,"Livello bibliografico","Monografia"]
[null,null,null,"Note generali","Bibliographic Level Mode of Issuance: Monograph"]
[null,null,"Nota di contenuto",null,"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 "]
[{"$nulls":4},"-- 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."]
[null,null,null,"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 "]
[{"$nulls":4},"of counting problems, and a partition technique for overlays of envelopes. No subject index. Annotation copyrighted by Book News, Inc., Portland, OR."]