Research

Publications

• Just how hard are rotations of ℤ^n? Algorithms and cryptography with the simplest lattice Huck Bennett, Atul Ganju, Pura Peetathawatchai, and Noah Stephens-Davidowitz
  EUROCRYPT 2023 [Arxiv]
  Recent work suggests rotations of the integer lattice (ℤ^n) are optimal candidates for decoding due to their maximal smoothing parameter. Motivated by these findings, our research explored the feasibility of using ℤSVP — the problem of finding the shortest vector in a rotation of ℤ^n — as a foundation for building cryptography. Our work includes: (1) a novel algorithm for ℤSVP which improved upon the previous best proven running time, (2) a simple public-key encryption scheme relying on the computational hardness of a ℤSVP variant, (3) an algorithm for sampling a secure basis of ℤ^n if such a basis exists, (4) experiments evaluating basis reduction methods on bases of rotations of ℤ^n generated by various algorithms, including our secure basis sampling algorithm, and (5) performance analysis of heuristic sieving algorithms on ℤ^n.

Manuscripts/Working Manuscripts

• Active Learning via Regression Beyond Realizability
  Atul Ganju, Shashaank Aiyer, Ved Sriraman, and Karthik Sridharan
  In Submission [Arxiv]
  Previous works in active learning either reduce this problem to offline classification, a problem which is widely believed to be intractable, or reduce this problem to online/offline regression and in doing so rely on the assumption that the problem instance is realizable. We develop the first efficient algorithm for active classification with performance guarantees when the problem instance is not realizable. Our result hinges on an observation that offline classification reduces to offline regression whenever the benchmark function class is convex. We leverage this observation to develop an efficient epoch-based improper algorithm for online active learning which provably works under a significantly milder assumptions than realizability as long as the benchmark class is convex.

• Adaptive Rates for Interactive Decision Making Atul Ganju and Karthik Sridharan
  In Progress [Writeup]
  Recent work has been able to characterize the worst-case learnability of a general class of interactive decision making problems; however it fails to let learners incorporate their intuitions about the favorable properties of their problem instances into the algorithms they employ for decision making. We address this by developing a framework for constructing algorithms that attain adaptive regret bounds in this framework. We show that each adaptive rate induces an offset complexity measure, introducing bias towards models with the desired favorable property and leveraging information from prior observations, and when this complexity measure can be upper bounded by a small quantity the adaptive rate is achievable. So far, we have been able to recover the small-loss bound for contextual bandits and are working on generalizing our results to variance-aware bounds and other adaptive bounds.

• A Framework for Simple and Complex Contagion on Clustered Networks and its Implications
  Atul Ganju [Writeup]
  Inspired by several experimental results which suggest that the diffusion of behavior across social networks is a complex contagion process, we develop the first analytic framework for modeling complex contagion on a rich class of networks with varying local structure. Specifically, this framework models the final fraction of nodes in these network that adopt a contagion. Extensive experimental results validate the accuracy of the mathematical models for adoption generated by our framework and enabled us to provide answers to the following questions. How does a network’s local structure influence contagion dynamics? Do the propensities the nodes of a network have towards adoption of a contagion dictate the types of networks in which the contagion is more likely to spread? How the initial fraction of nodes starting with a contagion effect the likelihood of a global cascade?