Search results for "AC0"

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