If you made any changes in Pure, your changes will be visible here soon.

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.

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

Hardness
Networks (circuits)
Computational complexity
Public key cryptography
Computational complexity
Networks (circuits)
Public key cryptography
Education
Concretes
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 journalArticle

Semiring
Automata
Costs
Finite automata
Complexity 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. Kucherov, G. & van Bevern, R. (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 proceedingConference contribution

Networks (circuits)
Hardness
Weak Approximation
Turing
Approximation
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 proceedingConference contribution

Networks (circuits)
Hardness
3 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 journalArticle

Graph Isomorphism
Conjugacy
Networks (circuits)
Encoding
Interactive Proof Systems
1 Citation (Scopus)

Better complexity bounds for cost register automata

Allender, E., Krebs, A. & McKenzie, P., Nov 1 2017, 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017. Larsen, K. G., Raskin, J-F. & Bodlaender, H. L. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, (Leibniz International Proceedings in Informatics, LIPIcs; vol. 83).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Costs
Finite automata
Polynomials
Networks (circuits)