Raghu Meka

collaborators

3 papers

cs.LG2025

Smoothed Agnostic Learning of Halfspaces over the Hypercube

Yiwen Kou, Raghu Meka

Agnostic learning of Boolean halfspaces is a fundamental problem in computational learning theory, but it is known to be computationally hard even for weak learning. Recent work [C…

cs.DM2025

Tight Lower Bound for Multicolor Discrepancy

Pasin Manurangsi, Raghu Meka

We prove the following asymptotically tight lower bound for $k$ -color discrepancy: For any $k \geq 2$ , there exists a hypergraph with $n$ hyperedges such that its $k$ -color discrep…

math.CO2025

Discrepancy Beyond Additive Functions with Applications to Fair Division

Alexandros Hollender, Pasin Manurangsi, Raghu Meka +1

We consider a setting where we have a ground set $M$ together with real-valued set functions $f_{1}, \dots, f_{n}$ , and the goal is to partition $M$ into two sets $S_{1}, S_{2}$ such that $…