Papers

This page contains some papers produced during the academic year of 2023-2024.

  • Robert Andrews and Avi Wigderson; Constant-Depth Arithmetic Circuits for Linear Algebra Problems. 2024. arXiv:2404.10839.
  • Jason M. Altschuler and Sinho Chewi; Shifted Composition I: Harnack and Reverse Transport Inequalities. arXiv preprint 2311.14520, 2023.
  • Jason M. Altschuler and Sinho Chewi; Shifted Composition II: Shift Harnack Inequalities and Curvature Upper Bounds. arXiv preprint 2401.00071, 2023.
  • Nima Anari, Sinho Chewi, and Thuy-Duong Vuong; Fast Parallel Sampling Under Isoperimetry. arXiv preprint 2401.09016, 2024.
  • Sinho Chewi; Log-concave Sampling. Forthcoming, 2024. Available online at: chewisinho.github.io.
  • Sinho Chewi, Jonathan Niles-Weed, and Philippe Rigollet; Statistical Optimal Transport.  Forthcoming, 2024; St. Flour lecture notes.
  • Yiheng Jiang, Sinho Chewi, and Aram-Alexandre Pooladian; Algorithms for Mean-field Variational Inference via Polyhedral Optimization in the Wasserstein Space. preprint 2312.02849, 2023.
  • Yunbum Kook, Matthew S. Zhang, Sinho Chewi, Murat A. Erdogdu, and Mufan (Bill) Li.; Sampling from the Mean-field Stationary Distribution.  arXiv preprint 2402.07355, 2024.
  • Dikstein, Y., Liu, S., & Wigderson, A.; Sparser Coboundary and Spectral Abelian HDXs. In preparation. 2024.
  • Ben Yaacov, I., Dikstein, Y. & Maor, G.; Sparse High Dimensional Expanders via Local Lifts. arXiv:2405.19191. 2024.
  • Dikstein, Y. & Dinur, I.; Agreement Theorems for High Dimensional Expanders in the Small Soundness Regime: The Role of Covers. Proceedings of The 56th Annual ACM SIGACT Symposium On Theory Of Computing, STOC 2024.
  • Dikstein, Y. & Dinur, I.; Swap Cosystolic Expansion. Proceedings of The 56th Annual ACM SIGACT Symposium On Theory Of Computing, STOC 2024.
  • Dikstein, Y., Dinur, I., & Lubotzky, A.; Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs. arXiv:2402.01078. 2024.
  • Jannis Blauth, Nathan Klein, and Martin Nägele; A Better-Than-1.6-Approximation for Prize-Collecting TSP. 2024. arXiv:2308.06254 [cs.DS].
  • Leonid Gurvits, Nathan Klein, and Jonathan Leake; From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP. 2024. arXiv:2311.09072 [math.CO].
  • D. Ellis Hershkowitz, Nathan Klein, and Rico Zenklusen; Ghost Value Augmentation for k-Edge-Connectivity. 2024. arXiv:2311.09941 [cs.DS].
  • Billy Jin, Nathan Klein, and David P. Williamson; A Lower Bound for the Max Entropy Algorithm for TSP. 2023. arXiv:2311.01950 [cs.DS].
  • M. Bafna, J. T. Hsieh, and P. K. Kothari; Rounding Large Independent Sets on Expanders. 2024.
  • Bakshi, P. Kothari, G. Rajendran, M. Tulsiani, and A. Vijayaraghavan; Efficient Certificates of Anti-Concentration Beyond Gaussians. In FOCS, 2024.
  • J. Błasiok, R.D. Buhai, P.K. Kothari, and D.Steurer; Semirandom Planted Clique and the Restricted Isometry Property.  In FOCS, 2024.
  • P. K. Kothari and P. Manohar; An Exponential Lower Bound for Linear 3-query Locally Correctable Codes. In B. Mohar, I. Shinkar, and R. O'Donnell, editors, Proceedings of the 56th Annual (ACM) Symposium on Theory of Computing, (STOC) 2024, Vancouver, BC, Canada, June 24-28, 2024}, pages 776--787. (ACM), 2024.
  • P. K. Kothari and P. Manohar; Superpolynomial Lower Bounds for Smooth 3-lccs and Sharp Bounds for Designs. In FOCS (to appear), 2024.
  • Jambulapati, Arun and Lee, James R and Liu, Yang P and Sidford, Aaron; Sparsifying Generalized Linear Models. arXiv preprint: arXiv:2311.18145. To appear in STOC 2024.
  • Chen, Li and Kyng, Rasmus and Liu, Yang P and Meierhans, Simon and Gutenberg, Maximilian Probst; Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow. arXiv preprint: arXiv:2311.18295. To appear in STOC 2024.
  • Liu, Yang P.; On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication. arXiv preprint: arXiv:2403.02582. 2024. In submission.
  • Bhangale, Amey and Braverman, Mark and Khot, Subhash and Liu, Yang P and Minzer, Dor; Parallel Repetition of k-Player Projection Games. arXiv preprint arXiv:2312.04783. 2023. In submission.
  • V. Reis and T. Rothvoss; The Subspace Flatness Conjecture and Faster Integer Programming in 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), Santa Cruz, CA, USA, 2023 pp. 974-988.
  • J. Kulkarni, V. Reis and T. Rothvoss; Optimal Online Discrepancy Minimization.  In Proceedings of the 56rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2024), to appear.
  • Jerome Zuiddam and Avi Wigderson;  Asymptotic Spectra: Theory, Applications and Extensions. 2024. In submission.
  • Peter Bürgisser and Mahmut Levent Doğan and Visu Makam and Michael Walter and Avi Wigderson. Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture. 2024. arXiv:2405.15368.