4 citations · 4 across the 3 of their papers we have counts for
6 papers
On the Complexity of Locally Dense Lattices
Shuichi Hirahara, Kazuki Ogitsuka
\emph{Locally dense lattices} are central gadgets used to prove the hardness of the Shortest Vector Problem and related lattice problems. Informally, a locally dense lattice is a l…
One-Sided-Error Parameterized Reductions for the Minimum Distance and Shortest Vector Problems
Shuichi Hirahara, Kazuki Ogitsuka
It is notoriously difficult to obtain deterministic reductions for the Minimum Distance Problem (MDP) and the Shortest Vector Problem (SVP). Under two-sided-error randomized reduct…
Test of Quantumness with Small-Depth Quantum Circuits
Shuichi Hirahara, François Le Gall
Recently Brakerski, Christiano, Mahadev, Vazirani and Vidick (FOCS 2018) have shown how to construct a test of quantumness based on the learning with errors (LWE) assumption: a tes…
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
Shuichi Hirahara, Nobutaka Shimizu
In this paper, we seek a natural problem and a natural distribution of instances such that any -time algorithm fails to solve most instances drawn from the distribution…
Beyond Natural Proofs: Hardness Magnification and Locality
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira +3
Hardness magnification reduces major complexity separations (such as ) to proving lower bounds for some natural problem against…
A Duality Between Depth-Three Formulas and Approximation by Depth-Two
Shuichi Hirahara
We establish an explicit link between depth-3 formulas and one-sided approximation by depth-2 formulas, which were previously studied independently. Specifically, we show that the…