Hi, I'm Shyamal, a fourth year Theory CS PhD student at Columbia. My research interests are in extremal/probabilistic combinatorics, sketching, discrepancy theory, and property testing. More generally, I particularly like the analysis of simple algorithms and crossover techniques between various areas of math and computer science. I am fortunate to be advised by Cliff Stein and Xi Chen and supported by an NSF Graduate Fellowship.
Publications
Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries (STOC '24). Xi Chen, Yumou Fei, Shyamal Patel
Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators (STOC '24). Shivam Nadimpalli and Shyamal Patel
Polylog-Competitive Deterministic Local Routing and Scheduling (STOC '24). Bernhard Haeupler, Shyamal Patel, Antti Röyskö, Cliff Stein, Goran Žužić
New Lower Bounds for Adaptive Tolerant Junta Testing (FOCS '23), Xi Chen and Shyamal Patel
Distribution-free Testing for Halfspaces Requires PAC Learning (SODA '22), Xi Chen and Shyamal Patel
Threshold Graphs Maximize Homomorphism Densities (Combinatorics Probability and Computing), Grigoriy Blekherman and Shyamal Patel
A Trivial Yet Optimal Solution To Vertex Fault Tolerant Spanners (PODC '19), Greg Bodwin and Shyamal Patel
Email: shyamalpatelb (at) gmail (dot) com