LEADER 04135oam 2200409zu 450 001 996200685103316 005 20210807003531.0 035 $a(CKB)111055184227354 035 $a(SSID)ssj0000455445 035 $a(PQKBManifestationID)12148338 035 $a(PQKBTitleCode)TC0000455445 035 $a(PQKBWorkID)10399643 035 $a(PQKB)11548361 035 $a(NjHacI)99111055184227354 035 $a(EXLCZ)99111055184227354 100 $a20160829d2002 uy 101 0 $aeng 135 $aur||||||||||| 181 $ctxt 182 $cc 183 $acr 200 10$a17th IEEE Annual Conference on Computational Complexity (CCC 2002) 210 31$a[Place of publication not identified]$cIEEE Computer Society Press$d2002 215 $a1 online resource (xii, 205 pages) $cillustrations 300 $aBibliographic Level Mode of Issuance: Monograph 311 $a0-7695-1468-5 327 $aPreface -- 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. 330 $aThirty-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. 606 $aComputational Complexity$vCongresses 615 0$aComputational Complexity 676 $a511.3 702 $aIEEE Staff 801 0$bPQKB 906 $aPROCEEDING 912 $a996200685103316 996 $a17th IEEE Annual Conference on Computational Complexity (CCC 2002)$92359233 997 $aUNISA