Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
149 | Mikkel Thorup |
On AC0 implementations of fusion trees and atomic heaps. |
SODA |
2003 |
DBLP BibTeX RDF |
|
131 | Alexander A. Sherstov |
Separating AC0 from depth-2 majority circuits. |
STOC |
2007 |
DBLP DOI BibTeX RDF |
AC0, communication complexity, discrepancy, threshold circuits |
108 | Manindra Agrawal, Eric Allender |
An Isomorphism Theorem for Circuit Complexity. |
CCC |
1996 |
DBLP DOI BibTeX RDF |
Complete Sets, Berman-Hartmanis Conjecture, NC1, AC0, NC0, projections, Circuit Complexity, uniformity, Isomorphisms |
63 | Mikkel Thorup |
Equivalence between priority queues and sorting. |
J. ACM |
2007 |
DBLP DOI BibTeX RDF |
sorting, Priority queues |
63 | Vikraman Arvind, K. V. Subrahmanyam 0001, N. V. Vinodchandran |
The Query Complexity of Program Checking by Constant-Depth Circuits. |
ISAAC |
1999 |
DBLP DOI BibTeX RDF |
|
54 | Manindra Agrawal |
Towards Uniform AC0 - Isomorphisms. |
CCC |
2001 |
DBLP DOI BibTeX RDF |
|
54 | Andris Ambainis, David A. Mix Barrington, Huong LeThanh |
On Counting AC0 Circuits with Negative Constants. |
MFCS |
1998 |
DBLP DOI BibTeX RDF |
|
47 | Alexander Healy |
Randomness-Efficient Sampling Within NC1. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
47 | Fabrice Noilhan, Miklos Santha |
Semantical Counting Circuits. |
CIAC |
2000 |
DBLP DOI BibTeX RDF |
|
47 | David A. Mix Barrington, Denis Thérien |
Finite monoids and the fine structure of NC1. |
J. ACM |
1988 |
DBLP DOI BibTeX RDF |
|
45 | Phokion G. Kolaitis, Swastik Kopparty |
Random graphs and the parity quantifier. |
STOC |
2009 |
DBLP DOI BibTeX RDF |
0-1 law, AC0, modular convergence, first-order logic |
38 | Akinobu Miyata, Jun Tarui, Etsuji Tomita |
Learning Boolean Functions in AC0 on Attribute and Classification Noise. |
ALT |
2004 |
DBLP DOI BibTeX RDF |
|
38 | Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio |
Learnability beyond AC0. |
STOC |
2002 |
DBLP DOI BibTeX RDF |
|
38 | Torben Hagerup |
Simpler and Faster Dictionaries on the AC0 RAM. |
ICALP |
1998 |
DBLP DOI BibTeX RDF |
|
32 | Heribert Vollmer |
The Complexity of Deciding if a Boolean Function Can Be Computed by Circuits over a Restricted Basis. |
Theory Comput. Syst. |
2009 |
DBLP DOI BibTeX RDF |
Post’s lattice, Membership problem, Computational complexity, Clones, Boolean circuit |
32 | Luc Longpré, Pierre McKenzie |
The Complexity of Solitaire. |
MFCS |
2007 |
DBLP DOI BibTeX RDF |
|
32 | Michal Koucký 0001, Pavel Pudlák, Denis Thérien |
Bounded-depth circuits: separating wires from gates. |
STOC |
2005 |
DBLP DOI BibTeX RDF |
communication, complexity, lower bounds, regular languages, wires, constant-depth circuits, gates |
32 | Fabrice Noilhan, Miklos Santha |
Semantical Counting Circuits. |
Theory Comput. Syst. |
2003 |
DBLP DOI BibTeX RDF |
|
32 | Emanuele Viola |
Hardness vs. Randomness within Alternating Time. |
CCC |
2003 |
DBLP DOI BibTeX RDF |
|
32 | Johann A. Makowsky |
Invariant Definability and P/poly. |
CSL |
1998 |
DBLP DOI BibTeX RDF |
|
29 | Benjamin Rossman |
On the constant-depth complexity of k-clique. |
STOC |
2008 |
DBLP DOI BibTeX RDF |
ac0, bounded variable hierarchy, k-clique, first-order logic, circuit complexity, constant-depth circuits |
28 | Nathan Linial, Yishay Mansour, Noam Nisan |
Constant Depth Circuits, Fourier Transform, and Learnability. |
J. ACM |
1993 |
DBLP DOI BibTeX RDF |
AC0 circuits, harmonic analysis learning, complexity, approximation, Boolean functions |
22 | Joseph Slote |
Parity vs. AC0 with Simple Quantum Preprocessing. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
22 | Vinayak M. Kumar |
Tight Correlation Bounds for Circuits Between AC0 and TC0. |
Electron. Colloquium Comput. Complex. |
2023 |
DBLP BibTeX RDF |
|
22 | Stefan Göller, Nathan Grosshans |
The AC0-Complexity Of Visibly Pushdown Languages. |
CoRR |
2023 |
DBLP DOI BibTeX RDF |
|
22 | Xin Lyu 0003 |
Improved Pseudorandom Generators for AC0 Circuits. |
CoRR |
2023 |
DBLP DOI BibTeX RDF |
|
22 | Vinayak M. Kumar |
Tight Correlation Bounds for Circuits Between AC0 and TC0. |
CoRR |
2023 |
DBLP DOI BibTeX RDF |
|
22 | Joseph Slote |
Parity vs. AC0 with simple quantum preprocessing. |
CoRR |
2023 |
DBLP DOI BibTeX RDF |
|
22 | Vinayak M. Kumar |
Tight Correlation Bounds for Circuits Between AC0 and TC0. |
CCC |
2023 |
DBLP DOI BibTeX RDF |
|
22 | Michaël Cadilhac, Charles Paperman |
The regular languages of wire linear AC0. |
Acta Informatica |
2022 |
DBLP DOI BibTeX RDF |
|
22 | Xin Lyu 0002 |
Improved Pseudorandom Generators for AC0 Circuits. |
Electron. Colloquium Comput. Complex. |
2022 |
DBLP BibTeX RDF |
|
22 | Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar |
Criticality of AC0-Formulae. |
Electron. Colloquium Comput. Complex. |
2022 |
DBLP BibTeX RDF |
|
22 | Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar |
Criticality of AC0 formulae. |
CoRR |
2022 |
DBLP DOI BibTeX RDF |
|
22 | Xuangui Huang, Peter Ivanov, Emanuele Viola |
Affine Extractors and AC0-Parity. |
APPROX/RANDOM |
2022 |
DBLP DOI BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
The Large-Error Approximate Degree of AC0. |
Theory Comput. |
2021 |
DBLP BibTeX RDF |
|
22 | Xuangui Huang, Peter Ivanov, Emanuele Viola |
Affine extractors and AC0-Parity. |
Electron. Colloquium Comput. Complex. |
2021 |
DBLP BibTeX RDF |
|
22 | Emanuele Viola |
AC0 Unpredictability. |
ACM Trans. Comput. Theory |
2021 |
DBLP DOI BibTeX RDF |
|
22 | Yuval Filmus, Or Meir, Avishay Tal |
Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
22 | Emanuele Viola |
New lower bounds for probabilistic degree and AC0 with parity gates. |
Electron. Colloquium Comput. Complex. |
2020 |
DBLP BibTeX RDF |
|
22 | Yuval Filmus, Or Meir, Avishay Tal |
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0. |
Electron. Colloquium Comput. Complex. |
2020 |
DBLP BibTeX RDF |
|
22 | Max Bannach, Till Tantau |
Computing Hitting Set Kernels By AC0-Circuits. |
Theory Comput. Syst. |
2020 |
DBLP DOI BibTeX RDF |
|
22 | Yuval Filmus, Or Meir, Avishay Tal |
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0. |
CoRR |
2020 |
DBLP BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. |
SIAM J. Comput. |
2020 |
DBLP DOI BibTeX RDF |
|
22 | Oded Goldreich 0001, Guy N. Rothblum |
Constant-Round Interactive Proof Systems for AC0[2] and NC1. |
Computational Complexity and Property Testing |
2020 |
DBLP DOI BibTeX RDF |
|
22 | Shion Samadder Chaudhury, Sabyasachi Dutta, Kouichi Sakurai |
AC0 Constructions of Secret Sharing Schemes - Accommodating New Parties. |
NSS |
2020 |
DBLP DOI BibTeX RDF |
|
22 | Benjamin Rossman, Srikanth Srinivasan 0001 |
Separation of AC0[⊕] Formulas and Circuits. |
Theory Comput. |
2019 |
DBLP DOI BibTeX RDF |
|
22 | Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal |
AC0[p] Lower Bounds against MCSP via the Coin Problem. |
Electron. Colloquium Comput. Complex. |
2019 |
DBLP BibTeX RDF |
|
22 | Aditya Potukuchi |
On the AC0[⊕] complexity of Andreev's Problem. |
Electron. Colloquium Comput. Complex. |
2019 |
DBLP BibTeX RDF |
|
22 | Aditya Potukuchi |
On the AC0[⊕] complexity of Andreev's Problem. |
CoRR |
2019 |
DBLP BibTeX RDF |
|
22 | |
AC0 Constructions for Evolving Secret Sharing Schemes and Redistribution of Secret Shares. |
IACR Cryptol. ePrint Arch. |
2019 |
DBLP BibTeX RDF |
|
22 | Yijia Chen, Jörg Flum |
Some lower bounds in parameterized AC0. |
Inf. Comput. |
2019 |
DBLP DOI BibTeX RDF |
|
22 | Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal |
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
22 | Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Avishay Tal |
AC0[p] Lower Bounds Against MCSP via the Coin Problem. |
ICALP |
2019 |
DBLP DOI BibTeX RDF |
|
22 | Alexander A. Sherstov, Pei Wu |
Near-optimal lower bounds on the threshold degree and sign-rank of AC0. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
22 | Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan 0001, Utkarsh Tripathi, S. Venkitesh |
A fixed-depth size-hierarchy theorem for AC0[⊕] via the coin problem. |
STOC |
2019 |
DBLP DOI BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
The Large-Error Approximate Degree of AC0. |
APPROX-RANDOM |
2019 |
DBLP DOI BibTeX RDF |
|
22 | Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie 0002 |
AC0∘MOD2 lower bounds for the Boolean Inner Product. |
J. Comput. Syst. Sci. |
2018 |
DBLP DOI BibTeX RDF |
|
22 | Oded Goldreich 0001, Guy N. Rothblum |
Constant-round interactive proof systems for AC0[2] and NC1. |
Electron. Colloquium Comput. Complex. |
2018 |
DBLP BibTeX RDF |
|
22 | Emanuele Viola |
AC0 unpredictability. |
Electron. Colloquium Comput. Complex. |
2018 |
DBLP BibTeX RDF |
|
22 | Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal |
Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. |
Electron. Colloquium Comput. Complex. |
2018 |
DBLP BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
The Large-Error Approximate Degree of AC0. |
Electron. Colloquium Comput. Complex. |
2018 |
DBLP BibTeX RDF |
|
22 | Benjamin Rossman |
Subspace-Invariant AC0 Formulas. |
CoRR |
2018 |
DBLP BibTeX RDF |
|
22 | Kuan Cheng, Xin Li 0006 |
Randomness Extraction in AC0 and with Small Locality. |
APPROX-RANDOM |
2018 |
DBLP DOI BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. |
Electron. Colloquium Comput. Complex. |
2017 |
DBLP BibTeX RDF |
|
22 | Benjamin Rossman, Srikanth Srinivasan 0001 |
Separation of AC0[⊕] Formulas and Circuits. |
Electron. Colloquium Comput. Complex. |
2017 |
DBLP BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. |
CoRR |
2017 |
DBLP BibTeX RDF |
|
22 | Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Tal Malkin |
Non-Malleable Codes from Average-Case Hardness: AC0, Decision Trees, and Streaming Space-Bounded Tampering. |
IACR Cryptol. ePrint Arch. |
2017 |
DBLP BibTeX RDF |
|
22 | Kuan Cheng, Yuval Ishai, Xin Li 0006 |
Near-Optimal Secret Sharing and Error Correcting Codes in AC0. |
IACR Cryptol. ePrint Arch. |
2017 |
DBLP BibTeX RDF |
|
22 | Yuan Li, Alexander A. Razborov, Benjamin Rossman |
On the AC0 Complexity of Subgraph Isomorphism. |
SIAM J. Comput. |
2017 |
DBLP DOI BibTeX RDF |
|
22 | Ning Ding 0001, Yanli Ren, Dawu Gu |
Learning AC0 Under k-Dependent Distributions. |
TAMC |
2017 |
DBLP DOI BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
22 | Avishay Tal |
Tight Bounds on the Fourier Spectrum of AC0. |
CCC |
2017 |
DBLP DOI BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
Improved Bounds on the Sign-Rank of AC0. |
Electron. Colloquium Comput. Complex. |
2016 |
DBLP BibTeX RDF |
|
22 | Srikanth Srinivasan 0001 |
On Polynomial Approximations to AC0. |
Electron. Colloquium Comput. Complex. |
2016 |
DBLP BibTeX RDF |
|
22 | Kuan Cheng, Xin Li 0006 |
Randomness Extraction in AC0 and with Small Locality. |
Electron. Colloquium Comput. Complex. |
2016 |
DBLP BibTeX RDF |
|
22 | Arnaud Durand 0001, Anselm Haak, Juha Kontinen, Heribert Vollmer |
Descriptive Complexity of #AC0 Functions. |
CoRR |
2016 |
DBLP BibTeX RDF |
|
22 | Yijia Chen, Jörg Flum |
Some lower bounds in parameterized AC0. |
CoRR |
2016 |
DBLP BibTeX RDF |
|
22 | Kuan Cheng, Xin Li 0006 |
Randomness Extraction in AC0 and with Small Locality. |
CoRR |
2016 |
DBLP BibTeX RDF |
|
22 | Arnaud Durand 0001, Anselm Haak, Juha Kontinen, Heribert Vollmer |
Descriptive Complexity of #AC0 Functions. |
CSL |
2016 |
DBLP DOI BibTeX RDF |
|
22 | Stefano Mazzanti |
Bases for AC0 and Other Complexity Classes. |
Fundam. Informaticae |
2015 |
DBLP DOI BibTeX RDF |
|
22 | Oded Goldreich 0001, Emanuele Viola, Avi Wigderson |
On Randomness Extraction in AC0. |
Electron. Colloquium Comput. Complex. |
2015 |
DBLP BibTeX RDF |
|
22 | Srikanth Srinivasan 0001 |
A Compression Algorithm for AC0[⊕] circuits using Certifying Polynomials. |
Electron. Colloquium Comput. Complex. |
2015 |
DBLP BibTeX RDF |
|
22 | Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie 0002 |
AC0 \circ MOD2 lower bounds for the Boolean Inner Product. |
Electron. Colloquium Comput. Complex. |
2015 |
DBLP BibTeX RDF |
|
22 | Yuval Filmus, Toniann Pitassi, Rahul Santhanam |
Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds. |
ACM Trans. Comput. Theory |
2015 |
DBLP DOI BibTeX RDF |
|
22 | Oded Goldreich 0001, Emanuele Viola, Avi Wigderson |
On Randomness Extraction in AC0. |
CCC |
2015 |
DBLP DOI BibTeX RDF |
|
22 | Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen |
Candidate weak pseudorandom functions in AC0 ○ MOD2. |
Electron. Colloquium Comput. Complex. |
2014 |
DBLP BibTeX RDF |
|
22 | Igor Carboni Oliveira, Rahul Santhanam |
Majority is incompressible by AC0[p] circuits. |
Electron. Colloquium Comput. Complex. |
2014 |
DBLP BibTeX RDF |
|
22 | Yuan Li, Alexander A. Razborov, Benjamin Rossman |
On the AC0 Complexity of Subgraph Isomorphism. |
Electron. Colloquium Comput. Complex. |
2014 |
DBLP BibTeX RDF |
|
22 | Avishay Tal |
Tight bounds on The Fourier Spectrum of AC0. |
Electron. Colloquium Comput. Complex. |
2014 |
DBLP BibTeX RDF |
|
22 | Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen |
Candidate weak pseudorandom functions in AC0 ○ MOD2. |
ITCS |
2014 |
DBLP DOI BibTeX RDF |
|
22 | Yuan Li, Alexander A. Razborov, Benjamin Rossman |
On the AC0 Complexity of Subgraph Isomorphism. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
22 | Jan Krajícek |
A reduction of proof complexity to computational complexity for AC0[p] Frege systems. |
Electron. Colloquium Comput. Complex. |
2013 |
DBLP BibTeX RDF |
|
22 | Zachary Remscrim, Michael Sipser |
AC0 Pseudorandomness of Natural Operations. |
Electron. Colloquium Comput. Complex. |
2013 |
DBLP BibTeX RDF |
|
22 | Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner |
Graph Isomorphism is Not AC0-Reducible to Group Isomorphism. |
ACM Trans. Comput. Theory |
2013 |
DBLP DOI BibTeX RDF |
|
22 | Luca Trevisan, Tongke Xue |
A Derandomized Switching Lemma and an Improved Derandomization of AC0. |
CCC |
2013 |
DBLP DOI BibTeX RDF |
|
22 | Paul Beame, Widad Machmouchi |
The quantum query complexity of AC0. |
Quantum Inf. Comput. |
2012 |
DBLP DOI BibTeX RDF |
|
22 | Swastik Kopparty, Srikanth Srinivasan 0001 |
Certifying Polynomials for AC0[⊕] circuits, with applications. |
Electron. Colloquium Comput. Complex. |
2012 |
DBLP BibTeX RDF |
|
22 | Luca Trevisan |
A Derandomized Switching Lemma and an Improved Derandomization of AC0. |
Electron. Colloquium Comput. Complex. |
2012 |
DBLP BibTeX RDF |
|
22 | Chris Beck, Russell Impagliazzo, Shachar Lovett |
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. |
Electron. Colloquium Comput. Complex. |
2012 |
DBLP BibTeX RDF |
|
22 | Russell Impagliazzo, William Matthews, Ramamohan Paturi |
A satisfiability algorithm for AC0. |
SODA |
2012 |
DBLP DOI BibTeX RDF |
|