Anindya De
Associate Professor and Graduate Chair (Computer and Information Science) at University of Pennsylvania

Areas of Interest:
Complexity theory, Analysis of Boolean functions, Learning theory, Applied probability

In the past:
  • Assistant Professor (Sep 2015 - Dec 2018), Computer Science, Northwestern University
  • Postdoctoral associate (Oct 2013 - Aug 2015), IAS and DIMACS
  • Research Fellow (Aug - Oct 2013), Simons Institute, UC Berkeley
  • Ph. D. (2008-13), UC Berkeley
    Advisor: Luca Trevisan, Chair(s) of Committee: Luca Trevisan and Umesh V. Vazirani.
  • B. Tech. (2004-08), IIT Kanpur

    [CV]


    Program committees: RANDOM 2015, CCC 2016, FOCS 2017, COLT 2020, ITCS 2021, COLT 2021, FOCS 2021, ITCS 2022, ALT 2022, COLT 2022, COLT 2023, ALT 2023, COLT 2024, STOC 2025.

    I also help organize TCS+, an online seminar series in theoretical computer science, accessible to the widest possible audience, and ensuring a carbon-free dissemination of ideas across the globe.

    • Publications

      Boolean function analysis, Applied probability and Learning theory

    1. Xi Chen, Anindya De, Shivam Nadimpalli, Rocco Servedio and Erik Waingarten
      Lower Bounds for Convexity Testing
      [arXiv] SODA 2025

    2. Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco Servedio and Tianqi Yang
      Relative-error monotonicity testing.
      [arXiv] SODA 2025

    3. Anindya De, Shivam Nadimpalli and Rocco Servedio
      Gaussian Approximation of Convex Sets by Intersections of Halfspaces
      [arXiv] FOCS 2024

    4. Xi Chen, Anindya De, Chin Ho Lee and Rocco Servedio
      Trace reconstruction from local statistical queries
      [arXiv] RANDOM 2024

    5. Anindya De, Huan Li, Shivam Nadimpalli and Rocco Servedio
      Detecting Low-Degree Truncation
      [arXiv] STOC 2024

    6. Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli and Rocco Servedio
      Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas
      [arXiv] SODA 2024

    7. Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli and Rocco Servedio
      Testing Intersecting and Union-Closed Families
      [arXiv] ITCS 2024

    8. Eshwar Ram Arunachaleswaran, Anindya De and Sampath Kannan
      Reconstructing Ultrametric Trees from Noisy Experiments
      [arXiv] ALT 2023

    9. Xi Chen, Anindya De, Chin Ho Lee, Rocco Servedio and Sandip Sinha
      Approximate Trace Reconstruction from a Single Trace
      [arXiv] SODA 2023

    10. Anindya De, Shivam Nadimpalli and Rocco Servedio
      Testing Convex Truncation
      [arXiv] SODA 2023

    11. Xi Chen, Anindya De, Chin Ho Lee, Rocco Servedio and Sandip Sinha
      Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
      [arXiv] SODA 2022

    12. Anindya De, Shivam Nadimpalli and Rocco Servedio
      Convex Influences
      [arXiv] ITCS 2022

    13. Anindya De, Shivam Nadimpalli and Rocco Servedio
      Approximating Sumset Size
      [arXiv] SODA 2022

    14. Anindya De, Sanjeev Khanna, Huan Li and Hesam Nikpey
      Nearly Tight Bounds for Discrete Search under Outlier Noise
      SOSA 2022

    15. Anindya De, Sanjeev Khanna, Huan Li and Hesam Nikpey
      Approximate optimization of convex functions with outlier noise
      [Conference Proceedings] NeurIPS 2021

    16. Aidao Chen, Anindya De and Aravindan Vijayaraghavan
      Algorithms for learning a mixture of linear classifiers
      [Conference Proceedings] ALT 2022

    17. Anindya De, Ryan O'Donnell and Rocco Servedio
      Learning sparse mixtures of permutations from noisy information
      [arXiv] COLT 2021

    18. Huck Bennett, Anindya De, Emmanouil Vlatakis and Rocco Servedio
      Reconstructing weighted voting schemes from partial information about their power indices
      [arXiv] COLT 2021

    19. Anindya De and Rocco Servedio
      Weak learning convex sets under normal distributions
      COLT 2021

    20. Anindya De, Elchanan Mossel and Joe Neeman
      Robust testing of low-dimensional functions
      [arXiv] STOC 2021

    21. Aidao Chen, Anindya De and Aravindan Vijayaraghavan
      Learning a mixture of two subspaces over finite fields
      [arXiv] ALT 2021

    22. Anindya De, Shivam Nadimpalli and Rocco Servedio
      Quantitative correlation inequalities via semigroup interpolation
      [arXiv] ITCS 2021, Probability Theory and Related Fields, 2022.

    23. Xi Chen, Anindya De, Chin Ho Lee, Rocco Servedio and Sandip Sinha
      Polynomial-time trace reconstruction in the low deletion rate regime
      [arXiv] ITCS 2021

    24. Xi Chen, Anindya De, Chin Ho Lee, Rocco Servedio and Sandip Sinha
      Polynomial-time trace reconstruction in the smoothed complexity model
      [arXiv] SODA 2021

    25. Xue Chen, Anindya De and Rocco Servedio
      Testing noisy linear functions for sparsity
      [arXiv] STOC 2020

    26. Xue Chen and Anindya De
      Reconstruction under outliers for Fourier-sparse functions
      [arXiv] SODA 2020

    27. Anindya De, Ryan O'Donnell and Rocco Servedio
      Sharp bounds for population recovery
      [arXiv] Theory of Computing, 2020

    28. Clement Canonne, Anindya De and Rocco Servedio
      Learning from satisfying assignments under continuous distributions
      [arXiv] SODA 2020

    29. Anindya De, Philip Long and Rocco Servedio
      Density estimation for shift-invariant multidimensional distributions
      [arXiv] ITCS 2019

    30. Anindya De, Elchanan Mossel and Joe Neeman
      Junta correlation is testable
      [arXiv] FOCS 2019

    31. Anindya De, Elchanan Mossel and Joe Neeman
      Is your function low-dimensional?
      [arXiv] COLT 2019

    32. Anindya De, Philip Long and Rocco Servedio
      Learning Sums of Independent Random Variables with Sparse Collective Support
      [arXiv] FOCS 2018

    33. Anindya De, Elchanan Mossel and Joe Neeman
      Non-interactive simulation of correlated distributions is decidable
      [ arXiv] SODA 2018

    34. Anindya De, Ryan O'Donnell and Rocco Servedio
      Optimal mean-based algorithms for trace reconstruction
      [arXiv] STOC 2017, Annals of Applied Probability 2019

    35. Anindya De, Elchanan Mossel and Joe Neeman
      Noise stability is computable and approximately low dimensional
      [arXiv] CCC 2017 
      Invited to special issue of Theory of Computing for CCC 2017.

    36. Constantinos Daskalakis, Anindya De, Gautam Kamath and Christos Tzamos
      A Size-Free CLT for Poisson Multinomials and its Applications
      [arXiv] STOC 2016

    37. Anindya De, Michael Saks and Sijian Tang
      Noisy population recovery in polynomial time
      [arXiv] FOCS 2016

    38. Xi Chen, Anindya De, Li-Yang Tan and Rocco Servedio
      Boolean monotonicity testing requires (almost) n1/2 non-adaptive queries
      [arXiv] STOC 2015

    39. Anindya De, Ilias Diakonikolas and Rocco Servedio
      Learning from satisfying assignments
      [arXiv] SODA 2015

    40. Anindya De and Rocco Servedio
      Efficient deterministic approximate counting for low degree polynomial threshold functions
      [arXiv] STOC 2014, Probability Theory and Related Fields, 2017

    41. Anindya De, Ilias Diakonikolas and Rocco Servedio
      Deterministic Approximate Counting for juntas of Degree-2 Polynomial Threshold Functions
      [arXiv] CCC 2014

    42. Anindya De, Elchanan Mossel and Joe Neeman
      Majority is Stablest : Discrete and SoS
      [arXiv] STOC 2013, Theory of Computing 2016

    43. Anindya De, Ilias Diakonikolas and Rocco Servedio
      Robust Khintchine-Kahane inequality and computing optimal
      constants in Fourier analysis and High-dimensional geometry
      [arXiv] ICALP 2013, SIAM Journal of Discrete Math 2016

    44. Anindya De, Ilias Diakonikolas and Rocco Servedio
      The Inverse Shapley Value problem
      [Journal version] ICALP 2012,  Games and Economic Behavior, 2017.

    45. Anindya De, Ilias Diakonikolas, Vitaly Feldman and Rocco Servedio
      Nearly optimal solutions for the Chow parameters problem and low weight approximation of halfspaces
      [Arxiv] STOC 2012, Journal of the ACM 2014
      IBM Pat Goldberg Memorial Math/CS/EE Best paper award, 2014  

      46. Pseudorandomness and Cryptography

    46. Eshan Chattopadhyay, Anindya De and Rocco Servedio
      Simple and Efficient pseudorandom generators from Gaussian Processes
      [ECCC] CCC 2019

    47. Anindya De
      Beyond the central limit theorem: Asymptotic expansions and pseudorandomness for combinatorial sums
      [ECCC] FOCS 2015

    48. Anindya De, Christopher Portmann, Thomas Vidick and Renato Renner
      Trevisan's extractor in the presence of quantum side information
      [Journal version][Arxiv version] SIAM Journal on Computing, 2012  

    49. Anindya De and Thomas Watson
      Extractors and lower bounds for locally samplable sources
      [Journal version][ECCC report] APPROX-RANDOM 2011, ACM ToCT 2012  

    50. Anindya De
      Pseudorandomness for permutation and regular branching programs
      [Proceedings version] [Full version] CCC 2011  

    51. Anindya De and Thomas Vidick
      Near optimal extractors against quantum storage
      [ECCC report] Preliminary version in QIP 2010. Extended version in STOC 2010 

    52. Anindya De, Omid Etesami, Luca Trevisan and Madhur Tulsiani
      Improved pseudorandom generators against depth 2 circuits
      [Conference version][ECCC report] APPROX-RANDOM 2010  

    53. Anindya De, Luca Trevisan and Madhur Tulsiani
      Non-uniform attacks against one-way functions and PRGs
      [Conference version] [ECCC report] CRYPTO 2010  

    54. Anindya De and Luca Trevisan
      Extractors using hardness amplification
      [Conference Proceedings],[Full version] APPROX-RANDOM 2009 

      55. Stochastic optimization

    55. Anindya De, Sanjeev Khanna, Huan Li and Hesam Nikpey
      An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs
      [Arxiv] ICALP 2020  

    56. Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra and Rocco Servedio.
      A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage
      [Arxiv] SODA 2014  

    57. Anindya De
      Boolean function analysis meets stochastic optimization: An approximation scheme for stochastic knapsack
      [Arxiv] SODA 2018  

      58. Miscellaneous

    58. Anindya De and Elchanan Mossel
      Explicit Optimal Hardness via Gaussian Stability results
      [Arxiv] ACM Transactions on Computation Theory, 2013 

    59. Anindya De
      Lower bounds in differential privacy
      [Arxiv] TCC 2012
      co-winner of Best student paper 

    60. Anindya De, Piyush P Kurur, Chandan Saha and Ramprasad Saptharishi
      Fast Integer Multiplication using Modular Arithmetic
      [arXiv][SICOMP version] STOC 2008, SIAM Journal on Computing 2013 

      61. Unpublished manuscripts

    61. Anindya De, Ilias Diakonikolas and Rocco Servedio
      Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions
      [arXiv]

    62. Anindya De
      Extractors and Pseudorandom generators using the Hardcore lemma
      [Full version] Unpublished manuscript  

      63. Some flings from the past

    63. Rajeev Kumar Gajbhiye, Anindya De, Rupesh Kumar Helwade and S.A. Soman
      A simple and efficient approach to determination of minimum set of Break Point Relays for Transmission Protection System Coordination
      [Conference Proceedings], International Conference on Future Power Systems, Amsterdam, 2005

    64. Rajeev Kumar Gajbhiye, Anindya De and S.A. Soman
      Computation of Optimal Break Point Set of Relays:An Integer Linear Programming Approach
      [Journal Version], IEEE Transactions on Power Delivery, 2008

    65. Ho-lin Chen, Anindya De and Ashish Goel
      Towards Programmable Molecular Machines
      [Full version], FNANO, 2008

      66. Links:    ECCC |    Wisdom AI