The FacetedDBLP logo    Search for: in:

Disable automatic phrases ?     Syntactic query expansion: ?

Searching for NC1 with no syntactic query expansion in all metadata.

Publication years (Num. hits)
1988-1997 (15) 1998-2001 (17) 2002-2006 (18) 2007-2010 (15) 2011-2020 (18) 2021-2023 (3)
Publication types (Num. hits)
article(33) incollection(1) inproceedings(52)
GrowBag graphs for keyword ? (Num. hits/coverage)

Group by:
The graphs summarize 47 occurrences of 39 keywords

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