The Experts below are selected from a list of 28227 Experts worldwide ranked by ideXlab platform

Eric Allender - One of the best experts on this subject based on the ideXlab platform.

  • the pervasive reach of resource bounded kolmogorov Complexity in Computational Complexity Theory
    Journal of Computer and System Sciences, 2011
    Co-Authors: Eric Allender, Michal Koucký, Detlef Ronneburger
    Abstract:

    We continue an investigation into resource-bounded Kolmogorov Complexity (Allender et al., 2006 [4]), which highlights the close connections between circuit Complexity and Levin's time-bounded Kolmogorov Complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov Complexity. The Kolmogorov measures that have been introduced have many advantages over other approaches to defining resource-bounded Kolmogorov Complexity (such as much greater independence from the underlying choice of universal machine that is used to define the measure) (Allender et al., 2006 [4]). Here, we study the properties of other measures that arise naturally in this framework. The motivation for introducing yet more notions of resource-bounded Kolmogorov Complexity are two-fold:*to demonstrate that other Complexity measures such as branching-program size and formula size can also be discussed in terms of Kolmogorov Complexity, and *to demonstrate that notions such as nondeterministic Kolmogorov Complexity and distinguishing Complexity (Buhrman et al., 2002 [15]) also fit well into this framework. The main theorems that we provide using this new approach to resource-bounded Kolmogorov Complexity are:*A complete set (R"K"N"t) for NEXP/poly defined in terms of strings of high Kolmogorov Complexity. *A lower bound, showing that R"K"N"t is not in [email protected]?coNP. *New conditions equivalent to the conditions ''[email protected]?nonuniform NC^1'' and ''[email protected]?L/poly''. *Theorems showing that ''distinguishing Complexity'' is closely connected to both FewEXP and to EXP. *Hardness results for the problems of approximating formula size and branching program size.

  • the pervasive reach of resource bounded kolmogorov Complexity in Computational Complexity Theory
    Journal of Computer and System Sciences, 2011
    Co-Authors: Eric Allender, Michal Koucký, Detlef Ronneburger
    Abstract:

    We continue an investigation into resource-bounded Kolmogorov Complexity (Allender et al., 2006 [4]), which highlights the close connections between circuit Complexity and Levin's time-bounded Kolmogorov Complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov Complexity. The Kolmogorov measures that have been introduced have many advantages over other approaches to defining resource-bounded Kolmogorov Complexity (such as much greater independence from the underlying choice of universal machine that is used to define the measure) (Allender et al., 2006 [4]). Here, we study the properties of other measures that arise naturally in this framework. The motivation for introducing yet more notions of resource-bounded Kolmogorov Complexity are two-fold:*to demonstrate that other Complexity measures such as branching-program size and formula size can also be discussed in terms of Kolmogorov Complexity, and *to demonstrate that notions such as nondeterministic Kolmogorov Complexity and distinguishing Complexity (Buhrman et al., 2002 [15]) also fit well into this framework. The main theorems that we provide using this new approach to resource-bounded Kolmogorov Complexity are:*A complete set (R"K"N"t) for NEXP/poly defined in terms of strings of high Kolmogorov Complexity. *A lower bound, showing that R"K"N"t is not in [email protected]?coNP. *New conditions equivalent to the conditions ''[email protected]?nonuniform NC^1'' and ''[email protected]?L/poly''. *Theorems showing that ''distinguishing Complexity'' is closely connected to both FewEXP and to EXP. *Hardness results for the problems of approximating formula size and branching program size.

  • Computational Complexity Theory
    Wiley Encyclopedia of Computer Science and Engineering, 2009
    Co-Authors: Eric Allender
    Abstract:

    This article is a brief overview of the field of Computational Complexity Theory. Keywords: Complexity Theory; reducibility; Complexity classes; complete sets; intractability; P; NP; PSPACE; EXP

  • Wiley Encyclopedia of Computer Science and Engineering - Computational Complexity Theory
    Wiley Encyclopedia of Computer Science and Engineering, 2009
    Co-Authors: Eric Allender
    Abstract:

    This article is a brief overview of the field of Computational Complexity Theory. Keywords: Complexity Theory; reducibility; Complexity classes; complete sets; intractability; P; NP; PSPACE; EXP

  • The future of Computational Complexity Theory: part II
    ACM SIGACT News, 1996
    Co-Authors: Eric Allender, Joan Feigenbaum, Judy Goldsmith, Toniann Pitassi, Steven Rudich
    Abstract:

    This is the final part of a 2-part column on the future of Computational Complexity Theory. The grounds rules were that the contributors had no restrictions (except a 1-page limit). For readers interested in more formal reports, in addition to the two URLs mentioned in the previous issue (ftp://ftp.cs.washington.edu/tr/1996/O3/UW-CSE-96-O3-O3.PS.Z and http://Theory.lcs.mit.edu/-oded/toc-sp.html) I would also point to the recent "Strategic Directions" report (http://geisel.csl.uiuc.edu/-loui/complete.html).Coming during the next few issues: the search for the perfect Theory journal; Thomas Jefferson exposed as a theoretical computer scientist; and Mitsunori Ogihara's survey of DNA-based computation. (The "Lance Fortnow in a clown suit" article promised in the previous column actually ran stand-alone last issue due to scheduling; it probably is still available at a library near you!) Finally, some recent work by Edith Hemaspaandra, Harald Hempel, and myself, and of Buhrman and Fortnow, partially resolves one of the open questions from Complexity Theory Column 11.

Avi Wigderson - One of the best experts on this subject based on the ideXlab platform.

  • Interactions of Computational Complexity Theory and Mathematics
    arXiv: Computational Complexity, 2017
    Co-Authors: Avi Wigderson
    Abstract:

    $ $[This paper is a (self contained) chapter in a new book, Mathematics and Computation, whose draft is available on my homepage at this https URL ]. We survey some concrete interaction areas between Computational Complexity Theory and different fields of mathematics. We hope to demonstrate here that hardly any area of modern mathematics is untouched by the Computational connection (which in some cases is completely natural and in others may seem quite surprising). In my view, the breadth, depth, beauty and novelty of these connections is inspiring, and speaks to a great potential of future interactions (which indeed, are quickly expanding). We aim for variety. We give short, simple descriptions (without proofs or much technical detail) of ideas, motivations, results and connections; this will hopefully entice the reader to dig deeper. Each vignette focuses only on a single topic within a large mathematical filed. We cover the following: $\bullet$ Number Theory: Primality testing $\bullet$ Combinatorial Geometry: Point-line incidences $\bullet$ Operator Theory: The Kadison-Singer problem $\bullet$ Metric Geometry: Distortion of embeddings $\bullet$ Group Theory: Generation and random generation $\bullet$ Statistical Physics: Monte-Carlo Markov chains $\bullet$ Analysis and Probability: Noise stability $\bullet$ Lattice Theory: Short vectors $\bullet$ Invariant Theory: Actions on matrix tuples

  • Computational Complexity Theory - Computational Complexity Theory
    IAS Park City Mathematics Series, 2004
    Co-Authors: Steven Rudich, Avi Wigderson
    Abstract:

    Week One: Complexity Theory: From Godel to Feynman Complexity Theory: From Godel to Feynman History and basic concepts Resources, reductions and P vs. NP Probabilistic and quantum computation Complexity classes Space Complexity and circuit Complexity Oracles and the polynomial time hierarchy Circuit lower bounds "Natural" proofs of lower bounds Bibliography Average case Complexity Average case Complexity Bibliography Exploring Complexity through reductions Introduction PCP theorem and hardness of computing approximate solutions Which problems have strongly exponential Complexity? Toda's theorem: $PH\subseteq P^{\ No. P}$ Bibliography Quantum computation Introduction Bipartite quantum systems Quantum circuits and Shor's factoring algorithm Bibliography Lower bounds: Circuit and communication Complexity Communication Complexity Lower bounds for probabilistic communication Complexity Communication Complexity and circuit depth Lower bound for directed $st$-connectivity Lower bound for $FORK$ (continued) Bibliography Proof Complexity An introduction to proof Complexity Lower bounds in proof Complexity Automatizability and interpolation The restriction method Other research and open problems Bibliography Randomness in computation Pseudorandomness Preface Computational indistinguishability Pseudorandom generators Pseudorandom functions and concluding remarks Appendix Bibliography Pseudorandomness-Part II Introduction Deterministic simulation of randomized algorithms The Nisan-Wigderson generator Analysis of the Nisan-Wigderson generator Randomness extractors Bibliography Probabilistic proof systems-Part I Interactive proofs Zero-knowledge proofs Suggestions for further reading Bibliography Probabilistically checkable proofs Introduction to PCPs NP-hardness of PCS A couple of digressions Proof composition and the PCP theorem Bibliography.

  • Computational Complexity Theory
    2004
    Co-Authors: Steven Rudich, Avi Wigderson
    Abstract:

    Week One: Complexity Theory: From Godel to Feynman Complexity Theory: From Godel to Feynman History and basic concepts Resources, reductions and P vs. NP Probabilistic and quantum computation Complexity classes Space Complexity and circuit Complexity Oracles and the polynomial time hierarchy Circuit lower bounds "Natural" proofs of lower bounds Bibliography Average case Complexity Average case Complexity Bibliography Exploring Complexity through reductions Introduction PCP theorem and hardness of computing approximate solutions Which problems have strongly exponential Complexity? Toda's theorem: $PH\subseteq P^{\ No. P}$ Bibliography Quantum computation Introduction Bipartite quantum systems Quantum circuits and Shor's factoring algorithm Bibliography Lower bounds: Circuit and communication Complexity Communication Complexity Lower bounds for probabilistic communication Complexity Communication Complexity and circuit depth Lower bound for directed $st$-connectivity Lower bound for $FORK$ (continued) Bibliography Proof Complexity An introduction to proof Complexity Lower bounds in proof Complexity Automatizability and interpolation The restriction method Other research and open problems Bibliography Randomness in computation Pseudorandomness Preface Computational indistinguishability Pseudorandom generators Pseudorandom functions and concluding remarks Appendix Bibliography Pseudorandomness-Part II Introduction Deterministic simulation of randomized algorithms The Nisan-Wigderson generator Analysis of the Nisan-Wigderson generator Randomness extractors Bibliography Probabilistic proof systems-Part I Interactive proofs Zero-knowledge proofs Suggestions for further reading Bibliography Probabilistically checkable proofs Introduction to PCPs NP-hardness of PCS A couple of digressions Proof composition and the PCP theorem Bibliography.

  • The future of Computational Complexity Theory: part I
    ACM SIGACT News, 1996
    Co-Authors: Christos H. Papadimitriou, Avi Wigderson, Oded Goldreich, Alexander A. Razborov, Michael Sipser
    Abstract:

    As you probably already know, there is an active discussion going on---in forums ranging from lunch-table conversations to workshops on "strategic directions" to formal reports---regarding the future of theoretical computer science. Since your Complexity columnist does not know The Answer, I've asked a number of people to contribute their comments on the narrower issue of the future of Complexity Theory. The only ground rule was a loose 1-page limit; each contributor could choose what aspect(s) of the future to address, and the way in which to address them. The first installment of contributions appears in this issue, and one or two more installments will appear among the next few issues.Also coming during the next few issues: the search for the perfect Theory journal, and (for the sharp-eyed) Lance Fortnow dons a clown suit. Finally, let me mention that work of Russell Impagliazzo resolves one of the open questions from Complexity Theory Column 11.

  • Kurt Gödel and the Foundations of Mathematics: The Gödel Phenomenon in Mathematics: A Modern View
    Kurt Gödel and the Foundations of Mathematics, 1
    Co-Authors: Avi Wigderson
    Abstract:

    What are the limits of mathematical knowledge? The purpose of this chapter is to introduce the main concepts from Computational Complexity Theory that are relevant to algorithmic accessibility of mathematical understanding. In particular, I’ll discuss the P versus NP problem, its possible impact on research in mathematics, and how interested Godel himself was in this Computational viewpoint. Much of the technical material will be necessarily sketchy. The interested reader is referred to the standard texts on Computational Complexity Theory, primarily [5, 25, 43, 61].

Heribert Vollmer - One of the best experts on this subject based on the ideXlab platform.

Silvia N. Santalla - One of the best experts on this subject based on the ideXlab platform.

  • Building an adiabatic quantum computer simulation in the classroom
    American Journal of Physics, 2018
    Co-Authors: Javier Rodríguez-laguna, Silvia N. Santalla
    Abstract:

    We present a didactic introduction to adiabatic quantum computation (AQC) via the explicit construction of a classical simulator of quantum computers. This constitutes a suitable route to introduce several important concepts for advanced undergraduates in physics: quantum many-body systems, quantum phase transitions, disordered systems, spin-glasses, and Computational Complexity Theory.

  • Physical consequences of P≠NP and the density matrix renormalization group annealing conjecture
    Journal of Statistical Mechanics: Theory and Experiment, 2014
    Co-Authors: Javier Rodríguez-laguna, Silvia N. Santalla
    Abstract:

    Computational Complexity Theory contains a corpus of theorems and conjectures regarding the time a Turing machine will need to solve certain types of problems as a function of the input size. Nature need not be a Turing machine and, thus, these theorems do not apply directly to it. But classical simulations of physical processes are programs running on Turing machines and, as such, are subject to them. In this work, Computational Complexity Theory is applied to classical simulations of systems performing an adiabatic quantum computation (AQC), based on an annealed extension of the density matrix renormalization group (DMRG). We conjecture that the Computational time required for those classical simulations is controlled solely by the maximal entanglement found during the process. Thus, lower bounds on the growth of entanglement with the system size can be provided. In some cases, quantum phase transitions can be predicted to take place in certain inhomogeneous systems. Concretely, physical conclusions are drawn from the assumption that the Complexity classes P and NP differ. As a by-product, an alternative measure of entanglement is proposed which, via Chebyshev's inequality, allows us to establish strict bounds on the required Computational time.

Susan Coppersmith - One of the best experts on this subject based on the ideXlab platform.

  • Renormalization group approach to satisfiability
    Europhysics Letters (EPL), 2007
    Co-Authors: Susan Coppersmith
    Abstract:

    Satisfiability is a classic problem in Computational Complexity Theory, in which one wishes to determine whether an assignment of values to a collection of Boolean variables exists in which all of a collection of clauses composed of logical ORs of these variables is true. Here, a renormalization group transformation is constructed and used to relate the properties of satisfiability problems with different numbers of variables in each clause. The transformation yields new insight into phase transitions delineating "hard" and "easy" satisfiability problems.