Research
Research
All publications in reverse chronological order of release. Authorship in alphabetical author. More data available on my Google Scholar.
Breaking the quadratic barrier: robust cardinality sketches for adaptive queries
Edith Cohen, Mihir Singhal, Uri Stemmer (2025)
ICML 2025, to appear
One attack to rule them all: tight quadratic bounds for adaptive queries on cardinality sketches
Edith Cohen, Jelani Nelson, Tamás Sarlós, Mihir Singhal, Uri Stemmer (2024)
Tight bounds for stream decodable error-correcting codes
Meghal Gupta, Venkatesan Guruswami, Mihir Singhal (2024)
Optimal quantile estimation: beyond the comparison model
Meghal Gupta, Mihir Singhal, Hongxun Wu (2024)
FOCS 2024, Best Student Paper
Omnipredictors for regression and the approximate rank of convex functions
Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Shetty, Mihir Singhal (2023)
COLT 2024
Locally computing edge orientations
Slobodan Mitrović, Ronitt Rubinfeld, Mihir Singhal (2023)
ESA 2024
Low-degree multicalibration
Parikshit Gopalan, Michael Kim, Mihir Singhal, Shengjia Zhao (2022)
COLT 2022
Computations associated with the resonance arrangement
Mihir Singhal, Zachary Chroman (2021)
Tetris is NP-hard even with O(1) rows or columns
Sualeh Asif, Michael Coulombe, Erik Demaine, Martin Demaine, Adam Hesterberg, Jayson Lynch, Mihir Singhal (2020)
JCDCG³ 2019, Journal of Information Processing
Families with no perfect matchings
Mihir Singhal (2020)
Combinatorial Theory
Unimodality of a refinement of Lassalle's sequence
Mihir Singhal (2020)
Discrete Mathematics
Lower bounds for superpatterns and universal sequences
Zachary Chroman, Matthew Kwan, Mihir Singhal (2020)
Journal of Combinatorial Theory, Series A
Erdos-Littlewood-Offord problem with arbitrary probabilities
Mihir Singhal (2020)
Discrete Mathematics