3 papers
cs.CC2026
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…
cs.IT2024
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…
quant-ph2021
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…