Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Gale-Berlekamp Game:
TR08-101 | 20th November 2008
Marek Karpinski, Warren Schudy

Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems

We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood ... more >>>

ISSN 1433-8092 | Imprint