Anindya De
Assistant Professor at Northwestern University
<myfirstname> at eecs dot northwestern dot edu

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

In the past:
  • 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.

    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. Anindya De, Philip Long and Rocco Servedio
      Efficient algorithms for learning sums of commonly supported integer random variables
      Manuscript

    2. Anindya De, Philip Long and Rocco Servedio
      Tight sample complexity lower bounds for learning sums of commonly supported integer random variables
      Manuscript

    3. Anindya De, Ryan O'Donnell and Rocco Servedio
      Sharp bounds for population recovery
      [arXiv]

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

    5. Boolean function analysis and Learning theory

    6. Anindya De, Ryan O'Donnell and Rocco Servedio
      Optimal mean-based algorithms for trace reconstruction
      [arXiv] STOC 2017

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

    8. Anindya De, Elchanan Mossel and Joe Neeman
      Noise stability is computable and approximately low dimensional
      [arXiv] CCC 2017

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

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

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

    12. Anindya De and Rocco Servedio
      Efficient deterministic approximate counting for low degree polynomial threshold functions
      [arXiv] STOC 2014

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

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

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

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

    17. Anindya De, Ilias Diakonikolas and Rocco Servedio
      The Inverse Shapley Value problem
      [Full version] ICALP 2012  
      Accepted modulo minor revisions to Games and Economic Behavior.

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

    19. Pseudorandomness and Cryptography

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

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

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

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

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

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

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

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

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

    29. Miscellaneous

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

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

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

    33. Anindya De, Piyush P Kurur, Chandan Saha and Ramprasad Saptharishi
      Fast Integer Multiplication using Modular Arithmetic
      [arXiv][SICOMP version] STOC 2008, SICOMP 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