Meghal Gupta

According to our database, Meghal Gupta authored at least 22 papers between 2016 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

A Classical Quadratic Speedup for Planted <i>k</i>XOR.

Meghal Gupta, William He, Ryan O'Donnell, Noah G. Singer

CoRR, August, 2025

Few Single-Qubit Measurements Suffice to Certify Any Quantum State.

Meghal Gupta, William He, Ryan O'Donnell

CoRR, June, 2025

List Decoding Bounds for Binary Codes with Noiseless Feedback.

Meghal Gupta, Rachel Yun Zhang

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Error Correction for Message Streams.

Meghal Gupta, Rachel Yun Zhang

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

Tight Bounds for Stream Decodable Error-Correcting Codes.

Meghal Gupta, Venkatesan Guruswami, Mihir Singhal

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Constant Query Local Decoding against Deletions Is Impossible.

Meghal Gupta

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Optimal Quantile Estimation: Beyond the Comparison Model.

Meghal Gupta, Mihir Singhal, Hongxun Wu

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Interactive Coding with Unbounded Noise.

Eden Fargion, Ran Gelles, Meghal Gupta

Proceedings of the Approximation, 2024

Dueling Optimization with a Monotone Adversary.

Avrim Blum, Meghal Gupta, Gene Li, Naren Sarayu Manoj, Aadirupa Saha, Yuanyuan Yang

Proceedings of the International Conference on Algorithmic Learning Theory, 2024

2023

On Interactive Coding Schemes with Adaptive Termination.

Meghal Gupta, Rachel Yun Zhang

Electron. Colloquium Comput. Complex., 2023

A Noise Resilient Transformation for Streaming Algorithms.

Meghal Gupta, Rachel Yun Zhang

Electron. Colloquium Comput. Complex., 2023

A New Upper Bound on the Maximal Error Resilience of Interactive Error-Correcting Codes.

Meghal Gupta, Rachel Yun Zhang

CoRR, 2023

Efficient Interactive Coding Achieving Optimal Error Resilience over the Binary Channel.

Meghal Gupta, Rachel Yun Zhang

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Binary Error-Correcting Codes with Minimal Noiseless Feedback.

Meghal Gupta, Venkatesan Guruswami, Rachel Yun Zhang

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

An Optimal Algorithm for Certifying Monotone Functions.

Meghal Gupta, Naren Sarayu Manoj

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting.

Ofer Grossman, Meghal Gupta, Mark Sellke

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Interactive Error Correcting Codes: New Constructions and Impossibility Bounds.

Meghal Gupta, Rachel Yun Zhang

Proceedings of the Approximation, 2023

2022

Positive Rate Binary Interactive Error Correcting Codes Resilient to >1/2 Adversarial Erasures.

Meghal Gupta, Rachel Yun Zhang

CoRR, 2022

The optimal error resilience of interactive communication over binary channels.

Meghal Gupta, Rachel Yun Zhang

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Interactive error correcting codes over binary erasure channels resilient to > ½ adversarial corruption.

Meghal Gupta, Yael Tauman Kalai, Rachel Yun Zhang

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to $>\frac12$ Adversarial Corruption.

Meghal Gupta, Yael Tauman Kalai, Rachel Yun Zhang

IACR Cryptol. ePrint Arch., 2021

2016

Bounding extremal functions of forbidden 0-1 matrices using (r, s)-formations.

Jesse Geneson, Meghal Gupta

CoRR, 2016