Pubbl/distr/stampa	[Place of publication not identified], : IEEE Computer Society Press, 2002
Soggetto topico	Engineering & Applied Sciences Computer Science
Formato	Materiale a stampa
Livello bibliografico	Monografia
Lingua di pubblicazione	eng
Record Nr.	UNISA-996200683703316

Pubbl/distr/stampa	[Place of publication not identified], : IEEE Computer Society Press, 2007
ISBN	1-5090-8868-7
Formato	Materiale a stampa
Livello bibliografico	Monografia
Lingua di pubblicazione	eng
Record Nr.	UNISA-996211345703316

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
Soggetto topico	Computational Complexity
Formato	Materiale a stampa
Livello bibliografico	Monografia
Lingua di pubblicazione	eng
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.
Record Nr.	UNISA-996200685103316