Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
120 | 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 |
93 | Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer |
Nondeterministic NC1 Computation. ![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. 12-21, 1996, IEEE Computer Society, 0-8186-7386-9. The full citation details ...](Pics/full.jpeg) |
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. ![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 |
|
82 | Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao |
Arithmetizing Classes Around NC 1 and L. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, pp. 477-488, 2007, Springer, 978-3-540-70917-6. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
66 | Hervé Caussinus, François Lemieux |
The Complexity of Computing over Quasigroups. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FSTTCS ![In: Foundations of Software Technology and Theoretical Computer Science, 14th Conference, Madras, India, December 15-17, 1994, Proceedings, pp. 36-47, 1994, Springer, 3-540-58715-2. The full citation details ...](Pics/full.jpeg) |
1994 |
DBLP DOI BibTeX RDF |
|
60 | Liliana Cojocaru |
Branching Programs, Grammar Systems and the NC1 Class. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SYNASC ![In: Proceedings of the Ninth International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2007, Timisoara, Romania, September 26-29, 2007, pp. 66-73, 2007, IEEE Computer Society, 978-0-7695-3078-9. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
60 | 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 |
|
60 | Tomas Sander, Adam L. Young, Moti Yung |
Non-Interactive CryptoComputing For NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FOCS ![In: 40th Annual Symposium on Foundations of Computer Science, FOCS '99, 17-18 October, 1999, New York, NY, USA, pp. 554-567, 1999, IEEE Computer Society, 0-7695-0409-4. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Arch. Math. Log. ![In: Arch. Math. Log. 44(6), pp. 711-749, 2005. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings, pp. 356-367, 2004, Springer, 3-540-22823-3. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
33 | Michal Koucký 0001 |
Circuit Complexity of Regular Languages. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. Syst. ![In: Theory Comput. Syst. 45(4), pp. 865-879, 2009. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP ![In: Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings, pp. 343-354, 2002, Springer, 3-540-43864-5. The full citation details ...](Pics/full.jpeg) |
2002 |
DBLP DOI BibTeX RDF |
|
33 | 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 |
|
33 | Bruno Poizat |
Une tentative malheureuse do construire une structure éliminant rapidement les quanteurs. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CSL ![In: Computer Science Logic, 14th Annual Conference of the EACSL, Fischbachau, Germany, August 21-26, 2000, Proceedings, pp. 61-70, 2000, Springer, 3-540-67895-6. The full citation details ...](Pics/full.jpeg) |
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. ![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 |
|
33 | Pierre McKenzie, Klaus Reinhardt, V. Vinay |
Circuits and Context-Free Languages. ![Search on Bibsonomy](Pics/bibsonomy.png) |
COCOON ![In: Computing and Combinatorics, 5th Annual International Conference, COCOON '99, Tokyo, Japan, July 26-28, 1999, Proceedings, pp. 194-203, 1999, Springer, 3-540-66200-6. The full citation details ...](Pics/full.jpeg) |
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. ![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. 88-96, 1996, IEEE Computer Society, 0-8186-7386-9. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ASIACRYPT (5) ![In: Advances in Cryptology - ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part V, pp. 3-32, 2023, Springer, 978-981-99-8732-0. The full citation details ...](Pics/full.jpeg) |
2023 |
DBLP DOI BibTeX RDF |
|
27 | Razvan Rosie |
Adaptively Secure Laconic Function Evaluation for NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CT-RSA ![In: Topics in Cryptology - CT-RSA 2022 - Cryptographers' Track at the RSA Conference 2022, Virtual Event, March 1-2, 2022, Proceedings, pp. 427-450, 2022, Springer, 978-3-030-95311-9. The full citation details ...](Pics/full.jpeg) |
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. ![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 |
|
27 | Lucas Kowalczyk, Hoeteck Wee |
Compact Adaptively Secure ABE for sf NC1 from k-Lin. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Cryptol. ![In: J. Cryptol. 33(3), pp. 954-1002, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
27 | Huijia Lin, Ji Luo 0002 |
Compact Adaptively Secure ABE from k-Lin: Beyond NC1 and towards NL. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IACR Cryptol. ePrint Arch. ![In: IACR Cryptol. ePrint Arch. 2020, pp. 318, 2020. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP BibTeX RDF |
|
27 | 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 |
|
27 | Huijia Lin, Ji Luo 0002 |
Compact Adaptively Secure ABE from k-Lin: Beyond NC1 and Towards NL. ![Search on Bibsonomy](Pics/bibsonomy.png) |
EUROCRYPT (3) ![In: Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part III, pp. 247-277, 2020, Springer, 978-3-030-45726-6. The full citation details ...](Pics/full.jpeg) |
2020 |
DBLP DOI BibTeX RDF |
|
27 | Daniel Grier, Luke Schaeffer |
Interactive shallow Clifford circuits: quantum advantage against NC1 and beyond. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CoRR ![In: CoRR abs/1911.02555, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
27 | Lucas Kowalczyk, Hoeteck Wee |
Compact Adaptively Secure ABE for NC1 from k-Lin. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IACR Cryptol. ePrint Arch. ![In: IACR Cryptol. ePrint Arch. 2019, pp. 224, 2019. The full citation details ...](Pics/full.jpeg) |
2019 |
DBLP BibTeX RDF |
|
27 | 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 |
|
27 | Nuttapong Attrapadung, Takahiro Matsuda 0002, Ryo Nishimaki, Shota Yamada 0001, Takashi Yamakawa |
Adaptively Single-Key Secure Constrained PRFs for NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IACR Cryptol. ePrint Arch. ![In: IACR Cryptol. ePrint Arch. 2018, pp. 1000, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
27 | Nuttapong Attrapadung, Takahiro Matsuda 0002, Ryo Nishimaki, Shota Yamada 0001, Takashi Yamakawa |
Constrained PRFs for NC1 in Traditional Groups. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IACR Cryptol. ePrint Arch. ![In: IACR Cryptol. ePrint Arch. 2018, pp. 154, 2018. The full citation details ...](Pics/full.jpeg) |
2018 |
DBLP BibTeX RDF |
|
27 | Ran Canetti, Yilei Chen 0001 |
Constraint-hiding Constrained PRFs for NC1 from LWE. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IACR Cryptol. ePrint Arch. ![In: IACR Cryptol. ePrint Arch. 2017, pp. 143, 2017. The full citation details ...](Pics/full.jpeg) |
2017 |
DBLP BibTeX RDF |
|
27 | Ran Canetti, Yilei Chen 0001 |
Constraint-Hiding Constrained PRFs for NC1 from LWE. ![Search on Bibsonomy](Pics/bibsonomy.png) |
EUROCRYPT (1) ![In: Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part I, pp. 446-476, 2017, 978-3-319-56619-1. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS (2) ![In: Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, pp. 384-394, 2015, Springer, 978-3-662-48053-3. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP DOI BibTeX RDF |
|
27 | Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig |
On Distinguishing NC1 and NL. ![Search on Bibsonomy](Pics/bibsonomy.png) |
DLT ![In: Developments in Language Theory - 19th International Conference, DLT 2015, Liverpool, UK, July 27-30, 2015, Proceedings., pp. 340-351, 2015, Springer, 978-3-319-21499-3. The full citation details ...](Pics/full.jpeg) |
2015 |
DBLP DOI BibTeX RDF |
|
27 | Eric Miles |
Iterated group products and leakage resilience against NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ITCS ![In: Innovations in Theoretical Computer Science, ITCS'14, Princeton, NJ, USA, January 12-14, 2014, pp. 261-268, 2014, ACM, 978-1-4503-2698-8. The full citation details ...](Pics/full.jpeg) |
2014 |
DBLP DOI BibTeX RDF |
|
27 | Eric Miles |
Iterated group products and leakage resilience against NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
IACR Cryptol. ePrint Arch. ![In: IACR Cryptol. ePrint Arch. 2013, pp. 815, 2013. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theor. Comput. Sci. ![In: Theor. Comput. Sci. 417, pp. 36-49, 2012. The full citation details ...](Pics/full.jpeg) |
2012 |
DBLP DOI BibTeX RDF |
|
27 | Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie |
Low uniform versions of NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR11, 2011. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP BibTeX RDF |
|
27 | Emil Jerábek |
On theories of bounded arithmetic for NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Ann. Pure Appl. Log. ![In: Ann. Pure Appl. Log. 162(4), pp. 322-340, 2011. The full citation details ...](Pics/full.jpeg) |
2011 |
DBLP DOI BibTeX RDF |
|
27 | Andreas Krebs, Nutan Limaye, Meena Mahajan |
Counting paths in VPA is complete for #NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR10, 2010. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR10, 2010. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010, Brno, Czech Republic, August 23-27, 2010. Proceedings, pp. 306-317, 2010, Springer, 978-3-642-15154-5. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
|
27 | Andreas Krebs, Nutan Limaye, Meena Mahajan |
Counting Paths in VPA Is Complete for #NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
COCOON ![In: Computing and Combinatorics, 16th Annual International Conference, COCOON 2010, Nha Trang, Vietnam, July 19-21, 2010. Proceedings, pp. 44-53, 2010, Springer, 978-3-642-14030-3. The full citation details ...](Pics/full.jpeg) |
2010 |
DBLP DOI BibTeX RDF |
|
27 | Liliana Cojocaru, Erkki Mäkinen, Ferucio Laurentiu Tiplea |
Classes of Szilard Languages in NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SYNASC ![In: 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2009, Timisoara, Romania, September 26-29, 2009, pp. 299-306, 2009, IEEE Computer Society, 978-1-4244-5910-0. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
|
27 | Alexander Healy |
Randomness-Efficient Sampling within NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Comput. Complex. ![In: Comput. Complex. 17(1), pp. 3-37, 2008. The full citation details ...](Pics/full.jpeg) |
2008 |
DBLP DOI BibTeX RDF |
68Q15, 68R10, Subject classification. 68Q10 |
27 | Meena Mahajan |
Polynomial Size Log Depth Circuits: Between NC1 and AC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Bull. EATCS ![In: Bull. EATCS 91, pp. 42-56, 2007. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP BibTeX RDF |
|
27 | Eric Allender, Samir Datta, Sambuddha Roy |
Topology inside NC1 ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR04, 2004. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP BibTeX RDF |
|
27 | Ran Raz |
Multilinear-NC1 != Multilinear-NC2 ![Search on Bibsonomy](Pics/bibsonomy.png) |
Electron. Colloquium Comput. Complex. ![In: Electron. Colloquium Comput. Complex. TR04, 2004. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP BibTeX RDF |
|
27 | Andrew Chiu, George I. Davida, Bruce E. Litow |
Division in logspace-uniform NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
RAIRO Theor. Informatics Appl. ![In: RAIRO Theor. Informatics Appl. 35(3), pp. 259-275, 2001. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
27 | Hervé Caussinus, Pierre McKenzie, Denis Thérien, Heribert Vollmer |
Nondeterministic NC1 Computation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
J. Comput. Syst. Sci. ![In: J. Comput. Syst. Sci. 57(2), pp. 200-212, 1998. The full citation details ...](Pics/full.jpeg) |
1998 |
DBLP DOI BibTeX RDF |
|
27 | François Pitt |
A quantifier-free theory based on a string algebra for NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Proof Complexity and Feasible Arithmetics ![In: Proof Complexity and Feasible Arithmetics, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, April 21-24, 1996, pp. 229-252, 1996, DIMACS/AMS, 978-0-8218-0577-0. The full citation details ...](Pics/full.jpeg) |
1996 |
DBLP DOI BibTeX RDF |
|
27 | Stephen Cook |
Relating the provable collapse of P to NC1 and the power of logical theories. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Proof Complexity and Feasible Arithmetics ![In: Proof Complexity and Feasible Arithmetics, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, April 21-24, 1996, pp. 73-91, 1996, DIMACS/AMS, 978-0-8218-0577-0. The full citation details ...](Pics/full.jpeg) |
1996 |
DBLP DOI BibTeX RDF |
|
27 | Sarnath Ramnath |
DTML is Logspace Hard under NC1 Reductions. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Parallel Process. Lett. ![In: Parallel Process. Lett. 2, pp. 189-193, 1992. The full citation details ...](Pics/full.jpeg) |
1992 |
DBLP DOI BibTeX RDF |
|
27 | Oscar H. Ibarra, Tao Jiang 0001, Bala Ravikumar |
Some Subclasses of Context-Free Languages In NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Inf. Process. Lett. ![In: Inf. Process. Lett. 29(3), pp. 111-117, 1988. The full citation details ...](Pics/full.jpeg) |
1988 |
DBLP DOI BibTeX RDF |
|
27 | David A. Mix Barrington, Neil Immerman, Howard Straubing |
On uniformity within NC1. ![Search on Bibsonomy](Pics/bibsonomy.png) |
SCT ![In: Proceedings: Third Annual Structure in Complexity Theory Conference, Georgetown University, Washington, D. C., USA, June 14-17, 1988, pp. 47-59, 1988, IEEE Computer Society, 0-8186-0794-7. The full citation details ...](Pics/full.jpeg) |
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. ![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 |
16 | Craig Gentry |
Fully homomorphic encryption using ideal lattices. ![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. 169-178, 2009, ACM, 978-1-60558-506-2. The full citation details ...](Pics/full.jpeg) |
2009 |
DBLP DOI BibTeX RDF |
fully homomorphic encryption |
16 | Michael Elberfeld, Till Tantau |
Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008, Torun, Poland, August 25-29, 2008, Proceedings, pp. 299-310, 2008, Springer, 978-3-540-85237-7. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ACM Trans. Comput. Log. ![In: ACM Trans. Comput. Log. 8(2), pp. 11, 2007. The full citation details ...](Pics/full.jpeg) |
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. ![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. 572-583, 2007, Springer, 978-3-540-74455-9. The full citation details ...](Pics/full.jpeg) |
2007 |
DBLP DOI BibTeX RDF |
|
16 | Vladimir Lifschitz, Alexander A. Razborov |
Why are there so many loop formulas? ![Search on Bibsonomy](Pics/bibsonomy.png) |
ACM Trans. Comput. Log. ![In: ACM Trans. Comput. Log. 7(2), pp. 261-268, 2006. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Comput. Complex. ![In: Comput. Complex. 15(2), pp. 115-162, 2006. The full citation details ...](Pics/full.jpeg) |
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, +). ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings, pp. 489-499, 2006, Springer, 978-3-540-32301-3. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
|
16 | Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu |
Learning a circuit by injecting values. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STOC ![In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pp. 584-593, 2006, ACM, 1-59593-134-1. The full citation details ...](Pics/full.jpeg) |
2006 |
DBLP DOI BibTeX RDF |
learning, circuit, gene regulatory network |
16 | Steven Perron |
A Propositional Proof System for Log Space. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CSL ![In: Computer Science Logic, 19th International Workshop, CSL 2005, 14th Annual Conference of the EACSL, Oxford, UK, August 22-25, 2005, Proceedings, pp. 509-524, 2005, Springer, 3-540-28231-9. The full citation details ...](Pics/full.jpeg) |
2005 |
DBLP DOI BibTeX RDF |
|
16 | Kung Fu Ng, Wei Hong Yang |
Regularities and their relations to error bounds. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Math. Program. ![In: Math. Program. 99(3), pp. 521-538, 2004. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings, pp. 346-355, 2004, Springer, 3-540-22823-3. The full citation details ...](Pics/full.jpeg) |
2004 |
DBLP DOI BibTeX RDF |
|
16 | Eric Allender, Vikraman Arvind, Meena Mahajan |
Arithmetic Complexity, Kleene Closure, and Formal Power Series. ![Search on Bibsonomy](Pics/bibsonomy.png) |
Theory Comput. Syst. ![In: Theory Comput. Syst. 36(4), pp. 303-328, 2003. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
16 | 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 |
|
16 | Leonid Libkin, Frank Neven |
Logical Definability and Query Languages over Unranked Trees. ![Search on Bibsonomy](Pics/bibsonomy.png) |
LICS ![In: 18th IEEE Symposium on Logic in Computer Science (LICS 2003), 22-25 June 2003, Ottawa, Canada, Proceedings, pp. 178-187, 2003, IEEE Computer Society, 0-7695-1884-2. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
16 | Rahul Santhanam, Dieter van Melkebeek |
Holographic Proofs and Derandomization. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark, pp. 269-283, 2003, IEEE Computer Society, 0-7695-1879-6. The full citation details ...](Pics/full.jpeg) |
2003 |
DBLP DOI BibTeX RDF |
|
16 | Yuval Ishai, Eyal Kushilevitz |
Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP ![In: Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings, pp. 244-256, 2002, Springer, 3-540-43864-5. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 2001, 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001, Proceedings, pp. 305-316, 2001, Springer, 3-540-41695-1. The full citation details ...](Pics/full.jpeg) |
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). ![Search on Bibsonomy](Pics/bibsonomy.png) |
COCOON ![In: Computing and Combinatorics, 7th Annual International Conference, COCOON 2001, Guilin, China, August 20-23, 2001, Proceedings, pp. 11-20, 2001, Springer, 3-540-42494-6. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
16 | Manindra Agrawal |
The First-Order Isomorphism Theorem. ![Search on Bibsonomy](Pics/bibsonomy.png) |
FSTTCS ![In: FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 21st Conference, Bangalore, India, December 13-15, 2001, Proceedings, pp. 70-82, 2001, Springer, 3-540-43002-4. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
16 | 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 |
|
16 | Eric Allender, Michal Koucký 0001, Detlef Ronneburger, Sambuddha Roy, V. Vinay |
Time-Space Tradeoffs in the Counting Hierarchy. ![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. 295-302, 2001, IEEE Computer Society, 0-7695-1053-1. The full citation details ...](Pics/full.jpeg) |
2001 |
DBLP DOI BibTeX RDF |
|
16 | Donald Beaver |
Minimal-Latency Secure Function Evaluation. ![Search on Bibsonomy](Pics/bibsonomy.png) |
EUROCRYPT ![In: Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding, pp. 335-350, 2000, Springer, 3-540-67517-5. The full citation details ...](Pics/full.jpeg) |
2000 |
DBLP DOI BibTeX RDF |
|
16 | Iannis Tourlakis |
Time-Space Lower Bounds for SAT on Uniform and Non-Uniform Machines. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 22-, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000, pp. 62-69, 2000, IEEE Computer Society, 0-7695-0674-7. The full citation details ...](Pics/full.jpeg) |
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. ![Search on Bibsonomy](Pics/bibsonomy.png) |
COCOON ![In: Computing and Combinatorics, 5th Annual International Conference, COCOON '99, Tokyo, Japan, July 26-28, 1999, Proceedings, pp. 18-30, 1999, Springer, 3-540-66200-6. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
16 | David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum |
On Monotone Planar Circuits. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CCC ![In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, Atlanta, Georgia, USA, May 4-6, 1999, pp. 24-, 1999, IEEE Computer Society, 0-7695-0075-7. The full citation details ...](Pics/full.jpeg) |
1999 |
DBLP DOI BibTeX RDF |
|
16 | Markus Holzer 0001 |
Multi-Head Finite Automata: Data-Independent Versus Data-Dependent Computations. ![Search on Bibsonomy](Pics/bibsonomy.png) |
MFCS ![In: Mathematical Foundations of Computer Science 1997, 22nd International Symposium, MFCS'97, Bratislava, Slovakia, August 25-29, 1997, Proceedings, pp. 299-308, 1997, Springer, 3-540-63437-1. The full citation details ...](Pics/full.jpeg) |
1997 |
DBLP DOI BibTeX RDF |
|
16 | Ronald V. Book, Heribert Vollmer, Klaus W. Wagner |
On Type-2 Probabilistic Quantifiers. ![Search on Bibsonomy](Pics/bibsonomy.png) |
ICALP ![In: Automata, Languages and Programming, 23rd International Colloquium, ICALP96, Paderborn, Germany, 8-12 July 1996, Proceedings, pp. 369-380, 1996, Springer, 3-540-61440-0. The full citation details ...](Pics/full.jpeg) |
1996 |
DBLP DOI BibTeX RDF |
|
16 | Sorin Istrail, Dejan Zivkovic |
A Non-Probabilistic Switching Lemma for the Sipser Function. ![Search on Bibsonomy](Pics/bibsonomy.png) |
STACS ![In: STACS 93, 10th Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25-27, 1993, Proceedings, pp. 566-575, 1993, Springer, 3-540-56503-5. The full citation details ...](Pics/full.jpeg) |
1993 |
DBLP DOI BibTeX RDF |
|
16 | Michael Kharitonov |
Cryptographic Lower Bounds for Learnability of Boolean Functions on the Uniform Distribution. ![Search on Bibsonomy](Pics/bibsonomy.png) |
COLT ![In: Proceedings of the Fifth Annual ACM Conference on Computational Learning Theory, COLT 1992, Pittsburgh, PA, USA, July 27-29, 1992., pp. 29-36, 1992, ACM, 0-89791-497-X. The full citation details ...](Pics/full.jpeg) |
1992 |
DBLP DOI BibTeX RDF |
|
16 | Shang-Hua Teng |
Functional Inversion and Communication Complexity. ![Search on Bibsonomy](Pics/bibsonomy.png) |
CRYPTO ![In: Advances in Cryptology - CRYPTO '91, 11th Annual International Cryptology Conference, Santa Barbara, California, USA, August 11-15, 1991, Proceedings, pp. 232-241, 1991, Springer, 3-540-55188-3. The full citation details ...](Pics/full.jpeg) |
1991 |
DBLP DOI BibTeX RDF |
|