8 citations · 35 across the 17 of their papers we have counts for
22 papers
Quantum Worst-Case to Average-Case Reductions for All Linear Problems
Vahid R. Asadi, Alexander Golovnev, Tom Gur +2
We study the problem of designing worst-case to average-case reductions for quantum algorithms. For all linear problems, we provide an explicit and efficient transformation of quan…
Worst-Case to Average-Case Reductions via Additive Combinatorics
Vahid R. Asadi, Alexander Golovnev, Tom Gur +1
We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time…
Derandomization of Cell Sampling
Alexander Golovnev, Tom Gur, Igor Shinkar
Since 1989, the best known lower bound on static data structures was Siegel's classical cell sampling lower bound. Siegel showed an explicit problem with inputs and possibl…
Relaxed Locally Correctable Codes with Improved Parameters
Vahid R. Asadi, Igor Shinkar
Locally decodable codes (LDCs) are error-correcting codes that admit a local decoding algorithm that recovers each individual bit of the message by querying only…
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality
Mohammad Mahdi Jahanara, Sajin Koroth, Igor Shinkar
Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoret…
Meyniel Extremal Families of Abelian Cayley Graphs
Fatemeh Hasiri, Igor Shinkar
We study the game of Cops and Robbers, where cops try to capture a robber on the vertices of a graph. Meyniel's conjecture states that for every connected graph on vertices…