Rahul Santhanam
where else to find them
what they talk about
all 4 in the filters
where they keep going back
no series more than once — all 5 in the filters
on a stage with
who talks about the same things
- Shuichi Hirahara7 talks
- Lijie Chen9 talks
- Makrand Sinha5 talks
- Toniann Pitassi5 talks
- Yuval Filmus9 talks
- Raghu Meka5 talks
| title | conference | date |
|---|---|---|
| A Commentary on the Collision of Worlds | Lower Bounds, Learning, and Average-Case Complexity | 2023-02-13 |
A précis of the concrete claims: Allender’s 2001 survey promotes a variant K^T (capital T) that relates tightly to circuit complexity and to MCSP via a… | ||
| 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… | ||
| A Survey on MCSP | Boolean Devices 2018 | 2018-09-10 |
Defines MCSP and variants (decision, search, optimization, approximate) and frames the core open: is MCSP NP‑hard or in P. Shows the explicit construction… | ||
| Improved Deterministic Algorithms for Sparse Max-SAT | Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms | 2015-11-06 |
Deterministic algorithms give explicit savings for sparse Max-SAT: savings Ω(n/c) (polynomial space) and savings n/√c (exponential space) for formulas with m =… | ||
| QBF Satisfiability Algorithms and Connections with Circuit Lower Bounds | Connections Between Algorithm Design and Complexity Theory | 2015-09-28 |
Gives a concrete algorithmic tradeoff: for QBF with k quantifier blocks over CNFs or small formulas the procedure achieves savings Ω(n^{1/(k+1)}) by splitting… | ||
| nothing matches | ||