Anindya De
Assistant 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


    Program committees: RANDOM 2015, CCC 2016, FOCS 2017.

    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.

  • Papers

      Applied probability and Learning

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

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

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

    4. Anindya De, Ryan O'Donnell and Rocco Servedio
      Sharp bounds for population recovery
      [arXiv] Theory of Computing (to appear)

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

    6. Boolean function analysis and Learning theory

    7. Anindya De, Ryan O'Donnell and Rocco Servedio
      Learning sparse mixtures of rankings from noisy information
      [arXiv] Submitted

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

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

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

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

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

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

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

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

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

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

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

    19. Anindya De, Ilias Diakonikolas and Rocco Servedio
      Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions

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

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

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

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

    24. Pseudorandomness and Cryptography

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

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

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

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

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

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

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

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

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

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

    35. Stochastic optimization

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

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

    38. Miscellaneous

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

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

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

    Some flings from the past

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

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

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

    Links:    ECCC