4 papers
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…
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…
Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model
Kelsey A. Jackson, Carl A. Miller, Daochen Wang
In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant…
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…