2.5k citations · 4.7k across the 60 of their papers we have counts for
10 papers · 1 filter
Optimization Algorithms for Faster Computational Geometry
Zeyuan Allen-Zhu, Zhenyu Liao, Yang Yuan
We study two fundamental problems in computational geometry: finding the maximum inscribed ball (MaxIB) inside a bounded polyhedron defined by hyperplanes, and the minimum encl…
Johnson-Lindenstrauss Compression with Neuroscience-Based Constraints
Zeyuan Allen-Zhu, Rati Gelashvili, Silvio Micali +1
Johnson-Lindenstrauss (JL) matrices implemented by sparse random synaptic connections are thought to be a prime candidate for how convergent pathways in the brain compress informat…
Nearly Linear-Time Packing and Covering LP Solvers
Zeyuan Allen-Zhu, Lorenzo Orecchia
Packing and covering linear programs (PC-LPs) form an important class of linear programs (LPs) across computer science, operations research, and optimization. In 1993, Luby and Nis…
Restricted Isometry Property for General p-Norms
Zeyuan Allen-Zhu, Rati Gelashvili, Ilya Razenshteyn
The Restricted Isometry Property (RIP) is a fundamental property of a matrix which enables sparse recovery. Informally, an matrix satisfies RIP of order for the $\…
Using Optimization to Solve Positive LPs Faster in Parallel
Zeyuan Allen-Zhu, Lorenzo Orecchia
Positive linear programs (LP), also known as packing and covering linear programs, are an important class of problems that bridges computer science, operations research, and optimi…
Knightian Robustness from Regret Minimization
Alessandro Chiesa, Silvio Micali, Zeyuan Allen Zhu
We consider auctions in which the players have very limited knowledge about their own valuations. Specifically, the only information that a Knightian player has about the profi…
Knightian Robustness of Single-Parameter Domains
Alessandro Chiesa, Silvio Micali, Zeyuan Allen Zhu
We consider players that have very limited knowledge about their own valuations. Specifically, the only information that a Knightian player has about the profile of true valuat…
Knightian Analysis of the VCG Mechanism in Unrestricted Combinatorial Auctions
Alessandro Chiesa, Silvio Micali, Zeyuan Allen Zhu
We consider auctions in which the players have very limited knowledge about their own valuations. Specifically, the only information that a Knightian player has about the profi…
Bridging Utility Maximization and Regret Minimization
Alessandro Chiesa, Silvio Micali, Zeyuan Allen Zhu
We relate the strategy sets that a player ends up with after refining his own strategies according to two very different models of rationality: namely, utility maximization and reg…
Knightian Analysis of the Vickrey Mechanism
Alessandro Chiesa, Silvio Micali, Zeyuan Allen Zhu
We analyze the Vickrey mechanism for auctions of multiple identical goods when the players have both Knightian uncertainty over their own valuations and incomplete preferences. In…