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)
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
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 ⋮ Relations among parallel and sequential computation models ⋮ Constructive separations and their consequences ⋮ Circuit complexity before the dawn of the new millennium ⋮ Fine-grained polynomial functional encryption ⋮ Fine-grained cryptography revisited ⋮ The non-hardness of approximating circuit size ⋮ Complexity barriers as independence ⋮ Theoretical computer science: computational complexity ⋮ Parameterized complexity classes defined by threshold circuits and their connection with sorting networks ⋮ Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024 ⋮ Computationally hard problems for logic programs under answer set semantics ⋮ The regular languages of first-order logic with one alternation ⋮ 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 ⋮ Affine projections of symmetric polynomials. ⋮ On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ \(n^{{\Omega{}}(\log{} n)}\) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom ⋮ The correlation between parity and quadratic polynomials mod \(3\) ⋮ Specification and Verification of Multi-Agent Systems ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) ⋮ On Distinguishing NC $$^1$$ and NL ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ Approximating Boolean Functions with Depth-2 Circuits ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ A logical characterization of constant-depth circuits over the reals ⋮ A note on some languages in uniform \(ACC^ 0\) ⋮ Separating the low and high hierarchies by oracles ⋮ On uniformity within \(NC^ 1\) ⋮ Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ Formulas versus Circuits for Small Distance Connectivity ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Top-down lower bounds for depth-three circuits ⋮ Evaluating spectral norms for constant depth circuits with symmetric gates ⋮ Some results on uniform arithmetic circuit complexity ⋮ General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results ⋮ The average sensitivity of bounded-depth formulas ⋮ Designing checkers for programs that run in parallel ⋮ Parallel complexity of algebraic operations ⋮ Structural properties for feasibly computable classes of type two ⋮ Uniform proofs of ACC representations ⋮ A note on separating the relativized polynomial time hierarchy by immune sets ⋮ Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\) ⋮ Skew circuits of small width ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ On deterministic approximation of DNF ⋮ Bounds in ontology-based data access via circuit complexity ⋮ Extensions of an idea of McNaughton ⋮ A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems] ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ A Circuit Complexity Approach to Transductions ⋮ Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$
Uses Software
This page was built for publication: Parity, circuits, and the polynomial-time hierarchy
