amir Abboud
where else to find them
no profile links on file
what they talk about
where they keep going back
no series more than once — all 2 in the filters
on a stage with
who talks about the same things
nobody close enough yet
| title | conference | date |
|---|---|---|
| Worst-Case to Expander-Case Reductions | ITCS 2023 | 2023-01-10 |
Shows that many graph problems reduce to expander instances by a simple gadget: add an expansion layer U of about n vertices and randomly connect original… | ||
| The New P | Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) | 2015-12-08 |
Introduces a colored-triangle detection problem: given colored nodes and threshold delta, trivial O(n^3) search exists and constant-delta cases admit truly… | ||
| Simulating Branching Programs with Edit Distance and Friends | Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) | 2015-12-08 |
Proves a concrete reduction from BP-SAT to LCS/edit distance: satisfiability of nondeterministic branching programs (width w, length T on n variables) maps to… | ||
| nothing matches | ||