516 citations · 2.7k across the 47 of their papers we have counts for
6 papers · 1 filter
On the Probabilistic Degree of OR over the Reals
Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli +1
We study the probabilistic degree over reals of the OR function on variables. For an error parameter in (0,1/3), the -error probabilistic degree of any Boolean function…
Origins of diamond surface noise probed by correlating single spin measurements with surface spectroscopy
Sorawis Sangtawesin, Bo L. Dwyer, Srikanth Srinivasan +15
The nitrogen vacancy (NV) center in diamond exhibits spin-dependent fluorescence and long spin coherence times under ambient conditions, enabling applications in quantum informatio…
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…
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…
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan
We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear num…
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…