Shuichi Hirahara
where else to find them
what they talk about
where they keep going back
- ITCS2 editions2022–2023
on a stage with
all 6 in the filters
who talks about the same things
- Rahul Santhanam7 talks
- Lijie Chen9 talks
- Mikito Nanashima3 talks
- Toniann Pitassi5 talks
- Yuval Filmus9 talks
- Ran Raz6 talks
| title | conference | date |
|---|---|---|
| Capturing One-Way Functions via NP-Hardness of Meta-Complexity | Minimal Complexity Assumptions for Cryptography 2023 | 2023-05-01 |
Main theorem: a one-way function iff NP is worst-case hard and distributional Kolmogorov complexity is NP-hard under randomized polynomial-time reductions… | ||
| Allender's Conjecture and its Impacts on Meta-Complexity | Lower Bounds, Learning, and Average-Case Complexity | 2023-02-13 |
Allender’s conjectures are shown false under plausible collapses: reductions to Kolmogorov-random strings would imply EXP^NP = NEXP, so the hoped… | ||
| Kolmogorov Complexity Characterizes Statistical Zero Knowledge | ITCS 2023 | 2023-01-10 |
Main theorem: for any reasonable promise problem A, A in NISZK iff A RP many-one reduces to RK (with RK using approximation error e(m) ≈ Θ(log^2 m)), and A in… | ||
| Learning versus Pseudorandom Generators in Constant Parallel Time | ITCS 2023 | 2023-01-10 |
Proves an equivalence: existence of polynomial-stretch pseudorandom generators computable in NC0 is characterized by average-case hardness of weak learning for… | ||
| Excluding PH Pessiland | ITCS 2022 | 2022-01-31 |
Proves unconditionally that PH Pessiland excluded by showing PH-average hardness is equivalent to existence of a PH-confutable pseudorandom generator (PH-PRG)… | ||
| Errorless versus Error-prone Average-Case Complexity | ITCS 2022 | 2022-01-31 |
Paper proves reductions between error-prone heuristics and errorless average-case algorithms by building on non-adaptive average BPP/poly instant checker… | ||
| Average-case Hardness of NP and PH from Worst-case Fine-grained Assumptions | ITCS 2022 | 2022-01-31 |
Proves concrete average-case hardness from weaker worst-case fine‑grained assumptions: improving on Hirahara’s 2^{O(N/log N)} threshold, the paper shows that… | ||
| nothing matches | ||