Mohan Paturi
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 1 in the filters
on a stage with
never shared a talk
who talks about the same things
nobody close enough yet
| title | conference | date |
|---|---|---|
| Satisfiability Algorithms I | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Shows that combinatorial facts about K-CNF drive both algorithms and lower bounds: the satisfiability decoding lemma proves any K-CNF has at most 2^{n(1-1/K)}… | ||
| Satisfiability Algorithms II | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Proves nonconstructive lower bounds showing most degree‑2 GF(2) polynomials need size 2^{n−o(n)} for depth‑3 circuits when bottom fan‑in k = o(log n)… | ||
| Sparsification Lemma and ETH | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Describes a concrete tool: the sparsification lemma that rewrites any k‑CNF, in 2^{εn} time, as a disjunction of linearly many linear‑size k‑CNFs while… | ||
| nothing matches | ||