- About
- Events
- Calendar
- Graduation Information
- Cornell Learning Machines Seminar
- Student Colloquium
- BOOM
- Fall 2024 Colloquium
- Conway-Walker Lecture Series
- Salton 2024 Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University - High School Programming Contests 2024
- Game Design Initiative
- CSMore: The Rising Sophomore Summer Program in Computer Science
- Explore CS Research
- ACSU Research Night
- Cornell Junior Theorists' Workshop 2024
- People
- Courses
- Research
- Undergraduate
- M Eng
- MS
- PhD
- Admissions
- Current Students
- Computer Science Graduate Office Hours
- Advising Guide for Research Students
- Business Card Policy
- Cornell Tech
- Curricular Practical Training
- A & B Exam Scheduling Guidelines
- Fellowship Opportunities
- Field of Computer Science Ph.D. Student Handbook
- Graduate TA Handbook
- Field A Exam Summary Form
- Graduate School Forms
- Instructor / TA Application
- Ph.D. Requirements
- Ph.D. Student Financial Support
- Special Committee Selection
- Travel Funding Opportunities
- Travel Reimbursement Guide
- The Outside Minor Requirement
- Diversity and Inclusion
- Graduation Information
- CS Graduate Minor
- Outreach Opportunities
- Parental Accommodation Policy
- Special Masters
- Student Spotlights
- Contact PhD Office
Recursive Lattice Reduction
Abstract: We propose a new framework called recursive lattice reduction for finding short non-zero vectors in a lattice or for finding dense sublattices of a lattice. At a high level, the framework works by recursively searching for dense sublattices of dense sublattices (or their duals) with progressively lower rank. We view this new framework as complementary to basis reduction algorithms; it provides an alternative and arguably simpler perspective which can be described without explicitly referencing any specific basis of the lattice.
Our main concrete result is an efficient reduction from the approximate Densest Sublattice Problem to exact (Hermite) Shortest Vector Problem in dimension k that matches the tradeoff between k, input dimension n, and approximation factor \gamma achieved by the best-known basis reduction algorithms (in terms of the Hermite factor, up to low-order terms) across all parameter regimes. In fact, this reduction also can be used to find dense sublattices with relatively large rank, which is a novel result (as far as we know). Additionally, we present an automated approach for searching for algorithms in this framework that (provably) achieve better approximations with fewer oracle calls.
Bio: Spencer Peters is a 5th year PhD student in Cornell CIS, advised by Noah Stephens-Davidowitz. He is broadly interested in the intersection of cryptography and algorithms, with a particular focus on lattice algorithms.