Overview

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.

Full Product Details

Author:   Manindra Agrawal ,  Vikraman Arvind
Publisher:   Birkhauser Verlag AG
Imprint:   Birkhauser Verlag AG
Edition:   Softcover reprint of the original 1st ed. 2014
Volume:   26
Dimensions:   Width: 15.50cm , Height: 1.10cm , Length: 23.50cm
Weight:   3.285kg
ISBN:  

9783319350585

ISBN 10:   3319350587
Pages:   202
Publication Date:   23 August 2016
Audience:   Professional and scholarly ,  Professional & Vocational
Format:   Paperback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.

Table of Contents

Preface.- 1. Complexity Theory Basics: NP and NL (Vikraman Arvind).- 2. Investigations Concerning the Structure of Complete Sets (Eric Allender).- 3. Space Complexity of the Directed Reachability Problem Over Surface-embedded Graphs (N.V. Vinodchandran).- 4. Algebraic Complexity Classes (Meena Mahajan).- 5. A Selection of Lower Bound Results for Arithmetic Circuits (Neeraj Kayal and Ramprasad Saptharishi).- 6. Explicit Tensors (Markus Bläser).- 7. Progress on Polynomial Identity Testing (Nitin Saxena).- 8. Malod and the Pascaline (Bruno Poizat).- 9. A Tutorial in Time and Space Bounds for Tree-like Resolution (Jacobo Torán).- 10. An Entropy Based Proof for the Moore Bound for Irregular Graphs (S. Ajesh Babu and Jaikumar Radharishnan).- 11. Permutation Groups and the Graph Isomorphism Problem (Sumanta Ghosh and Piyush P. Kurur).

Reviews

Author Information

Manindra Agrawal is Professor at the Department of Computer Science and Engineering of the Indian Institute of Technology in Kanpur, India. Vikraman Arvind is Professor at the Institute of Mathematical Sciences of the CIT Campus in Chennai, India.

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions