recent

An improved protocol for ExactlyN with more than 3 players

The ExactlyN problem in the number-on-forehead (NOF) communication setting asks $k$ players, each of whom can see every input but their …
Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman
Cite arXiv
Lifting to Parity Decision Trees via Stifling
We show that the deterministic decision tree complexity of a (partial) function or relation $f$ lifts to the deterministic parity …
Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif, Swagato Sanyal
Cite arXiv Talk Video
One-Way Communication Complexity and Non-Adaptive Decision Trees

We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision …
Nikhil S. Mande, Swagato Sanyal, Suhail Sherif
Cite arXiv
Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness
We study the complexity of optimizing highly smooth convex functions. For a positive integer $p$, we want to find an …
Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
Cite arXiv Talk Video
No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization
We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function …
Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
Cite arXiv Talk Video
Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
We give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a …
Arkadev Chattopadhyay, Ankit Garg, Suhail Sherif
Cite arXiv Talk Video