1 citations · 2 across the 6 of their papers we have counts for
7 papers
The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
Yi-Jun Chang, Zeyong Li
In this paper, we present a low-diameter decomposition algorithm in the LOCAL model of distributed computing that succeeds with probability . Specifically, we show h…
Separating Key Agreement and Computational Differential Privacy
Vipul Arora, Eldon Chung, Zeyong Li +1
Two party differential privacy allows two parties who do not trust each other, to come together and perform a joint analysis on their data whilst maintaining individual-level priva…
Lattice Problems Beyond Polynomial Time
Divesh Aggarwal, Huck Bennett, Zvika Brakerski +6
We study the complexity of lattice problems in a world where algorithms, reductions, and protocols can run in superpolynomial time, revisiting four foundational results: two worst-…
A Computation Model with Automatic Functions and Relations as Primitive Operations
Ziyuan Gao, Sanjay Jain, Li Zeyong +2
Prior work of Hartmanis and Simon (Hartmanis and Simon, 1974) and Floyd and Knuth (Floyd and Knuth, 1990) investigated what happens if a device uses primitive steps more natural th…
Alternating Automatic Register Machines
Ziyuan Gao, Sanjay Jain, Zeyong Li +2
This paper introduces and studies a new model of computation called an Alternating Automatic Register Machine (AARM). An AARM possesses the basic features of a conventional registe…
Dimension-Preserving Reductions Between SVP and CVP in Different -Norms
Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +2
We show a number of reductions between the Shortest Vector Problem and the Closest…
A -Time Algorithm for -SVP and -Hermite SVP, and an Improved Time-Approximation Tradeoff for (H)SVP
Divesh Aggarwal, Zeyong Li, Noah Stephens-Davidowitz
We show a -time algorithm that finds a (non-zero) vector in a lattice with norm at most $\tilde{O}(\sqrt{n})\cdot \min\{λ_1(\mathca…