63 citations · 88 across the 9 of their papers we have counts for
15 papers
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…
The Role of Symmetry in Quantum Query-to-Communication Simulation
Sourav Chakraborty, Arkadev Chattopadhyay, Peter Høyer +3
Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of…
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…
Quantum Query-to-Communication Simulation Needs a Logarithmic Overhead
Sourav Chakraborty, Arkadev Chattopadhyay, Nikhil S. Mande +1
Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function and the two-party bounded-erro…
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…