Publications

Manuscript(s)

  • Lower Bounds for Leader Election and Collective Coin Flipping, Revisited
    Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco Servedio
    Manuscript 2025
  • Condensing and Extracting against Online Adversaries
    Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco Servedio
    Manuscript 2025
  • Two-Sided Lossless Expanders in the Unbalanced Setting
    Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Yunya Zhao
    Manuscript 2025

    • Publications

  • Leakage-resilient extractors against number-on-forehead protocols
    Eshan Chattopadhyay, Jesse Goodman
    57th Annual ACM Symposium on Theory of Computing (STOC), 2025
  • On the Existence of Seedless Condensers: Exploring the Terrain
    Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach
    65th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2024
  • Extractors for Polynomial Sources over F2
    Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani
    15th Innovations in Theoretical Computer Science (ITCS), 2024
  • Recursive Error Reduction for Regular Branching Programs
    Eshan Chattopadhyay, Jyun-Jie Liao
    15th Innovations in Theoretical Computer Science (ITCS), 2024
  • Hardness against Linear Branching Programs and More
    Eshan Chattopadhyay, Jyun-Jie Liao
    38th Computational Complexity Conference (CCC), 2023
  • Low-Degree Polynomials Extract from Local Sources
    Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro
    49th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2022
  • Extractors for Sum of Two Sources
    Eshan Chattopadhyay, Jyun-Jie Liao
    54th Annual ACM Symposium on Theory of Computing (STOC), 2022
  • The Space Complexity of Sampling
    Eshan Chattopadhyay, Jesse Goodman, David Zuckerman
    13th Innovations in Theoretical Computer Science (ITCS) conference, 2022
  • Affine Extractors for Almost Logarithmic Entropy
    Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao
    62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2021
  • Improved Extractors for Small-Space Sources
    Eshan Chattopadhyay, Jesse Goodman
    62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2021
  • Fractional Pseudorandom Generators from Any Fourier Level
    Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, Abhishek Shetty
    36th Computational Complexity Conference (CCC), 2021
  • Non-Malleable Codes, Extractors and Secret Sharing for Interleaved Tampering and Composition of Tampering
    Eshan Chattopadhyay, Xin Li
    18th Theory of Cryptography Conference (TCC), 2020
  • Extractors and Secret-Sharing against Bounded Collusion Protocols
    Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, David Zuckerman
    61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020 (merge of this paper and this paper)
  • A Recipe for Constructing Two-Source Extractors
    Eshan Chattopadhyay
    Invited survey article for ACM SIGACT News Complexity Theory Column, June 2020 issue
  • Non-Malleability against Polynomial Tampering
    Marshall Ball, Eshan Chattopadhyay, Jyun-Jie Liao, Tal Malkin, Li-Yang Tan
    40th Annual International Cryptology Conference (CRYPTO), 2020
  • Optimal Error Pseudodistributions for Read-Once Branching Programs
    Eshan Chattopadhyay, Jyun-Jie Liao
    35th Computational Complexity Confererence (CCC), 2020
  • Extractors for Adversarial Sources via Extremal Hypergraphs
    Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li
    52nd Annual ACM Symposium on Theory of Computing (STOC), 2020
  • XOR Lemmas for Resilient Functions Against Polynomials
    Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett, David Zuckerman
    52nd Annual ACM Symposium on Theory of Computing (STOC), 2020
  • Simple and efficient pseudorandom generators from Gaussian processes
    Eshan Chattopadhyay, Anindya De, Rocco A. Servedio
    34th Computational Complexity Confererence (CCC), 2019
  • Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates
    Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal
    10th Innovations in Theoretical Computer Science (ITCS) conference, 2019
  • Privacy Amplification from Non-Malleable Codes
    Eshan Chattopadhyay, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu, Sruthi Sekar
    20th International Conference on Cryptology in India (Indocrypt), 2019
  • Pseudorandom Generators from Polarizing Random Walks
    Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett
    Theory of Computing, 2019.
    Special Issue: 33rd Computational Complexity Confererence (CCC), 2018
  • A New Approach for Constructing Low-Error, Two-Source Extractors
    Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma
    33rd Computational Complexity Confererence (CCC), 2018
  • Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity
    Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal
    50th Annual ACM Symposium on Theory of Computing (STOC), 2018
  • Non-Malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions
    Eshan Chattopadhyay, Xin Li
    49th Annual ACM Symposium on Theory of Computing (STOC), 2017
  • Explicit Two-Source Extractors and More
    PhD Thesis, 2016.
    Bert Kay Dissertation Award (best doctoral thesis in computer science at UT Austin)
  • Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols
    Eshan Chattopadhyay, Xin Li
    57th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2016
  • Explicit Two-Source Extractors and Resilient Functions
    Eshan Chattopadhyay, David Zuckerman
    Annals of Mathematics 2019
    Preliminary version in the 48th Annual ACM Symposium on Theory of Computing (STOC), 2016, Best Paper Award
  • Extractors for Sumset Sources
    Eshan Chattopadhyay, Xin Li
    48th Annual ACM Symposium on Theory of Computing (STOC), 2016
  • Non-Malleable Extractors and Codes, with their Many Tampered Extensions
    Eshan Chattopadhyay, Vipul Goyal, Xin Li
    SIAM Journal on Computing (SICOMP) 2020.
    Preliminary version in the 48th Annual ACM Symposium on Theory of Computing (STOC), 2016
  • New Extractors for Interleaved Sources
    Eshan Chattopadhyay, David Zuckerman
    31st Computational Complexity Confererence (CCC), 2016
  • Non-Malleable Codes Against Constant Split-State Tampering
    Eshan Chattopadhyay, David Zuckerman
    55th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2014
  • An Explicit VC-Theorem for Low-Degree Polynomials
    Eshan Chattopadhyay, Adam Klivans, Pravesh Kothari
    16th International Conference on Randomization and Computation (RANDOM) 2012