From the 1 of 10 linked papers with an AI index.
10 papers
On Lower Bounds for AND via Torus Polynomials
Vaibhav Krishan, Jayalal Sarma
The paper uses torus polynomial approximations to prove exponential size lower bounds for symmetric CC^0 circuits computing the AND function and provides degree upper bounds for ce…
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…
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…
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…