Projects per year
Fingerprint Dive into the research topics where Eric Allender is active. These topic labels come from the works of this person. Together they form a unique fingerprint.
- 2 Similar Profiles
Networks (circuits)
Engineering & Materials Science
Polynomials
Engineering & Materials Science
Kolmogorov Complexity
Mathematics
Complexity Classes
Mathematics
Arithmetic Circuits
Mathematics
Lower bound
Mathematics
Circuit Complexity
Mathematics
Strings
Mathematics
Network
Recent external collaboration on country level. Dive into details by clicking on the dots.
Projects 2008 2016
- 3 Finished
Eager: Af: New Approaches To Hardness For Circuit Minimization
National Science Foundation (NSF)
9/1/15 → 8/31/16
Project: Research project
Hardness
Networks (circuits)
Computational complexity
Public key cryptography
Af: Medium: Computational Complexity Theory And Circuit Complexity
National Science Foundation (NSF)
6/1/11 → 5/31/14
Project: Research project
Computational complexity
Networks (circuits)
Public key cryptography
Education
Concretes
Computational Complexity Theory And Circuit Complexity
National Science Foundation (NSF)
8/1/08 → 7/31/12
Project: Research project
Computational complexity
Networks (circuits)
Amplification
Numerical analysis
Research Output 1985 2019
Better Complexity Bounds for Cost Register Automata
Allender, E., Krebs, A. & McKenzie, P., Apr 15 2019, In : Theory of Computing Systems. 63, 3, p. 367-385 19 p.Research output: Contribution to journal › Article
Semiring
Automata
Costs
Finite automata
Complexity Theory
Syntactic separation of subset satisfiability problems
Allender, E., Farach-Colton, M. & Tsai, M. T., Sep 2019, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019. Achlioptas, D. & Vegh, L. A. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 16. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 145).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Syntactics
Hardness
Computational geometry
Graph theory
The non-hardness of approximating circuit size
Allender, E., Ilango, R. & Vafa, N., Jan 1 2019, Computer Science – Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Proceedings. van Bevern, R. & Kucherov, G. (eds.). Springer Verlag, p. 13-24 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11532 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Networks (circuits)
Hardness
Weak Approximation
Turing
Approximation
5
Citations
(Scopus)
Minimum circuit size, graph isomorphism, and related problems
Allender, E., Grochow, J. A., Van Melkebeek, D., Moore, C. & Morgan, A., Jan 1 2018, In : SIAM Journal on Computing. 47, 4, p. 1339-1372 34 p.Research output: Contribution to journal › Article
Graph Isomorphism
Conjugacy
Networks (circuits)
Encoding
Interactive Proof Systems
1
Citation
(Scopus)
Minimum circuit size, graph isomorphism, and related problems
Allender, E., Grochow, J. A., Van Melkebeek, D., Moore, C. & Morgan, A., Jan 1 2018, 9th Innovations in Theoretical Computer Science, ITCS 2018. Karlin, A. R. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 20. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 94).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
Networks (circuits)
Hardness