Author
|
Conference
|
Journal
|
Organization
|
Year
|
DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all domains
Limit my searches in the following domains
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(6)
Circuit Complexity
Complexity Theory
Computer Model
Integrated Circuit
Logic Gate
Lower Bound
Subscribe
Academic
Publications
Non-uniform ACC Circuit Lower Bounds
Edit
Non-uniform ACC Circuit Lower Bounds
(
Citations: 6
)
BibTex
|
RIS
|
RefWorks
Download
Ryan Williams
Conference:
Annual IEEE Conference on Computational Complexity - CCC
, pp. 115-125, 2011
DOI:
10.1109/CCC.2011.36
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
Citation Context
(4)
...recent breakthrough result of Williams [
3
] who showed that non-deterministic exponential time does not have efficient ACC 0 circuits...
Arkadev Chattopadhyay
,
et al.
Linear Systems over Finite Abelian Groups
...A few months ago, Williams [
17
] succeeded in carrying out the program by proving an ingenious lower bound for NEXP against non-uniform constant-depth ACC circuits of sub-exponential size (For every fixed depth d, he also provided an exponential-size lower bound), thereby solving a notorious long-standing open problem...
...For more background and history on circuit lower bounds, we refer the readers to [
17
] which elaborates on this history in detail...
...In [
17
], Williams gave an algorithm for solving the satisfiability problem of SYM + circuits of size s over n variables in time O((2 n +s)n O(1) ). Combining it with Corollary 1, the following theorem is immediate...
...Note 1. In [
17
], there are about n δ many input variables set in a single copy...
...In this section, we present our main lower bound result via the framework invented by Williams [
17
]...
...to note that, because of Theorem 4, it is possible to state a slight variant of Lemma 3.1 of [
17
]...
...The following theorem is a variant of Theorem 5.2 in [
17
]...
...the work of Williams [
17
], our algorithm for deciding the satisfiability of the succinctly represented 3-CNF instance Cx proceeds as the following steps...
...In the recent work by Fortnow and Santhanam [9], they defined notions of robust simulations and significant separations, and showed that the theorem of Williams [
17
] can be strengthened with respect to significant separations...
Fengming Wang
.
NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of
...These newer results include hierarchy theorems [Bar02, FS04, vMP06], time-space tradeoffs [For00, FLvMV05], and circuit lower bounds [BFT98, Vin05, San07, Wil10a,
Wil10b
]...
...Our most technically involved result is that the recent breakthrough lower bound of Williams [Wil10a,
Wil10b
] can be strengthened to a significant separation...
...Our most technically involved result is that the recent lower bound of Williams [
Wil10b
] that NEXP � ACC 0 extends to the robustly often setting...
...Now we are ready to prove the robustly often analogue of Williams’ main result [
Wil10b
]...
Lance Fortnow
,
et al.
Robust Simulations and Significant Separations
...The two topics are time-space lower bounds for the satisfiability problem (originating with work of Fortnow and others [2,3]) and circuit size lower bounds for nondeterministic exponential time [7,
8
]...
Ryan Williams
.
Diagonalization Strikes Back: Some Recent Lower Bounds in Complexity T...
References
(39)
Z~ formulae on finite structures
(
Citations: 135
)
M. Ajtai
Journal:
Annals of Pure and Applied Logic - APAL
, 1983
The Permanent Requires Large Uniform Threshold Circuits
(
Citations: 22
)
Eric Allender
Journal:
Chicago Journal of Theoretical Computer Science - CJTCS
, vol. 1999, 1999
The monotone circuit complexity of Boolean functions
(
Citations: 128
)
Noga Alon
,
Ravi B. Boppana
Journal:
Combinatorica
, vol. 7, no. 1, pp. 1-22, 1987
Computational Complexity - A Modern Approach
(
Citations: 73
)
Sanjeev Arora
,
Boaz Barak
Published in 2009.
A Uniform Circuit Lower Bound for the Permanent
(
Citations: 29
)
Eric Allender
,
Vivek Gore
Journal:
Siam Journal on Computing - SIAMCOMP
, vol. 23, no. 5, pp. 1026-1049, 1994
Order by:
Citations
(6)
Linear Systems over Finite Abelian Groups
Arkadev Chattopadhyay
,
Shachar Lovett
Conference:
Annual IEEE Conference on Computational Complexity - CCC
, pp. 300-308, 2011
NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of
Fengming Wang
Conference:
Theory and Applications of Models of Computation - TAMC
, pp. 164-170, 2011
Robust Simulations and Significant Separations
(
Citations: 1
)
Lance Fortnow
,
Rahul Santhanam
Journal:
Computing Research Repository - CORR
, vol. abs/1012.2, 2010
NE is not NP Turing Reducible to Nonexpoentially Dense NP Sets
Bin Fu
Journal:
Electronic Colloquium on Computational Complexity - ECCC
, vol. abs/1012.2, 2010
Diagonalization Strikes Back: Some Recent Lower Bounds in Complexity Theory
Ryan Williams