Anindya De
Associate Professor 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

    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. Anindya De, Huan Li, Shivam Nadimpalli and Rocco Servedio
      Detecting Low-Degree Truncation
      [arXiv] STOC 2024

    2. 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

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

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

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

    6. 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

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

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

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

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

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

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

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

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

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

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

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

    18. 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

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

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

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

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

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

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

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

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

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

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

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

    30. 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.

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

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

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

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

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

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

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

    38. 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

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

    40. 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  

    41. Pseudorandomness and Cryptography

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

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

    44. 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  

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

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

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

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

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

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

    51. Stochastic optimization

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

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

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

    55. Miscellaneous

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

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

    58. 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 

    59. Unpublished manuscripts

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

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

    62. 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