Showing 2023Show all
3 papers · 1 filter
cs.CC2023
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…
cs.CC2023
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,…
cs.GT2023
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…