Meghal Gupta

According to our database, Meghal Gupta authored at least 26 papers between 2016 and 2026.

Collaborative distances:

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

2026

Super-Constant Weight Dicke States in Constant Depth Without Fanout.

Lucas Gretta, Meghal Gupta, Malvika Raj Joshi

CoRR, April, 2026

Parity ∉ QAC0 ⟺ QAC0 is Fourier-Concentrated.

Lucas Gretta, Meghal Gupta, Malvika Raj Joshi

CoRR, April, 2026

QEDBENCH: Quantifying the Alignment Gap in Automated Evaluation of University-Level Mathematical Proofs.

Santiago Gonzalez, Alireza Amiri Bavandpour, Peter Ye, Edward Zhang, Ruslans Aleksejevs, Todor Antic, Polina Baron, Sujeet Bhalerao, Shubhrajit Bhattacharya, Zachary Burton, John Byrne, Hyungjun Choi, Nujhat Ahmed Disha, Koppány István Encz, Yuchen Fang, Robert Joseph George, Ebrahim Ghorbani, Alan Goldfarb, Jing Guo, Meghal Gupta, Stefano Huber, Annika Kanckos, Minjung Kang, Hyun Jong Kim, Dino Lorenzini, Levi Lorenzo, Tianyi Mao, Giovanni Marzenta, Ariane M. Masuda, Lukas Mauth, Ana Mickovic, Andres Miniguano-Trujillo, Antoine Moulin, Wenqi Ni, Tomos Parry, Kevin Ren, Hossein Roodbarani, Mathieu Rundström, Manjil Saikia, Detchat Samart, Rebecca Steiner, Connor Stewart, Dhara Thakkar, Jeffrey Tse, Vasiliki Velona, Yunhai Xiang, Sibel Yalçin, Jun Yan, Ji Zeng, Arman Cohan, Quanquan C. Liu

CoRR, February, 2026

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

Meghal Gupta, William He, Ryan O'Donnell

Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026

A Classical Quadratic Speedup for Planted k xor.

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

Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, 2026

2025

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

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

CoRR, August, 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