3 papers
quant-ph2026
Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding
Amin Shiraz Gilani, Daochen Wang, Pei Wu +1
The edge list model is arguably the simplest input model for graphs, where the graph is specified by a list of its edges. In this model, we study the quantum query complexity of th…
cs.CC2026
Rational degree is polynomially related to degree
Robin Kothari, Matt Kovacs-Deak, Daochen Wang +1
We prove that for every Boolean function , where is the degree of and is the ra…
cs.CC2025
On the Rational Degree of Boolean Functions and Applications
Vishnu Iyer, Siddhartha Jain, Robin Kothari +5
We study a natural complexity measure of Boolean functions known as the rational degree. Denoted , it is the minimal degree of a rational function that is equal t…