6 citations · 13 across the 3 of their papers we have counts for
5 papers
Topology inside NC
Eric Allender, Samir Datta, Arsenii Karnaukhov +3
We show that ACC is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, s…
Minimum Circuit Size, Graph Isomorphism, and Related Problems
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek +2
We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of…
Graph Isomorphism and Circuit Size
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek +2
It is well-known [KST93] that the complexity of the Graph Automorphism problem is characterized by a special case of Graph Isomorphism, where the input graphs satisfy the "promise"…
Reductions to the set of random strings: The resource-bounded case
Eric Allender, Harry Buhrman, Luke Friedman +1
This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we s…
Width-parameterized SAT: Time-Space Tradeoffs
Shiteng Chen, Tiancheng Lou, Periklis Papakonstantinou +1
Width parameterizations of SAT, such as tree-width and path-width, enable the study of computationally more tractable and practical SAT instances. We give two simple algorithms. On…