2 citations · 2 across the 10 of their papers we have counts for
20 papers
Optimal compression with quantum retrieval
Shyam Dhamapurkar, Mohit Garg, Manaswi Paraashar +1
We consider the following data compression problem. Given a string of Hamming weight at most , compress it into a shorter string so that any…
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…
Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal +2
In this short note, we initiate the study of the Linear Isomorphism Testing Problem in the setting of communication complexity, a natural linear algebraic generalization of the cla…
Testing Isomorphism of Boolean Functions over Finite Abelian Groups
Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal +2
Let and be Boolean functions over a finite Abelian group , where is fully known, and we have {\em query access} to , that is, given any $x \in \mathcal{…
Low Degree Local Correction Over the Boolean Cube
Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar +2
In this work, we show that the class of multivariate degree- polynomials mapping to any Abelian group is locally correctable with $\widetilde{O}_{d}((\log n)^{…
Quantum Advantage with Faulty Oracle
David Rasmussen Lolck, Laura Mančinska, Manaswi Paraashar
This paper investigates the impact of noise in the quantum query model, a fundamental framework for quantum algorithms. We focus on the scenario where the oracle is subject to non-…
Approximate Degree Composition for Recursive Functions
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal +2
Determining the approximate degree composition for Boolean functions remains a significant unsolved problem in Boolean function complexity. In recent decades, researchers have conc…
Local Correction of Linear Functions over the Boolean Cube
Prashanth Amireddy, Amik Raj Behera, Manaswi Paraashar +2
We consider the task of locally correcting, and locally list-correcting, multivariate linear functions over the domain over arbitrary fields and more generally Abelian…
On the communication complexity of finding a king in a tournament
Nikhil S. Mande, Manaswi Paraashar, Swagato Sanyal +1
A tournament is a complete directed graph. A king in a tournament is a vertex v such that every other vertex is reachable from v via a path of length at most 2. It is well known th…
Randomized and quantum query complexities of finding a king in a tournament
Nikhil S. Mande, Manaswi Paraashar, Nitin Saurabh
A tournament is a complete directed graph. It is well known that every tournament contains at least one vertex v such that every other vertex is reachable from v by a path of lengt…
Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal +2
Given Boolean functions \( f, g : \mathbb{F}_2^n \to \{-1,+1\} \), we say they are {\em linearly isomorphic} if there exists \( A \in \mathrm{GL}_n(\mathbb{F}_2) \) such that \( f(…
On the Composition of Randomized Query Complexity and Approximate Degree
Sourav Chakraborty, Chandrima Kayal, Rajat Mittal +3
For any Boolean functions and , the question whether , is known as the composition question for the randomized query complexity. Similarly,…
Solving Odd-Fair Parity Games
Irmak Sağlam, Anne-Kathrin Schmuck
This paper discusses the problem of efficiently solving parity games where player Odd has to obey an additional 'strong transition fairness constraint' on its vertices -- given tha…
Separations between Combinatorial Measures for Transitive Functions
Sourav Chakraborty, Chandrima Kayal, Manaswi Paraashar
The role of symmetry in Boolean functions has been extensively studied in complexity theory. For example, symmetric functions, that is, functions that are…
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…
Tight Chang's-lemma-type bounds for Boolean functions
Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal +3
Chang's lemma (Duke Mathematical Journal, 2002) is a classical result with applications across several areas in mathematics and computer science. For a Boolean function that ta…
Query Complexity of Global Minimum Cut
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra +1
In this work, we resolve the query complexity of global minimum cut problem for a graph by designing a randomized algorithm for approximating the size of minimum cut in a graph, wh…
Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh +2
The disjointness problem - where Alice and Bob are given two subsets of and they have to check if their sets intersect - is a central problem in the world of comm…
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…
Efficiently Sampling and Estimating from Substructures using Linear Algebraic Queries
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra +1
Given an unknown matrix having non-negative entries, the \emph{inner product} (IP) oracle takes as inputs a specified row (or a column) of and a vector $v \in…