Parity, circuits, and the polynomial-time hierarchy

Related Items

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 ⋮ Lower bounds against weakly-uniform threshold circuits ⋮ Some notes on threshold circuits, and multiplication in depth 4 ⋮ Rudimentary reductions revisited ⋮ On the computational complexity of the Riemann mapping ⋮ An arithmetic model of computation equivalent to threshold circuits ⋮ Learning in parallel ⋮ On adaptive DLOGTIME and POLYLOGTIME reductions ⋮ On input read-modes of alternating Turing machines ⋮ A note on the power of majority gates and modular gates ⋮ The graph of multiplication is equivalent to counting ⋮ A simple lower bound for monotone clique using a communication game ⋮ The invariant problem for binary string structures and the parallel complexity theory of queries ⋮ Regular languages in $NC$ ⋮ Formulas, regular languages and Boolean circuits ⋮ The complexity of computing symmetric functions using threshold circuits ⋮ Probabilistic polynomials, AC$^ 0$ functions and the polynomial-time hierarchy ⋮ Local restrictions from the Furst-Saxe-Sipser paper ⋮ The communication complexity of addition ⋮ $NC^ 1$: The automata-theoretic viewpoint ⋮ On the power of small-depth threshold circuits ⋮ The quantifier structure of sentences that characterize nondeterministic time complexity ⋮ Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets ⋮ Exponential lower bounds for the pigeonhole principle ⋮ On the correlation between parity and modular polynomials ⋮ Ehrenfeucht-Fraïssé games in finite set theory ⋮ Extensions to Barrington's M-program model ⋮ On read-once threshold formulae and their randomized decision tree complexity ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ The intractability of computing the Hamming distance ⋮ First-order logics: some characterizations and closure properties ⋮ Mean-payoff games and propositional proofs ⋮ Universal algebra and hardness results for constraint satisfaction problems ⋮ On the power of interaction ⋮ A constant-space sequential model of computation for first-order logic ⋮ A lower bound for perceptrons and an oracle separation of the $PP^{PH}$ hierarchy ⋮ Attribute-efficient learning in query and mistake-bound models ⋮ Threshold circuits of small majority-depth ⋮ Relating polynomial time to constant depth ⋮ Reductions in circuit complexity: An isomorphism theorem and a gap theorem ⋮ Parallelizing quantum circuits ⋮ Circuits and expressions with nonassociative gates ⋮ Resolution of Hartmanis' conjecture for NL-hard sparse sets ⋮ Programs over semigroups of dot-depth one ⋮ Non-uniform automata over groups ⋮ Large parallel machines can be extremely slow for small problems ⋮ Constant-time Hough transform on the processor arrays with reconfigurable bus systems ⋮ On the complexity of counting in the polynomial hierarchy ⋮ On the computational complexity of reachability in 2D binary images and some basic problems of 2D digital topology ⋮ Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC ⋮ A slight sharpening of LMN ⋮ The parallel complexity of two problems on concurrency ⋮ The complexity of computing maximal word functions ⋮ 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}$$ ⋮ Support set selection for abductive and default reasoning ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ Some lower bounds in parameterized $\mathrm{AC}^{0}$ ⋮ Indistinguishability and First-Order Logic ⋮ How Do Read-Once Formulae Shrink? ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Circuit complexity of linear functions: gate elimination and feeble security ⋮ Classifying the computational complexity of problems ⋮ Unnamed Item ⋮ Some $0/1$ polytopes need exponential size extended formulations ⋮ Towards optimal packed string matching ⋮ On the correlation of symmetric functions ⋮ Exponential lower bounds of complexity and step-by-step simulation circuits ⋮ Unnamed Item ⋮ A Characterisation of NL Using Membrane Systems without Charges and Dissolution ⋮ y= 2xVS.y= 3x ⋮ A characterization of definability of second-order generalized quantifiers with applications to non-definability ⋮ UP and the low and high hierarchies: A relativized separation ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ A second step toward the strong polynomial-time hierarchy ⋮ Bounded Independence Plus Noise Fools Products ⋮ First-order rewritability of ontology-mediated queries in linear temporal logic ⋮ Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates ⋮ Typed Monoids – An Eilenberg-Like Theorem for Non Regular Languages ⋮ COLLAPSING THE HIERARCHY OF PARALLEL COMPUTATIONAL MODELS ⋮ Using the renormalization group to classify Boolean functions ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Fourier concentration from shrinkage ⋮ String shuffle: circuits and graphs ⋮ First-order expressibility of languages with neutral letters or: The Crane Beach conjecture ⋮ The robustness of LWPP and WPP, with an application to graph reconstruction ⋮ The complexity of ODD_n^A ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Cryptographic hardness for learning intersections of halfspaces ⋮ Definability of Geometric Properties in Algebraically Closed Fields ⋮ Adiabatic graph-state quantum computation ⋮ Investigations Concerning the Structure of Complete Sets ⋮ On the correlation of symmetric functions ⋮ Ehrenfeucht-Fraïssé Games on Random Structures ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Fine-Grained Cryptography ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Enumerative counting is hard ⋮ A new theorem in threshold logic and its application to multioperand binary adders ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ A new proof of Ajtai's completeness theorem for nonstandard finite structures ⋮ Witnessing functions in bounded arithmetic and search problems ⋮ Tally NP sets and easy census functions. ⋮ Counting modulo quantifiers on finite structures ⋮ Languages defined with modular counting quantifiers ⋮ Circuit and decision tree complexity of some number theoretic problems ⋮ Pseudorandom Functions: Three Decades Later ⋮ Which problems have strongly exponential complexity? ⋮ Mining circuit lower bound proofs for meta-algorithms ⋮ Relativized worlds with an infinite hierarchy ⋮ Upper bound for torus polynomials ⋮ Hardness and optimality in QBF proof systems modulo NP ⋮ 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 ⋮ 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

Uses Software

PAL-11A

Cites Work