Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NON-REDUNDANCY OF RELATIONS:
Reports tagged with Non-redundancy of relations:
TR26-077 | 15th May 2026
Joshua Brakensiek, Venkatesan Guruswami

Redundancy Is All You Need (for CSP Sparsification)

The seminal work of Benczu}r and Karger demonstrated cut sparsifiers of near-linear size, with several applications throughout theoretical computer science. Subsequent extensions have yielded sparsifiers for hypergraph cuts and more recently linear codes over Abelian groups. A decade ago, Kogan and Krauthgamer asked about the sparsifiability of arbitrary constraint satisfaction ... more >>>




ISSN 1433-8092 | Imprint