5 citations · 25 across the 15 of their papers we have counts for
3 papers · 1 filter
New affine-invariant codes from lifting
Alan Guo, Swastik Kopparty, Madhu Sudan
In this work we explore error-correcting codes derived from the "lifting" of "affine-invariant" codes. Affine-invariant codes are simply linear codes whose coordinates are a vector…
Local reconstructors and tolerant testers for connectivity and diameter
Andrea Campagna, Alan Guo, Ronitt Rubinfeld
A local property reconstructor for a graph property is an algorithm which, given oracle access to the adjacency list of a graph that is "close" to having the property, provides ora…
Classic Nintendo Games are (Computationally) Hard
Greg Aloupis, Erik D. Demaine, Alan Guo +1
We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to generalized versi…