2 citations · 2 across the 10 of their papers we have counts for
4 papers · 1 filter
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…