9 papers
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…
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…
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…
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…
Fourier Entropy-Influence Conjecture for Random Linear Threshold Functions
Sourav Chakraborty, Sushrut Karmalkar, Srijita Kundu +2
The Fourier-Entropy Influence (FEI) Conjecture states that for any Boolean function , the Fourier entropy of is at most its influence up to a unive…
Improved bounds on Fourier entropy and Min-entropy
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký +2
Given a Boolean function , the Fourier distribution assigns probability to . The Fourier Entropy-Influence (FEI) conjec…
Optimal Quasi-Gray Codes: The Alphabet Matters
Diptarka Chakraborty, Debarati Das, Michal Koucký +1
A quasi-Gray code of dimension and length over an alphabet is a sequence of distinct words from such that any two consecutive words diff…