21st Annual IEEE Conference on Computational Complexity (CCC 2006): 16-20 July 2006/Prague, Czech Republic

• Record Nr.: UNINA9910145611703321
• Pubbl/distr/stampa: [Place of publication not identified], : IEEE Computer Society Press, 2006
• ISBN: 9781509098248; 1509098240
• Descrizione fisica: 1 online resource
• Disciplina: 511.3
• Soggetti: Computational complexity; Logic programming
• Lingua di pubblicazione: Inglese
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di contenuto: Proceedings. Twenty-First Annual IEEE Conference on Computational Complexity -- 21st Annual IEEE Conference on Computational Complexity - Title -- 21st Annual IEEE Conference on Computational Complexity - Copyright -- 21st Annual IEEE Conference on Computational Complexity - TOC -- Preface -- Committees -- Reviewers -- Awards -- Godel and Computations -- Polynomial identity testing for depth 3 circuits -- Every Linear Threshold Function has a Low-Weight Approximator -- Constructions of low-degree and error-correcting /spl epsi/-biased generators -- How to Get More Mileage from Randomness Extractors -- Exposure-resilient extractors -- Making hard problems harder.
• Sommario/riassunto: This annual conference covers all areas of computational complexity theory and encompasses results from other areas of computer science and mathematics motivated by topics in complexity theory. The 30 papers in CCC 2006 focuses on computational complexity while addressing topics such as complexity classes, algebraic complexity, proof complexity, interactive proof systems, circuits and other concrete computational models. It also examines subjects in Kolmogorov complexity, average case complexity reducibility, communication complexity, complexity and logic, nonapproximability, cryptographic complexity, complexity and learning, quantum computation, and ; derandomization.