3 papers
cs.CC2023
Explicit orthogonal and unitary designs
Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes
We give a strongly explicit construction of -approximate -designs for the orthogonal group and the unitary group , for . Our d…
cs.DS2020
Spectrum preserving short cycle removal on regular graphs
Pedro Paredes
We describe a new method to remove short cycles on regular graphs while maintaining spectral bounds (the nontrivial eigenvalues of the adjacency matrix), as long as the graphs have…
cs.DS2019
The SDP value for random two-eigenvalue CSPs
Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
We precisely determine the SDP value (equivalently, quantum value) of large random instances of certain kinds of constraint satisfaction problems, ``two-eigenvalue 2CSPs''. We show…