26 citations · 26 across the 6 of their papers we have counts for
6 papers
On Top-Down and Local Lower Bounds for Circuits
Gülce Kardeş, Benjamin Rossman
Classical lower bounds for circuits proceed bottom-up by simplifying or approximating gates beginning at the input layer. We introduce a complementary top-down mode…
Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-2 Circuits and Lower Bounds
Joshua A. Grochow, Gülce Kardeş, Michael Levet
In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model. We prove the first circuit lower bounds for Group Is…
Universality in Collective Intelligence on the Rubik's Cube
David Krakauer, Gülce Kardeş, Joshua Grochow
Progress in understanding expert performance is limited by the scarcity of quantitative data on long-term knowledge acquisition and deployment. Here we use the Rubik's Cube as a co…
Physical Complexity of a Cognitive Artifact
Gülce Kardeş, David Krakauer, Joshua Grochow
Cognitive science and theoretical computer science both seek to classify and explain the difficulty of tasks. Mechanisms of intelligence are those that reduce task difficulty. Here…
Explaining Necessary Truths
Gülce Kardeş, Simon DeDeo
Knowing the truth is rarely enough -- we also seek out reasons why the fact is true. While much is known about how we explain contingent truths, we understand less about how we exp…
Thermodynamics of computations with absolute irreversibility, unidirectional transitions, and stochastic computation times
Gonzalo Manzano, Gülce Kardeş, Édgar Roldán +1
Developing a thermodynamic theory of computation is a challenging task at the interface of non-equilibrium thermodynamics and computer science. In particular, this task requires de…