3 papers
cs.CC2026
Improved Bounds for Coin Flipping, Leader Election, and Random Selection
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach +1
Random selection, leader election, and collective coin flipping are fundamental tasks in fault-tolerant distributed computing. We study these problems in the full-information model…
cs.CC2025
Condensing and Extracting Against Online Adversaries
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach +1
We study the tasks of deterministically condensing and extracting from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model of defective randomness where extraction…
quant-ph2025
Forrelation is Extremally Hard
Uma Girish, Rocco Servedio
The Forrelation problem is a central problem that demonstrates an exponential separation between quantum and classical capabilities. In this problem, given query access to -bit…