4 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…
Certificate Games and Consequences for the Classical Adversary Bound
Sourav Chakraborty, Anna Gál, Mika Göös +3
We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function va…
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…
Relations between monotone complexity measures based on decision tree complexity
Farzan Byramji, Vatsal Jha, Chandrima Kayal +1
In a recent result, Knop, Lovett, McGuire and Yuan (STOC 2021) proved the log-rank conjecture for communication complexity, up to log n factor, for any Boolean function composed wi…