Search results for "NC1"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
120	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
93	Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer	Nondeterministic NC1 Computation.	CCC	1996	DBLP DOI BibTeX RDF	nondeterministic Turing machine, leaf language, Computational complexity, circuit
93	David A. Mix Barrington, Denis Thérien	Finite monoids and the fine structure of NC1.	J. ACM	1988	DBLP DOI BibTeX RDF
82	Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao	Arithmetizing Classes Around NC 1 and L.	STACS	2007	DBLP DOI BibTeX RDF
66	Hervé Caussinus, François Lemieux	The Complexity of Computing over Quasigroups.	FSTTCS	1994	DBLP DOI BibTeX RDF
60	Liliana Cojocaru	Branching Programs, Grammar Systems and the NC1 Class.	SYNASC	2007	DBLP DOI BibTeX RDF
60	Alexander Healy	Randomness-Efficient Sampling Within NC1.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
60	Tomas Sander, Adam L. Young, Moti Yung	Non-Interactive CryptoComputing For NC1.	FOCS	1999	DBLP DOI BibTeX RDF	cryptocomputing, cryptography, public key, complexity theory, homomorphic encryption, secure computation
43	Stephen A. Cook, Tsuyoshi Morioka	Quantified propositional calculus and a second-order theory for NC1.	Arch. Math. Log.	2005	DBLP DOI BibTeX RDF	Computational Complexity, Proof Complexity, Bounded Arithmetic
43	Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano	On NC1 Boolean Circuit Composition of Non-interactive Perfect Zero-Knowledge.	MFCS	2004	DBLP DOI BibTeX RDF
33	Michal Koucký 0001	Circuit Complexity of Regular Languages.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Circuit complexity, Regular languages, Upper and lower bounds
33	Farid M. Ablayev, Cristopher Moore, Chris Pollett	Quantum and Stochastic Branching Programs of Bounded Width.	ICALP	2002	DBLP DOI BibTeX RDF
33	Fabrice Noilhan, Miklos Santha	Semantical Counting Circuits.	CIAC	2000	DBLP DOI BibTeX RDF
33	Bruno Poizat	Une tentative malheureuse do construire une structure éliminant rapidement les quanteurs.	CSL	2000	DBLP DOI BibTeX RDF
33	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
33	Pierre McKenzie, Klaus Reinhardt, V. Vinay	Circuits and Context-Free Languages.	COCOON	1999	DBLP DOI BibTeX RDF
33	Dieter van Melkebeek	Reducing P to a Sparse Set using a Constant Number of Queries Collapses P to L.	CCC	1996	DBLP DOI BibTeX RDF	computational complexity theory, sparse hard set problem for P
27	Jie Chen 0021, Qiaohan Chu, Ying Gao 0006, Jianting Ning, Luping Wang	Improved Fully Adaptive Decentralized MA-ABE for NC1 from MDDH.	ASIACRYPT (5)	2023	DBLP DOI BibTeX RDF
27	Razvan Rosie	Adaptively Secure Laconic Function Evaluation for NC1.	CT-RSA	2022	DBLP DOI BibTeX RDF
27	Lijie Chen 0001, Zhenjian Lu, Xin Lyu 0002, Igor Carboni Oliveira	Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
27	Lucas Kowalczyk, Hoeteck Wee	Compact Adaptively Secure ABE for sf NC1 from k-Lin.	J. Cryptol.	2020	DBLP DOI BibTeX RDF
27	Huijia Lin, Ji Luo 0002	Compact Adaptively Secure ABE from k-Lin: Beyond NC1 and towards NL.	IACR Cryptol. ePrint Arch.	2020	DBLP BibTeX RDF
27	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
27	Huijia Lin, Ji Luo 0002	Compact Adaptively Secure ABE from k-Lin: Beyond NC1 and Towards NL.	EUROCRYPT (3)	2020	DBLP DOI BibTeX RDF
27	Daniel Grier, Luke Schaeffer	Interactive shallow Clifford circuits: quantum advantage against NC1 and beyond.	CoRR	2019	DBLP BibTeX RDF
27	Lucas Kowalczyk, Hoeteck Wee	Compact Adaptively Secure ABE for NC1 from k-Lin.	IACR Cryptol. ePrint Arch.	2019	DBLP BibTeX RDF
27	Oded Goldreich 0001, Guy N. Rothblum	Constant-round interactive proof systems for AC0[2] and NC1.	Electron. Colloquium Comput. Complex.	2018	DBLP BibTeX RDF
27	Nuttapong Attrapadung, Takahiro Matsuda 0002, Ryo Nishimaki, Shota Yamada 0001, Takashi Yamakawa	Adaptively Single-Key Secure Constrained PRFs for NC1.	IACR Cryptol. ePrint Arch.	2018	DBLP BibTeX RDF
27	Nuttapong Attrapadung, Takahiro Matsuda 0002, Ryo Nishimaki, Shota Yamada 0001, Takashi Yamakawa	Constrained PRFs for NC1 in Traditional Groups.	IACR Cryptol. ePrint Arch.	2018	DBLP BibTeX RDF
27	Ran Canetti, Yilei Chen 0001	Constraint-hiding Constrained PRFs for NC1 from LWE.	IACR Cryptol. ePrint Arch.	2017	DBLP BibTeX RDF
27	Ran Canetti, Yilei Chen 0001	Constraint-Hiding Constrained PRFs for NC1 from LWE.	EUROCRYPT (1)	2017	DBLP DOI BibTeX RDF
27	Michael Hahn 0001, Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig	Visibly Counter Languages and the Structure of NC1.	MFCS (2)	2015	DBLP DOI BibTeX RDF
27	Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig	On Distinguishing NC1 and NL.	DLT	2015	DBLP DOI BibTeX RDF
27	Eric Miles	Iterated group products and leakage resilience against NC1.	ITCS	2014	DBLP DOI BibTeX RDF
27	Eric Miles	Iterated group products and leakage resilience against NC1.	IACR Cryptol. ePrint Arch.	2013	DBLP BibTeX RDF
27	Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas 0001, Heribert Vollmer	Counting classes and the fine structure between NC1 and L.	Theor. Comput. Sci.	2012	DBLP DOI BibTeX RDF
27	Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie	Low uniform versions of NC1.	Electron. Colloquium Comput. Complex.	2011	DBLP BibTeX RDF
27	Emil Jerábek	On theories of bounded arithmetic for NC1.	Ann. Pure Appl. Log.	2011	DBLP DOI BibTeX RDF
27	Andreas Krebs, Nutan Limaye, Meena Mahajan	Counting paths in VPA is complete for #NC1.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
27	Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas 0001, Heribert Vollmer	Counting Classes and the Fine Structure between NC1 and L.	Electron. Colloquium Comput. Complex.	2010	DBLP BibTeX RDF
27	Samir Datta, Meena Mahajan, B. V. Raghavendra Rao, Michael Thomas 0001, Heribert Vollmer	Counting Classes and the Fine Structure between NC1 and L.	MFCS	2010	DBLP DOI BibTeX RDF
27	Andreas Krebs, Nutan Limaye, Meena Mahajan	Counting Paths in VPA Is Complete for #NC1.	COCOON	2010	DBLP DOI BibTeX RDF
27	Liliana Cojocaru, Erkki Mäkinen, Ferucio Laurentiu Tiplea	Classes of Szilard Languages in NC1.	SYNASC	2009	DBLP DOI BibTeX RDF
27	Alexander Healy	Randomness-Efficient Sampling within NC1.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	68Q15, 68R10, Subject classification. 68Q10
27	Meena Mahajan	Polynomial Size Log Depth Circuits: Between NC1 and AC1.	Bull. EATCS	2007	DBLP BibTeX RDF
27	Eric Allender, Samir Datta, Sambuddha Roy	Topology inside NC1	Electron. Colloquium Comput. Complex.	2004	DBLP BibTeX RDF
27	Ran Raz	Multilinear-NC1 != Multilinear-NC2	Electron. Colloquium Comput. Complex.	2004	DBLP BibTeX RDF
27	Andrew Chiu, George I. Davida, Bruce E. Litow	Division in logspace-uniform NC1.	RAIRO Theor. Informatics Appl.	2001	DBLP DOI BibTeX RDF
27	Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer	Nondeterministic NC1 Computation.	J. Comput. Syst. Sci.	1998	DBLP DOI BibTeX RDF
27	François Pitt	A quantifier-free theory based on a string algebra for NC1.	Proof Complexity and Feasible Arithmetics	1996	DBLP DOI BibTeX RDF
27	Stephen Cook	Relating the provable collapse of P to NC1 and the power of logical theories.	Proof Complexity and Feasible Arithmetics	1996	DBLP DOI BibTeX RDF
27	Sarnath Ramnath	DTML is Logspace Hard under NC1 Reductions.	Parallel Process. Lett.	1992	DBLP DOI BibTeX RDF
27	Oscar H. Ibarra, Tao Jiang 0001, Bala Ravikumar	Some Subclasses of Context-Free Languages In NC1.	Inf. Process. Lett.	1988	DBLP DOI BibTeX RDF
27	David A. Mix Barrington, Neil Immerman, Howard Straubing	On uniformity within NC1.	SCT	1988	DBLP DOI BibTeX RDF
16	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
16	Craig Gentry	Fully homomorphic encryption using ideal lattices.	STOC	2009	DBLP DOI BibTeX RDF	fully homomorphic encryption
16	Michael Elberfeld, Till Tantau	Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.	MFCS	2008	DBLP DOI BibTeX RDF	circuit classes, computational complexity, bioinformatics, haplotyping, perfect phylogenies
16	Michael Benedikt, Leonid Libkin, Frank Neven	Logical definability and query languages over ranked and unranked trees.	ACM Trans. Comput. Log.	2007	DBLP DOI BibTeX RDF	Ranked trees, unranked trees, query languages, tree automata, model theory
16	Fabian Wagner	Hardness Results for Tournament Isomorphism and Automorphism.	MFCS	2007	DBLP DOI BibTeX RDF
16	Vladimir Lifschitz, Alexander A. Razborov	Why are there so many loop formulas?	ACM Trans. Comput. Log.	2006	DBLP DOI BibTeX RDF	loop formulas, stable models, P-completeness, Answer sets
16	Benny Applebaum, Yuval Ishai, Eyal Kushilevitz	Computationally Private Randomizing Polynomials and Their Applications.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	Subject classification. 94A60, 68P25, 68Q15
16	Amitabha Roy 0001, Howard Straubing	Definability of Languages by Generalized First-Order Formulas over (N, +).	STACS	2006	DBLP DOI BibTeX RDF
16	Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu	Learning a circuit by injecting values.	STOC	2006	DBLP DOI BibTeX RDF	learning, circuit, gene regulatory network
16	Steven Perron	A Propositional Proof System for Log Space.	CSL	2005	DBLP DOI BibTeX RDF
16	Kung Fu Ng, Wei Hong Yang	Regularities and their relations to error bounds.	Math. Program.	2004	DBLP DOI BibTeX RDF	epigraph, linearly regular, property (G), strong CHIP, tangent cone, positive linear functional, graph, regular, error bound, normal cone, multifunction
16	Alina Beygelzimer, Mitsunori Ogihara	The Enumerability of P Collapses P to NC.	MFCS	2004	DBLP DOI BibTeX RDF
16	Eric Allender, Vikraman Arvind, Meena Mahajan	Arithmetic Complexity, Kleene Closure, and Formal Power Series.	Theory Comput. Syst.	2003	DBLP DOI BibTeX RDF
16	Fabrice Noilhan, Miklos Santha	Semantical Counting Circuits.	Theory Comput. Syst.	2003	DBLP DOI BibTeX RDF
16	Leonid Libkin, Frank Neven	Logical Definability and Query Languages over Unranked Trees.	LICS	2003	DBLP DOI BibTeX RDF
16	Rahul Santhanam, Dieter van Melkebeek	Holographic Proofs and Derandomization.	CCC	2003	DBLP DOI BibTeX RDF
16	Yuval Ishai, Eyal Kushilevitz	Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials.	ICALP	2002	DBLP DOI BibTeX RDF
16	Massimiliano Goldwurm, Beatrice Palano, Massimo Santini 0001	On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages.	STACS	2001	DBLP DOI BibTeX RDF	Uniform random generation, ambiguous context-free languages, auxiliary pushdown automata, circuit complexity
16	Michal Koucký 0001	Log-Space Constructible Universal Traversal Sequences for Cycles of Length O(n4.03).	COCOON	2001	DBLP DOI BibTeX RDF
16	Manindra Agrawal	The First-Order Isomorphism Theorem.	FSTTCS	2001	DBLP DOI BibTeX RDF
16	Manindra Agrawal	Towards Uniform AC0 - Isomorphisms.	CCC	2001	DBLP DOI BibTeX RDF
16	Eric Allender, Michal Koucký 0001, Detlef Ronneburger, Sambuddha Roy, V. Vinay	Time-Space Tradeoffs in the Counting Hierarchy.	CCC	2001	DBLP DOI BibTeX RDF
16	Donald Beaver	Minimal-Latency Secure Function Evaluation.	EUROCRYPT	2000	DBLP DOI BibTeX RDF
16	Iannis Tourlakis	Time-Space Lower Bounds for SAT on Uniform and Non-Uniform Machines.	CCC	2000	DBLP DOI BibTeX RDF
16	David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie	On the Complexity of Some Problems on Groups Input as Multiplication Tables.	CCC	2000	DBLP DOI BibTeX RDF	logic, circuit complexity, group membership, integer arithmetic
16	Jun Tarui, Seinosuke Toda	Some Observations on the Computational Complexity of Graph Accessibility Problem.	COCOON	1999	DBLP DOI BibTeX RDF
16	David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum	On Monotone Planar Circuits.	CCC	1999	DBLP DOI BibTeX RDF
16	Markus Holzer 0001	Multi-Head Finite Automata: Data-Independent Versus Data-Dependent Computations.	MFCS	1997	DBLP DOI BibTeX RDF
16	Ronald V. Book, Heribert Vollmer, Klaus W. Wagner	On Type-2 Probabilistic Quantifiers.	ICALP	1996	DBLP DOI BibTeX RDF
16	Sorin Istrail, Dejan Zivkovic	A Non-Probabilistic Switching Lemma for the Sipser Function.	STACS	1993	DBLP DOI BibTeX RDF
16	Michael Kharitonov	Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution.	COLT	1992	DBLP DOI BibTeX RDF
16	Shang-Hua Teng	Functional Inversion and Communication Complexity.	CRYPTO	1991	DBLP DOI BibTeX RDF