Cited By
View all- Williams R(2014)Nonuniform ACC Circuit Lower BoundsJournal of the ACM10.1145/255990361:1(1-32)Online publication date: 1-Jan-2014
Nexp does not have non-uniform quasipolynomial-size ACC circuits of o(log log n) depth
Pages 164 - 170
Abstract
ACCm circuits are circuits consisting of unbounded fan-in AND, OR and MODm gates and unary NOT gates, where m is a fixed integer. We show that there exists a language in non-deterministic exponential time which can not be computed by any non-uniform family of ACCm circuits of quasipolynomial size and o(log log n) depth, where m is an arbitrarily chosen constant.
References
[1]
Allender, E.: The permanent requires large uniform threshold circuits. Chicago J. Theor. Comput. Sci. (1999)
[2]
Allender, E., Gore, V.: A uniform circuit lower bound for the permanent. SIAM Journal on Computing 23(5), 1026-1049 (1994)
[3]
Arora, S., Barak, B.: Computational Complexity, a modern approach. Cambridge University Press, Cambridge (2009)
[4]
Barrington, D.A.M.: Quasipolynomial size circuit classes. In: Proc. IEEE Conf. on Structure in Complexity Theory, pp. 86-93 (1992)
[5]
Beame, P., Håstad, J.: Optimal bounds for decision problems on the crcw pram. Journal of the ACM 36(3), 643-670 (1989)
[6]
Beigel, R.: When do extra majority gates help? polylog() majority gates are equivalent to one. Computational Complexity 4, 314-324 (1994)
[7]
Beigel, R., Tarui, J.: On ACC. Computational Complexity 4, 350-366 (1994)
[8]
Beigel, R., Tarui, J., Toda, S.: On probabilistic acc circuits with an exact-threshold output gate. In: Ibaraki, T., Iwama, K., Yamashita, M., Inagaki, Y., Nishizeki, T. (eds.) ISAAC 1992. LNCS, vol. 650, pp. 420-429. Springer, Heidelberg (1992)
[9]
Fortnow, L., Santhanam, R.: Robust simulations and significant separations, http://arxiv.org/abs/1012.2034 (manuscript)
[10]
Håstad, J.: Almost optimal lower bounds for small depth circuits. In: Proc. ACM Symp. on Theory of Computing (STOC), pp. 6-20 (1986)
[11]
Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences 65(4), 672-694 (2002)
[12]
Koiran, P., Perifel, S.: A superpolynomial lower bound on the size of uniform non-constantdepth threshold circuits for the permanent. Computational Complexity, 35-40 (2009)
[13]
Razborov, A.: Lower bounds on the size of bounded-depth networks over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences. of the USSR 41(4), 333-338 (1987)
[14]
Smolensky, R.: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In: Proc. ACM Symp. on Theory of Computing (STOC), pp. 77-82 (1987)
[15]
Vollmer, H.: Introduction to Circuit Complexity. Springer, Heidelberg (1999)
[16]
Williams, R.: Improving exhaustive search implies superpolynomial lower bounds. In: Proc. ACM Symp. on Theory of Computing (STOC), pp. 231-240 (2010)
[17]
Williams, R.: Non-uniform ACC circuit lower bounds. In: Proc. IEEE Conf. on Computational Complexity (2010), http://www.cs.cmu.edu/~ryanw/acc-lbs.pdf
[18]
Yao, A.C.-C.: On ACC and threshold circuits. In: Proc. IEEE Symp. on Found. of Comp. Sci (FOCS), pp. 619-627 (1990)
[19]
Zak, S.: A turing machine hierarchy. Theoretical Computer Science 26, 327-333 (1983)
- Nexp does not have non-uniform quasipolynomial-size ACC circuits of o(log log n) depth
Recommendations
Linear-size log-depth negation-limited inverter for k-tonic binary sequences
TAMC'07: Proceedings of the 4th international conference on Theory and applications of models of computationA zero-one sequence x1,..., xn is k-tonic if the number of i's such that xi ≠ xi+1 is at most k. The notion generalizes well-known bitonic sequences. In negation-limited complexity, one considers circuits with a limited number of NOT gates, being ...
Linear-size log-depth negation-limited inverter for k-tonic binary sequences
In negation-limited complexity, one considers circuits with a limited number of NOT gates, being motivated by the gap in our understanding of monotone versus general circuit complexity. In this context, the study of inverters, i.e., circuits with inputs ...
Monotone Circuits for Connectivity Have Depth (log n)2-o(1)
We prove that a monotone circuit of size nd recognizing connectivity must have depth $\Omega((\log n)^2/\log d)$. For formulas this implies depth $\Omega((\log n)^2/\log\log n)$. For polynomial-size circuits the bound becomes $\Omega((\log n)^2)$ which ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 23 May 2011
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 30 Dec 2024
Other Metrics
Citations
Cited By
View all- Williams R(2014)Nonuniform ACC Circuit Lower BoundsJournal of the ACM10.1145/255990361:1(1-32)Online publication date: 1-Jan-2014