Perspectives in Computational Complexity: The Somenath Biswas Anniversary VolumeManindra Agrawal, Vikraman Arvind Springer, 16 ביולי 2014 - 202 עמודים This book brings together contributions by leading researchers in computational complexity theory written in honor of Somenath Biswas on the occasion of his sixtieth birthday. They discuss current trends and exciting developments in this flourishing area of research and offer fresh perspectives on various aspects of complexity theory. The topics covered include arithmetic circuit complexity, lower bounds and polynomial identity testing, the isomorphism conjecture, space-bounded computation, graph isomorphism, resolution and proof complexity, entropy and randomness. Several chapters have a tutorial flavor. The aim is to make recent research in these topics accessible to graduate students and senior undergraduates in computer science and mathematics. It can also be useful as a resource for teaching advanced level courses in computational complexity. |
תוכן
| 1 | |
2 Investigations Concerning the Structure of Complete Sets | 23 |
3 Space Complexity of the Directed Reachability Problem over SurfaceEmbedded Graphs | 36 |
4 Algebraic Complexity Classes | 51 |
5 A Selection of Lower Bounds for Arithmetic Circuits | 76 |
6 Explicit Tensors | 117 |
7 Progress on Polynomial Identity TestingII | 131 |
8 Malod and the Pascaline | 147 |
9 A Tutorial on Time and Space Bounds in TreeLike Resolution | 158 |
10 An EntropyBased Proof for the Moore Bound for Irregular Graphs | 173 |
11 Permutation Groups and the Graph Isomorphism Problem | 183 |
מהדורות אחרות - הצג הכל
מונחים וביטויים נפוצים
Allender arithmetic circuits Arvind automorphism boolean Bürgisser circuit computing clauses coefficient-function complexity classes complexity theory Computational Complexity Computer Science computes a polynomial constant coset defined Delayer denote directed graph edge element explicit exponential function G-orbits gates graph G graph isomorphism problem group G Hence Hoory input integer language Lemma Let G linear polynomials logspace lower bound Malod matrix monomials multilinear multilinear formula multiplication node nondeterministic nonzero NP-complete NP-complete sets NP-creative open problem P/poly partial derivatives partition Pascaline path Perm permutation group planar planar graphs polynomial computed polynomial family polynomial ƒ polynomial-time algorithm polynomially bounded primitive permutation group proof prove PSPACE random rank rank-one tensors reachability problem resolution refutation result Saptharishi sequence skew circuits Somenath Biswas space STOC strong generating set subgroup Theorem tree-like resolution Turing machine undirected upper bound V₁ Valiant variables vertex vertices