Computational Complexity: A Modern Approach

By Sanjeev Arora, Boaz Barak. 2009

3,126 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Scalable agent alignment via reward modeling: a research direction (2018, background): “We could also understand this term analogous to more formal notions of difﬁculty in computational complexity theory (see e.g. Arora & Barak, 2009).”
Complexity and entanglement for thermofield double states (2018, methodology): “hole interior. It has been suggested that this quantity is the quantum computational complexity of the boundary state [10]. The concept of circuit complexity is rooted in theoretical computer science [15,16]. In classical computing, one is interested in implementing a given algorithm, i.e., a functi”
Jerusalem Lectures on Black Holes and Quantum Information (2014, background): “It is not a priori clear that such functions should exist, but they are widely expected to; indeed almost all of modern cryptography is based on their assumed existence [158].”
Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems (2019, background): “Unless the topology of the graph has some special structure, such as two-dimensional lattices, this problem is known to be nondeterministic polynomial time (NP)–hard (2, 3).”
Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation (2016, background): “ familiarity with Computational Complexity, especially the theory of interactive proofs and MerlinArthur games as initiated by Goldwasser-Micali-Rackoff [GMR85] and Babai [Bab85] (see Arora and Barak [AB09], Chapter 8). All of the interactive proofs (also known as “protocols”) of this paper will use”
Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search (2018, background): “Approximation algorithms provide theoretical guarantees, but their scalability may be limited and algorithms with satisfactory bounds may not exist [3, 38].”
Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective (2023, background): “For a rigorous definition, we refer readers to Arora & Barak [2].”
Model complexity of deep learning: a survey (2021, background): “In addition to the above studies on effective complexity, piecewise linear neural networks or the piecewise linear property can also help the exploration of expressive capacity (see Section 2, [4, 36, 64, 70, 92]).”
Resolving the conflict between generality and plausibility in verified computation (2013, background): “Since degree-2 constraint satisfaction is an NP-complete problem [5], the PCP that we present here generalizes to checking NP relations.”
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy (2010, methodology): “ the ǫ-independence of the classes in deﬁnition 3 above. The basic bounded error classes BPP and BQP are well known to be independent of the error tolerance 0 <ǫ<1 2. Indeed the standard method [7, 8] for reducing ǫis to consider the majority vote answer of multiple runs of the circuit. Simila”
Understanding Deep Neural Networks with Rectified Linear Units (2016, background): “Our investigation of the function space represented by ReLU DNNs also takes inspiration from the classical theory of circuit complexity; we refer the reader to [1, 3, 5, 13, 17, 27, 30, 37] for various surveys of this deep and fascinating field.”
What the Near Future of Artificial Intelligence Could Be (2019, background): “The degrees of complexity of a problem are well known and extensively studied in computational theory (Arora and Barak 2009; Sipser 2012).”