11 citations · 33 across the 22 of their papers we have counts for
25 papers
On Lower Bounds for AND via Torus Polynomials
Vaibhav Krishan, Jayalal Sarma
We explore a torus polynomial approximation based approach towards a long-standing question: whether can be computed by circuits - the class of constant-depth polynomi…
On the Reachability Problem on Monoid-Labelled Undirected Graphs
Nagashri Krishnakumar, Harshil Mittal, Jayalal Sarma
The labelled reachability problem for undirected graphs with edges labelled by elements of a monoid (more generally, groupoids or magmas) captures the classes and $\sf…
A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
Sutanay Bhattacharjee, Ameya Panse, Jayalal Sarma
Color refinement is an important technique that works very well in practice for the graph isomorphism problem. Tinhofer graphs are the class of graphs for which refinement together…
VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
Balagopal Komarath, Harshil Mittal, Jayalal Sarma
Arithmetic circuit complexity studies the complexity of computing polynomials using only arithmetic operations such as addition, multiplication, subtraction, and division. Polynomi…
On Condensation of Block Sensitivity, Certificate Complexity and the (and ) Decision Tree Complexity
Sai Soumya Nalli, Karthikeya Polisetty, Jayalal Sarma
Given an -bit Boolean function with a complexity measure (such as block sensitivity, query complexity, etc.) , the hardness condensation question asks whether can…
Bounds for Hardness Condensation in the Query Model
Chandrima Kayal, Rajat Mittal, Sai Soumya Nalli +4
For any Boolean function with a complexity measure having value , is it possible to restrict the function to variables while keeping t…