17th IEEE Annual Conference on Computational Complexity (CCC 2002)

• Record Nr.: UNINA9910872712803321
• Pubbl/distr/stampa: [Place of publication not identified], : IEEE Computer Society Press, 2002
• Descrizione fisica: 1 online resource (xii, 205 pages) : illustrations
• Disciplina: 511.3
• Soggetti: Computational complexity
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: Preface -- Committees -- Ron Book Prize for Best Student Paper -- 2002 Best Paper Award -- Resolution Lower Bounds for the Weak Pigeonhole Principle -- Hard examples for bounded depth frege -- Resolution lower bounds for the weak pigeon hole principle -- Hard examples for bounded depth Frege -- Improved cryptographic hash functions with worst-case/average-case connection -- Algorithmic derandomization via complexity theory -- Pseudo-random generators for all hardnesses -- Randomness conductors and constant-degree lossless expanders -- Expanders from symmetric codes -- The complexity of approximating the entropy -- Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems -- On communication over an entanglement-assisted quantum channel -- Hardness amplification within NP -- 3-MANIFOLD KNOT GENUS is NP-complete -- On the power of unique 2-prover 1-round games -- Learnability beyond AC/sup 0/ -- Resolution lower bounds for perfect matching principles -- Resolution width-size trade-offs for the Pigeon-Hole Principle -- The inapproximability of lattice and coding problems with preprocessing -- Sampling short lattice vectors and the closest lattice vector problem -- The history of complexity -- The correlation between parity and quadratic polynomials mod 3 -- Functions that have read-twice constant width branching programs are not necessarily testable -- On the complexity of integer multiplication in branching programs with multiple tests and in read-once branching programs with limited nondeterminism -- Information theory methods ; in communication complexity -- Extracting quantum entanglement (general entanglement purification protocols) -- Algebras of minimal rank over perfect fields -- Rapid mixing -- Pseudorandomness and average-case complexity via uniform reductions -- Pseudo-random generators and structure of complete degrees -- Decoding concatenated codes using soft information -- Arthur and Merlin in a quantum world -- Streaming computation of combinatorial objects -- Lower bounds for linear locally decodable codes and private information retrieval -- Better lower bounds for locally decodable codes -- Universal arguments and their applications -- Author index.
• Sommario/riassunto: Thirty-six papers originally presented at the May 2002 conference sponsored by the IEEE Computer Society cover a range of issues in computational complexity. They look at such topics as hard examples for bounded depth frege, relations between average case complexity and approximation complexity, algorithmic derandomization via complexity theory, randomness conductors and constant-degree lossless expanders, resolution lower bounds for perfect matching principles, information theory methods in communication complexity, and pseudo-random generators and structure of complete degrees. Annotation copyrighted by Book News, Inc., Portland, OR.