Anindya De
Postdoctoral researcher at DIMACS and IAS
<myfirstname> at math dot ias dot edu

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

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] [Research statement] [Teaching statement]

New: 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


    Boolean function analysis and Learning theory

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

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

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

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

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

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

  7. Anindya De, Elchanan Mossel and Joe Neeman
    Majority is Stablest : Discrete and SoS
    [arXiv] STOC 2013

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

  9. Anindya De, Ilias Diakonikolas and Rocco Servedio
    The Inverse Shapley Value problem
    [Full version] ICALP 2012  

  10. 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, To appear in Journal of the ACM  

  11. Pseudorandomness and Cryptography

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

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

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

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

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

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

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

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

  20. Miscellaneous

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

  22. Anindya De and Elchanan Mossel
    Explicit Optimal Hardness via Gaussian Stability results
    [Arxiv] To appear in ACM, Transactions on Computation Theory 

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

  24. 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 | Personal