Computational Complexity

DOI10.1017/CBO9780511804106zbMath1154.68056OpenAlexW4252948584MaRDI QIDQ5900112

Publication date: 30 June 2008

Full work available at URL: https://doi.org/10.1017/cbo9780511804106

deterministic algorithms probabilistic algorithms analysis of algorithms complexity theory complexity classes

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Cryptography (94A60) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Authentication, digital signatures and secret sharing (94A62)

Related Items

Characterizing time computational complexity classes with polynomial differential equations, One-Way Functions and (Im)perfect Obfuscation, On the Complexity of Closest Pair via Polar-Pair of Point-Sets, Probabilistic Algorithmic Randomness, Super-Perfect Zero-Knowledge Proofs, On Emulating Interactive Proofs with Public Coins, Reducing Testing Affine Spaces to Testing Linearity of Functions, Worst-Case to Average-Case Reductions for Subclasses of P, Constant-Round Interactive Proof Systems for AC0[2 and NC1], Pseudo-mixing Time of Random Walks, On Constructing Expanders for Any Number of Vertices, Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications, Privately puncturing PRFs from lattices: adaptive security and collusion resistant pseudorandomness, Approximate NFA universality and related problems motivated by information theory, Indistinguishable predictions and multi-group fair learning, Succinct interactive oracle proofs: applications and limitations, Interactions of computational complexity theory and mathematics, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, On the degree of univariate polynomials over the integers, Unnamed Item, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Unnamed Item, Membership in Moment Polytopes is in NP and coNP, Implicit computation complexity in higher-order programming languages, Expander-based cryptography meets natural proofs, Two function algebras defining functions in $\mathsf{NC}^k$ Boolean circuits, Complete Problem for Perfect Zero-Knowledge Quantum Proof, Certifying trapdoor permutations, revisited, Time- and space-efficient arguments from groups of unknown order, The Journey from NP to TFNP Hardness, A Hierarchy Theorem for Interactive Proofs of Proximity, $\mathrm{SL}_2$ homomorphic hash functions: worst case to average case reduction and short collision search, Completeness, approximability and exponential time results for counting problems with easy decision version, Computing equilibria: a computational complexity perspective, Quantified Derandomization: How to Find Water in the Ocean, Branching Programs for Tree Evaluation, A counterexample to the chain rule for conditional HILL entropy, Matrix rigidity of random Toeplitz matrices, Enhancements of trapdoor permutations, Improved bounds on the an-complexity of $O(1)$-linear functions, Parameterized complexity classes beyond para-NP, Unpredictability and Computational Irreducibility, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, A new asymptotic notation: Weak Theta, Causes for query answers from databases: datalog abduction, view-updates, and integrity constraints, Some conditionally hard problems on links and 3-manifolds, Machines that perform measurements, Persuasion and dynamic communication, Approximate counting in SMT and value estimation for probabilistic programs, Pseudorandom generators for $\mathrm{CC}^0[p$ and the Fourier spectrum of low-degree polynomials over finite fields], Two Comments on Targeted Canonical Derandomizers, On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions, Unnamed Item, Hardness of embedding simplicial complexes in $\mathbb R^d$, Perfect implementation, On the complexity of restoring corrupted colorings, Inventory rationing and markdown strategy in the presence of lead-time sensitive customers, Optimal measures and Markov transition kernels, Computation as an unbounded process, Keeping logic in the trivium of computer science: a teaching perspective, Towards implementation of a generalized architecture for high-level quantum programming language, Parameterized random complexity, A note on the relation between XOR and selective XOR lemmas, Environmentally friendly composable multi-party computation in the plain model from standard (timed) assumptions, Oblivious transfer from trapdoor permutations in minimal rounds, On the complexity of matroid isomorphism problem, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Introduction to Testing Graph Properties, Book review of: S. Arora and B. Barak, Computational complexity: a modern approach., Almost Every Simply Typed $$\lambda $$-Term Has a Long $$\beta $$-Reduction Sequence, Derandomization in game-theoretic probability, Unnamed Item, Limitations of semidefinite programs for separable states and entangled games, The complexity of debate checking, A polynomial upper bound on Reidemeister moves, Non-interactive proofs of proximity, Challenging epistemology: Interactive proofs and zero knowledge, Matching dependencies: semantics and query answering, An approach to estimating the complexity of probabilistic procedures for the postoptimality analysis of discrete optimization problems, Parallelization of entanglement-resistant multi-prover interactive proofs, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Unnamed Item, Unnamed Item, Parameterized counting of partially injective homomorphisms, Fast switch and spline scheme for accurate inversion of nonlinear functions: the new first choice solution to Kepler's equation, The efficient certification of knottedness and Thurston norm, The computational status of physics, Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP, Using Merging Variables-Based Local Search to Solve Special Variants of MaxSAT Problem, Optimal state amalgamation is NP-hard, Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer, Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More), In a World of P=BPP, Notes on Levin’s Theory of Average-Case Complexity, On Yao’s XOR-Lemma, Short Locally Testable Codes and Proofs, Bravely, Moderately: A Common Theme in Four Recent Works, Basing Non-Interactive Zero-Knowledge on (Enhanced) Trapdoor Permutations: The State of the Art, Average Case Complexity, Revisited, Basic Facts about Expander Graphs, Introduction to Testing Graph Properties, Randomness and Computation, Every Set in P Is Strongly Testable Under a Suitable Encoding, Relations and equivalences between circuit lower bounds and karp-lipton theorems, On the Complexity of Matroid Isomorphism Problems, Efficient adaptively-secure IB-KEMs and VRFs via near-collision resistance, Hardness magnification near state-of-the-art lower bounds, On Adaptively Secure Multiparty Computation with a Short CRS, Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly, On Statistically Secure Obfuscation with Approximate Correctness, Mass problems associated with effectively closed sets, $H$-colouring $P_t$-free graphs in subexponential time, Constant-Round Interactive Proofs for Delegating Computation, Proving that $\mathrm{prBPP}=\mathrm{prP}$ is as hard as proving that ``almost NP is not contained in P/poly, Advice hierarchies among finite automata, Unnamed Item, On the Complexity of Closest Pair via Polar-Pair of Point-Sets, Complexity analysis of hypergeometric orthogonal polynomials, Packing Problems in Space Solved by CPLEX: An Experimental Analysis, On the average-case complexity of parameterized clique, Pseudorandom Functions: Three Decades Later, Approximate NFA universality motivated by information theory, Lower bounds and hardness magnification for sublinear-time shrinking cellular automata, ``Selfish algorithm for reducing the computational cost of the network survivability analysis