Nonuniform ACC Circuit Lower Bounds (Q3189637)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Nonuniform ACC Circuit Lower Bounds	scientific article

Statements

scholarly article

0 references

Nonuniform ACC Circuit Lower Bounds (English)

0 references

Journal of the ACM

0 references

publication date

12 September 2014

0 references

zbMATH Keywords

ACC

0 references

circuit complexity

0 references

NEXP

0 references

lower bounds

0 references

satisfiability

0 references

R. Ryan Williams

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1145/2559903

0 references

0 references

On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits

0 references

0 references

0 references

The monotone circuit complexity of Boolean functions

0 references

Computational Complexity

0 references

\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs

0 references

Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

0 references

Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)

0 references

Superlinear lower bounds for bounded-width branching programs

0 references

Non-uniform automata over groups

0 references

0 references

0 references

Set Partitioning via Inclusion-Exclusion

0 references

0 references

The Complexity of Satisfiability of Small Depth Circuits

0 references

A note on a theorem of Barrington, Straubing and Thérien

0 references

Linear Systems over Composite Moduli

0 references

Short propositional formulas represent nondeterministic computations

0 references

Rapid Multiplication of Rectangular Matrices

0 references

Rectangular matrix multiplication revisited

0 references

Time-space lower bounds for satisfiability

0 references

Parity, circuits, and the polynomial-time hierarchy

0 references

A lower bound for depth-3 circuits with MOD \(m\) gates

0 references

Lower Bounds for (MOD<i><sub>p</sub></i> - MOD<i><sub>m</sub></i>) Circuits

0 references

0 references

Constant width planar computation characterizes ACC\(^{0}\)

0 references

Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms

0 references

Fast rectangular matrix multiplication and applications

0 references

In search of an easy witness: Exponential time vs. probabilistic polynomial time.

0 references

0 references

Derandomizing polynomial identity tests means proving circuit lower bounds

0 references

Circuit-size lower bounds and non-reducibility to sparse sets

0 references

A circuit-based proof of Toda's theorem

0 references

Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses

0 references

On the computational power of depth-2 circuits with threshold and modulo gates

0 references

Explicit lower bound of <i>4.5n - o(n)</i> for boolena circuits

0 references

0 references

Hardness vs randomness

0 references

How to multiply matrices faster

0 references

A note on succinct representations of graphs

0 references

On alternation. II. A graph theoretic approach to determinism versus nondeterminism

0 references

0 references

0 references

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

0 references

On O(Tlog T) reduction from RAM computations to satisfiability

0 references

On uniformity and circuit lower bounds

0 references

Satisfiability Is Quasilinear Complete in NQL

0 references

An algorithm for the satisfiability problem of formulas in conjunctive normal form

0 references

Separating Nondeterministic Time Complexity Classes

0 references

A satisfiability algorithm and average-case hardness for formulas over the full binary basis

0 references

PP is as Hard as the Polynomial-Time Hierarchy

0 references

Time-space tradeoffs for SAT on nonuniform machines

0 references

NP is as easy as detecting unique solutions

0 references

NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth

0 references

Improving Exhaustive Search Implies Superpolynomial Lower Bounds

0 references

Exponential size lower bounds for some depth three circuits

0 references

Identifiers

zbMATH Open document ID

0 references

10.1145/2559903

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:3189637

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q3189637&oldid=35411499"