Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
149 | Mikkel Thorup |
On AC0 implementations of fusion trees and atomic heaps. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SODA ![In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA., pp. 699-707, 2003, ACM/SIAM, 0-89871-538-5. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP BibTeX RDF |
|
131 | Alexander A. Sherstov |
Separating AC0 from depth-2 majority circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pp. 294-301, 2007, ACM, 978-1-59593-631-8. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
AC0, communication complexity, discrepancy, threshold circuits |
108 | Manindra Agrawal, Eric Allender |
An Isomorphism Theorem for Circuit Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, Philadelphia, Pennsylvania, USA, May 24-27, 1996, pp. 2-11, 1996, IEEE Computer Society, 0-8186-7386-9. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 54(6), pp. 28, 2007. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ISAAC ![In: Algorithms and Computation, 10th International Symposium, ISAAC '99, Chennai, India, December 16-18, 1999, Proceedings, pp. 123-132, 1999, Springer, 3-540-66916-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
54 | Manindra Agrawal |
Towards Uniform AC0 - Isomorphisms. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pp. 13-20, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
54 | Andris Ambainis, David A. Mix Barrington, Huong LeThanh |
On Counting AC0 Circuits with Negative Constants. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 1998, 23rd International Symposium, MFCS'98, Brno, Czech Republic, August 24-28, 1998, Proceedings, pp. 409-417, 1998, Springer, 3-540-64827-5. The full citation details ...](Pics/full.jpeg) |
1998 |
DBLP DOI BibTeX RDF |
|
47 | Alexander Healy |
Randomness-Efficient Sampling Within NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
APPROX-RANDOM ![In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, pp. 398-409, 2006, Springer, 3-540-38044-2. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
47 | Fabrice Noilhan, Miklos Santha |
Semantical Counting Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CIAC ![In: Algorithms and Complexity, 4th Italian Conference, CIAC 2000, Rome, Italy, March 2000, Proceedings, pp. 87-101, 2000, Springer, 3-540-67159-5. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
47 | David A. Mix Barrington, Denis Thérien |
Finite monoids and the fine structure of NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 35(4), pp. 941-952, 1988. The full citation details ...](Pics/full.jpeg) |
1988 |
DBLP DOI BibTeX RDF |
|
45 | Phokion G. Kolaitis, Swastik Kopparty |
Random graphs and the parity quantifier. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pp. 705-714, 2009, ACM, 978-1-60558-506-2. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ALT ![In: Algorithmic Learning Theory, 15th International Conference, ALT 2004, Padova, Italy, October 2-5, 2004, Proceedings, pp. 142-155, 2004, Springer, 978-3-540-23356-5. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
38 | Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio |
Learnability beyond AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pp. 776-784, 2002, ACM, 1-58113-495-9. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
|
38 | Torben Hagerup |
Simpler and Faster Dictionaries on the AC0 RAM. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP ![In: Automata, Languages and Programming, 25th International Colloquium, ICALP'98, Aalborg, Denmark, July 13-17, 1998, Proceedings, pp. 79-90, 1998, Springer, 3-540-64781-3. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. Syst. ![In: Theory Comput. Syst. 44(1), pp. 82-90, 2009. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
Post’s lattice, Membership problem, Computational complexity, Clones, Boolean circuit |
32 | Luc Longpré, Pierre McKenzie |
The Complexity of Solitaire. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 2007, 32nd International Symposium, MFCS 2007, Ceský Krumlov, Czech Republic, August 26-31, 2007, Proceedings, pp. 182-193, 2007, Springer, 978-3-540-74455-9. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
32 | Michal Koucký 0001, Pavel Pudlák, Denis Thérien |
Bounded-depth circuits: separating wires from gates. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pp. 257-265, 2005, ACM, 1-58113-960-8. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
communication, complexity, lower bounds, regular languages, wires, constant-depth circuits, gates |
32 | Fabrice Noilhan, Miklos Santha |
Semantical Counting Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. Syst. ![In: Theory Comput. Syst. 36(3), pp. 217-229, 2003. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
32 | Emanuele Viola |
Hardness vs. Randomness within Alternating Time. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark, pp. 53-, 2003, IEEE Computer Society, 0-7695-1879-6. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
32 | Johann A. Makowsky |
Invariant Definability and P/poly. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CSL ![In: Computer Science Logic, 12th International Workshop, CSL '98, Annual Conference of the EACSL, Brno, Czech Republic, August 24-28, 1998, Proceedings, pp. 142-158, 1998, Springer, 3-540-65922-6. The full citation details ...](Pics/full.jpeg) |
1998 |
DBLP DOI BibTeX RDF |
|
29 | Benjamin Rossman |
On the constant-depth complexity of k-clique. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pp. 721-730, 2008, ACM, 978-1-60558-047-0. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. ACM ![In: J. ACM 40(3), pp. 607-620, 1993. The full citation details ...](Pics/full.jpeg) |
1993 |
DBLP DOI BibTeX RDF |
AC0 circuits, harmonic analysis learning, complexity, approximation, Boolean functions |
22 | Joseph Slote |
Parity vs. AC0 with Simple Quantum Preprocessing. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ITCS ![In: 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, pp. 92:1-92:21, 2024, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-309-6. The full citation details ...](Pics/full.jpeg) |
2024 |
DBLP DOI BibTeX RDF |
|
22 | Vinayak M. Kumar |
Tight Correlation Bounds for Circuits Between AC0 and TC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR23, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP BibTeX RDF |
|
22 | Stefan Göller, Nathan Grosshans |
The AC0-Complexity Of Visibly Pushdown Languages. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2302.13116, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
22 | Xin Lyu 0003 |
Improved Pseudorandom Generators for AC0 Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2301.10102, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
22 | Vinayak M. Kumar |
Tight Correlation Bounds for Circuits Between AC0 and TC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2304.02770, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
22 | Joseph Slote |
Parity vs. AC0 with simple quantum preprocessing. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2311.13679, 2023. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
22 | Vinayak M. Kumar |
Tight Correlation Bounds for Circuits Between AC0 and TC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 38th Computational Complexity Conference, CCC 2023, July 17-20, 2023, Warwick, UK, pp. 18:1-18:40, 2023, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-282-2. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
22 | Michaël Cadilhac, Charles Paperman |
The regular languages of wire linear AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Acta Informatica ![In: Acta Informatica 59(4), pp. 321-336, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
22 | Xin Lyu 0002 |
Improved Pseudorandom Generators for AC0 Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR22, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP BibTeX RDF |
|
22 | Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar |
Criticality of AC0-Formulae. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR22, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP BibTeX RDF |
|
22 | Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar |
Criticality of AC0 formulae. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2212.08397, 2022. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
22 | Xuangui Huang, Peter Ivanov, Emanuele Viola |
Affine Extractors and AC0-Parity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
APPROX/RANDOM ![In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022, September 19-21, 2022, University of Illinois, Urbana-Champaign, USA (Virtual Conference)., pp. 9:1-9:14, 2022, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-249-5. The full citation details ...](Pics/full.jpeg) |
2022 |
DBLP DOI BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
The Large-Error Approximate Degree of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. ![In: Theory Comput. 17, pp. 1-46, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
22 | Xuangui Huang, Peter Ivanov, Emanuele Viola |
Affine extractors and AC0-Parity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR21, 2021. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP BibTeX RDF |
|
22 | Emanuele Viola |
AC0 Unpredictability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ACM Trans. Comput. Theory ![In: ACM Trans. Comput. Theory 13(1), pp. 5:1-5:8, 2021. The full citation details ...](Pics/full.jpeg) |
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). ![Search on Bibsonomy](Pics/bibsonomy.png) |
ITCS ![In: 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference., pp. 89:1-89:7, 2021, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-177-1. The full citation details ...](Pics/full.jpeg) |
2021 |
DBLP DOI BibTeX RDF |
|
22 | Emanuele Viola |
New lower bounds for probabilistic degree and AC0 with parity gates. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR20, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
22 | Yuval Filmus, Or Meir, Avishay Tal |
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR20, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
22 | Max Bannach, Till Tantau |
Computing Hitting Set Kernels By AC0-Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. Syst. ![In: Theory Comput. Syst. 64(3), pp. 374-399, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
22 | Yuval Filmus, Or Meir, Avishay Tal |
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/2012.02210, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIAM J. Comput. ![In: SIAM J. Comput. 49(4), 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
22 | Oded Goldreich 0001, Guy N. Rothblum |
Constant-Round Interactive Proof Systems for AC0[2] and NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Computational Complexity and Property Testing ![In: Computational Complexity and Property Testing - On the Interplay Between Randomness and Computation, pp. 326-351, 2020, Springer, 978-3-030-43661-2. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
22 | Shion Samadder Chaudhury, Sabyasachi Dutta, Kouichi Sakurai |
AC0 Constructions of Secret Sharing Schemes - Accommodating New Parties. ![Search on Bibsonomy](Pics/bibsonomy.png) |
NSS ![In: Network and System Security - 14th International Conference, NSS 2020, Melbourne, VIC, Australia, November 25-27, 2020, Proceedings, pp. 292-308, 2020, Springer, 978-3-030-65744-4. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
22 | Benjamin Rossman, Srikanth Srinivasan 0001 |
Separation of AC0[⊕] Formulas and Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. ![In: Theory Comput. 15, pp. 1-20, 2019. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR19, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
22 | Aditya Potukuchi |
On the AC0[⊕] complexity of Andreev's Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR19, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
22 | Aditya Potukuchi |
On the AC0[⊕] complexity of Andreev's Problem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1907.07969, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
22 | |
AC0 Constructions for Evolving Secret Sharing Schemes and Redistribution of Secret Shares. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IACR Cryptol. ePrint Arch. ![In: IACR Cryptol. ePrint Arch. 2019, pp. 1428, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
22 | Yijia Chen, Jörg Flum |
Some lower bounds in parameterized AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Comput. ![In: Inf. Comput. 267, pp. 116-134, 2019. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ITCS ![In: 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, pp. 22:1-22:15, 2019, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-095-8. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP ![In: 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece., pp. 66:1-66:15, 2019, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-109-2. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
22 | Alexander A. Sherstov, Pei Wu |
Near-optimal lower bounds on the threshold degree and sign-rank of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pp. 401-412, 2019, ACM, 978-1-4503-6705-9. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pp. 442-453, 2019, ACM, 978-1-4503-6705-9. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP DOI BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
The Large-Error Approximate Degree of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
APPROX-RANDOM ![In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA., pp. 55:1-55:16, 2019, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-125-2. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comput. Syst. Sci. ![In: J. Comput. Syst. Sci. 97, pp. 45-59, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
22 | Oded Goldreich 0001, Guy N. Rothblum |
Constant-round interactive proof systems for AC0[2] and NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR18, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
22 | Emanuele Viola |
AC0 unpredictability. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR18, 2018. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR18, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
The Large-Error Approximate Degree of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR18, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
22 | Benjamin Rossman |
Subspace-Invariant AC0 Formulas. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1806.04831, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
22 | Kuan Cheng, Xin Li 0006 |
Randomness Extraction in AC0 and with Small Locality. ![Search on Bibsonomy](Pics/bibsonomy.png) |
APPROX-RANDOM ![In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, pp. 37:1-37:20, 2018, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-085-9. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP DOI BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR17, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP BibTeX RDF |
|
22 | Benjamin Rossman, Srikanth Srinivasan 0001 |
Separation of AC0[⊕] Formulas and Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR17, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1703.05784, 2017. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IACR Cryptol. ePrint Arch. ![In: IACR Cryptol. ePrint Arch. 2017, pp. 1061, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP BibTeX RDF |
|
22 | Kuan Cheng, Yuval Ishai, Xin Li 0006 |
Near-Optimal Secret Sharing and Error Correcting Codes in AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IACR Cryptol. ePrint Arch. ![In: IACR Cryptol. ePrint Arch. 2017, pp. 927, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP BibTeX RDF |
|
22 | Yuan Li, Alexander A. Razborov, Benjamin Rossman |
On the AC0 Complexity of Subgraph Isomorphism. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SIAM J. Comput. ![In: SIAM J. Comput. 46(3), pp. 936-971, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
22 | Ning Ding 0001, Yanli Ren, Dawu Gu |
Learning AC0 Under k-Dependent Distributions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
TAMC ![In: Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Bern, Switzerland, April 20-22, 2017, Proceedings, pp. 187-200, 2017, 978-3-319-55910-0. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pp. 1-12, 2017, IEEE Computer Society, 978-1-5386-3464-6. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
22 | Avishay Tal |
Tight Bounds on the Fourier Spectrum of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, pp. 15:1-15:31, 2017, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-040-8. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP DOI BibTeX RDF |
|
22 | Mark Bun, Justin Thaler |
Improved Bounds on the Sign-Rank of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR16, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP BibTeX RDF |
|
22 | Srikanth Srinivasan 0001 |
On Polynomial Approximations to AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR16, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP BibTeX RDF |
|
22 | Kuan Cheng, Xin Li 0006 |
Randomness Extraction in AC0 and with Small Locality. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR16, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP BibTeX RDF |
|
22 | Arnaud Durand 0001, Anselm Haak, Juha Kontinen, Heribert Vollmer |
Descriptive Complexity of #AC0 Functions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1604.06617, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP BibTeX RDF |
|
22 | Yijia Chen, Jörg Flum |
Some lower bounds in parameterized AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1606.08014, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP BibTeX RDF |
|
22 | Kuan Cheng, Xin Li 0006 |
Randomness Extraction in AC0 and with Small Locality. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1602.01530, 2016. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP BibTeX RDF |
|
22 | Arnaud Durand 0001, Anselm Haak, Juha Kontinen, Heribert Vollmer |
Descriptive Complexity of #AC0 Functions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CSL ![In: 25th EACSL Annual Conference on Computer Science Logic, CSL 2016, August 29 - September 1, 2016, Marseille, France, pp. 20:1-20:16, 2016, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-95977-022-4. The full citation details ...](Pics/full.jpeg) |
2016 |
DBLP DOI BibTeX RDF |
|
22 | Stefano Mazzanti |
Bases for AC0 and Other Complexity Classes. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Fundam. Informaticae ![In: Fundam. Informaticae 136(4), pp. 433-460, 2015. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP DOI BibTeX RDF |
|
22 | Oded Goldreich 0001, Emanuele Viola, Avi Wigderson |
On Randomness Extraction in AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR15, 2015. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP BibTeX RDF |
|
22 | Srikanth Srinivasan 0001 |
A Compression Algorithm for AC0[⊕] circuits using Certifying Polynomials. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR15, 2015. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR15, 2015. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP BibTeX RDF |
|
22 | Yuval Filmus, Toniann Pitassi, Rahul Santhanam |
Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ACM Trans. Comput. Theory ![In: ACM Trans. Comput. Theory 7(2), pp. 5:1-5:16, 2015. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP DOI BibTeX RDF |
|
22 | Oded Goldreich 0001, Emanuele Viola, Avi Wigderson |
On Randomness Extraction in AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, pp. 601-668, 2015, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 978-3-939897-81-1. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP DOI BibTeX RDF |
|
22 | Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen |
Candidate weak pseudorandom functions in AC0 ○ MOD2. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR14, 2014. The full citation details ...](Pics/full.jpeg) |
2014 |
DBLP BibTeX RDF |
|
22 | Igor Carboni Oliveira, Rahul Santhanam |
Majority is incompressible by AC0[p] circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR14, 2014. The full citation details ...](Pics/full.jpeg) |
2014 |
DBLP BibTeX RDF |
|
22 | Yuan Li, Alexander A. Razborov, Benjamin Rossman |
On the AC0 Complexity of Subgraph Isomorphism. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR14, 2014. The full citation details ...](Pics/full.jpeg) |
2014 |
DBLP BibTeX RDF |
|
22 | Avishay Tal |
Tight bounds on The Fourier Spectrum of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR14, 2014. The full citation details ...](Pics/full.jpeg) |
2014 |
DBLP BibTeX RDF |
|
22 | Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen |
Candidate weak pseudorandom functions in AC0 ○ MOD2. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ITCS ![In: Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pp. 251-260, 2014, ACM, 978-1-4503-2698-8. The full citation details ...](Pics/full.jpeg) |
2014 |
DBLP DOI BibTeX RDF |
|
22 | Yuan Li, Alexander A. Razborov, Benjamin Rossman |
On the AC0 Complexity of Subgraph Isomorphism. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pp. 344-353, 2014, IEEE Computer Society, 978-1-4799-6517-5. The full citation details ...](Pics/full.jpeg) |
2014 |
DBLP DOI BibTeX RDF |
|
22 | Jan Krajícek |
A reduction of proof complexity to computational complexity for AC0[p] Frege systems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR13, 2013. The full citation details ...](Pics/full.jpeg) |
2013 |
DBLP BibTeX RDF |
|
22 | Zachary Remscrim, Michael Sipser |
AC0 Pseudorandomness of Natural Operations. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR13, 2013. The full citation details ...](Pics/full.jpeg) |
2013 |
DBLP BibTeX RDF |
|
22 | Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner |
Graph Isomorphism is Not AC0-Reducible to Group Isomorphism. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ACM Trans. Comput. Theory ![In: ACM Trans. Comput. Theory 5(4), pp. 13:1-13:13, 2013. The full citation details ...](Pics/full.jpeg) |
2013 |
DBLP DOI BibTeX RDF |
|
22 | Luca Trevisan, Tongke Xue |
A Derandomized Switching Lemma and an Improved Derandomization of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pp. 242-247, 2013, IEEE Computer Society, 978-0-7695-4997-2. The full citation details ...](Pics/full.jpeg) |
2013 |
DBLP DOI BibTeX RDF |
|
22 | Paul Beame, Widad Machmouchi |
The quantum query complexity of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Quantum Inf. Comput. ![In: Quantum Inf. Comput. 12(7-8), pp. 670-676, 2012. The full citation details ...](Pics/full.jpeg) |
2012 |
DBLP DOI BibTeX RDF |
|
22 | Swastik Kopparty, Srikanth Srinivasan 0001 |
Certifying Polynomials for AC0[⊕] circuits, with applications. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR12, 2012. The full citation details ...](Pics/full.jpeg) |
2012 |
DBLP BibTeX RDF |
|
22 | Luca Trevisan |
A Derandomized Switching Lemma and an Improved Derandomization of AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR12, 2012. The full citation details ...](Pics/full.jpeg) |
2012 |
DBLP BibTeX RDF |
|
22 | Chris Beck, Russell Impagliazzo, Shachar Lovett |
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR12, 2012. The full citation details ...](Pics/full.jpeg) |
2012 |
DBLP BibTeX RDF |
|
22 | Russell Impagliazzo, William Matthews, Ramamohan Paturi |
A satisfiability algorithm for AC0. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SODA ![In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pp. 961-972, 2012, SIAM, 978-1-61197-210-8. The full citation details ...](Pics/full.jpeg) |
2012 |
DBLP DOI BibTeX RDF |
|