3 papers
cs.DS2026
Exponential Quantum Space Advantage for Approximating Max-SAT in the Streaming Setting
Haoyu Wang, Guangxu Yang
In this paper, we give a one-pass quantum streaming algorithm for Max-SAT that uses space and achieves a -approximation on instances with …
cs.LG2025
Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics
Sebastian Sanokowski, Wilhelm Berghammer, Martin Ennemoser +3
Learning to sample from complex unnormalized distributions over discrete domains emerged as a promising research direction with applications in statistical physics, variational inf…
cs.DS2024
Revisit the Partial Coloring Method: Prefix Spencer and Sampling
Dongrun Cai, Xue Chen, Wenxuan Shu +2
As the most powerful tool in discrepancy theory, the partial coloring method has wide applications in many problems including the Beck-Fiala problem and Spencer's celebrated result…