14 citations · 30 across the 18 of their papers we have counts for
Showing 2018 · cs.CCShow all
3 papers · 2 filters
cs.CC2018
A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates
Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush +2
We show that there is a randomized algorithm that, when given a small constant-depth Boolean circuit made up of gates that compute constant-degree Polynomial Threshold function…
cs.CC2018★ 14 cited
A Fixed-Depth Size-Hierarchy Theorem for AC via the Coin Problem
Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan +2
We prove the first Fixed-depth Size-hierarchy Theorem for uniform AC circuits; in particular, for fixed , the class of uniform AC for…
cs.CC2018
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
Suryajith Chillara, Christian Engels, Nutan Limaye +1
We study the size blow-up that is necessary to convert an algebraic circuit of product-depth to one of product-depth in the multilinear setting. We show that for every po…