Showing 2026Show all
3 papers · 1 filter
cs.CC2026
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…
quant-ph2026
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…
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…