63 citations · 88 across the 9 of their papers we have counts for
12 papers · 1 filter
Lifting to Parity Decision Trees Via Stifling
Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal +1
We show that the deterministic decision tree complexity of a (partial) function or relation lifts to the deterministic parity decision tree (PDT) size complexity of the compose…
Monotone Complexity of Spanning Tree Polynomial Re-visited
Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal +1
We prove two results that shed new light on the monotone complexity of the spanning tree polynomial, a classic polynomial in algebraic complexity and beyond. First, we show that th…
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on input…
Query-to-Communication Lifting Using Low-Discrepancy Gadgets
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth +2
Lifting theorems are theorems that relate the query complexity of a function to the communication complexity of the composed function , for…
Lower Bounds for Linear Decision Lists
Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande +1
We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions. We use this technique to prov…
Weights at the Bottom Matter When the Top is Heavy
Arkadev Chattopadhyay, Nikhil S. Mande
Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR of THR is a well-known open problem that represents a frontier of our understanding in bool…