5 papers
No Perfect Randomized Composition
Alexander Meiburg
Does computing a composition of total Boolean functions require the product of the randomized query complexities of its factors? We give a negative answer. There are families of to…
Constant Rate Codes with Fully Addressable Transversal T: Good Codes, Sparse Checks
Alexander Meiburg
Recent work by Wills constructed codes with constant rate and transversal . Extending this line of work, we construct asymptotically good CSS codes with \textbf{fully addressabl…
Block Sensitivity can exceed Spectral Sensitivity Squared
Alexander Meiburg
The spectral sensitivity of a Boolean function is the largest eigenvalue of the adjacency matrix of its sensitivity graph. It lower-bounds every standard measure of query co…
Bounding the Graph Capacity with Quantum Mechanics and Finite Automata
Alexander Meiburg
The zero-error capacity of a channel (or Shannon capacity of a graph) quantifies how much information can be transmitted with no risk of error. In contrast to the Shannon capacity…
Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography
Alex Meiburg
Matrix permanents are hard to compute or even estimate in general. It had been previously suggested that the permanents of Positive Semidefinite (PSD) matrices may have efficient a…