Parity, circuits, and the polynomial-time hierarchy
From MaRDI portal
Publication:3318683
DOI10.1007/BF01744431zbMath0534.94008DBLPjournals/mst/FurstSS84WikidataQ55967164 ScholiaQ55967164MaRDI QIDQ3318683
Merrick L. Furst, Michael Sipser, James B. Saxe
Publication date: 1984
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (only showing first 100 items - show all)
Narrow Proofs May Be Maximally Long ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ Parameterized Parallel Computing and First-Order Logic ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Neural networks and complexity theory ⋮ The complexity of graph connectivity ⋮ Parallel complexity of iterated morphisms and the arithmetic of small numbers ⋮ Trans-dichotomous algorithms without multiplication — some upper and lower bounds ⋮ On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions ⋮ Linear constraint query languages expressive power and complexity ⋮ Borel complexity and Ramsey largeness of sets of oracles separating complexity classes ⋮ Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic ⋮ A note on uniform circuit lower bounds for the counting hierarchy (extended abstract) ⋮ Unnamed Item ⋮ Substitution Principle and semidirect products ⋮ Communication and information complexity ⋮ Circuit complexity of regular languages ⋮ Iteration on notation and unary functions ⋮ Black-Box and Data-Driven Computation ⋮ A constant-space sequential model of computation for first-order logic ⋮ Circuit complexity of regular languages ⋮ Unnamed Item ⋮ Natural proofs ⋮ An exact characterization of symmetric functions in \(qAC^{0}[2\)] ⋮ The descriptive complexity approach to LOGCFL ⋮ Unprovability of strong complexity lower bounds in bounded arithmetic ⋮ Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms ⋮ NP-hardness of approximating meta-complexity: a cryptographic approach ⋮ Quantum depth in the random oracle model ⋮ Quantum cryptography in Algorithmica ⋮ Unnamed Item ⋮ On the complexity of some problems on groups input as multiplication tables ⋮ The Power of Diversity ⋮ Unnamed Item ⋮ Circuit complexity and the expressive power of generalized first-order formulas ⋮ Fine-grained cryptography revisited ⋮ The non-hardness of approximating circuit size ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ On algorithmic statistics for space-bounded algorithms ⋮ Parity helps to compute majority ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lower bounds for modular counting by circuits with modular gates ⋮ The Power of Programs over Monoids in DA ⋮ Dualities for Constraint Satisfaction Problems ⋮ First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ Bounded-width polynomial-size Boolean formulas compute exactly those functions in AC\(^ 0\) ⋮ The expressive power of voting polynomials ⋮ Random sequence generation by cellular automata ⋮ Unbounded fan-in circuits and associative functions ⋮ ``During cannot be expressed by ``after ⋮ A simple function that requires exponential size read-once branching programs ⋮ The average sensitivity of bounded-depth circuits ⋮ A lower bound for depth-3 circuits with MOD \(m\) gates ⋮ Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Perceptrons, PP, and the polynomial hierarchy ⋮ On ACC ⋮ Representing Boolean functions as polynomials modulo composite numbers ⋮ Circuits constructed with MOD\(_ q\) gates cannot compute ``and in sublinear size ⋮ Lower bounds on the size of bounded depth circuits over a complete basis with logical addition ⋮ One-way functions and circuit complexity ⋮ On the language of primitive words ⋮ Circuits in bounded arithmetic. I ⋮ Limits on the power of concurrent-write parallel machines ⋮ Parallel computation with threshold functions ⋮ Counting quantifiers, successor relations, and logarithmic space ⋮ The complexity of symmetric functions in bounded-depth circuits ⋮ Semigroups and languages of dot-depth two ⋮ Borel separability of the coanalytic Ramsey sets ⋮ Relativized alternation and space-bounded computation ⋮ Collapse of the hierarchy of constant-depth exact quantum circuits ⋮ On the shrinkage exponent for read-once formulae ⋮ A tight relationship between generic oracles and type-2 complexity theory ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ A satisfiability algorithm and average-case hardness for formulas over the full binary basis ⋮ Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) ⋮ With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy ⋮ Simplified lower bounds for propositional proofs ⋮ Dyn-FO: A parallel, dynamic complexity class ⋮ Finitely representable databases ⋮ Predicting nonlinear cellular automata quickly by decomposing them into linear ones ⋮ Algebraic methods and bounded formulas ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ On the relative complexity of some languages in \(NC^ 1\) ⋮ Inverse monoids of dot-depth two ⋮ Linear circuits, two-variable logic and weakly blocked monoids ⋮ Finite semigroup varieties defined by programs ⋮ Queries with arithmetical constraints ⋮ The isomorphism conjecture for constant depth reductions ⋮ Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? ⋮ Lower bounds for constant-depth circuits in the presence of help bits ⋮ Lower bounds for recognizing small cliques on CRCW PRAM's ⋮ Lifting lower bounds for tree-like proofs ⋮ Isomorphism testing of Boolean functions computable by constant-depth circuits
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A 3n-lower bound on the network complexity of Boolean functions
- On counting problems and the polynomial-time hierarchy
- The polynomial-time hierarchy
- A second step toward the polynomial hierarchy
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativization of questions about log space computability
This page was built for publication: Parity, circuits, and the polynomial-time hierarchy
