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 |
|