Ryan Williams
where else to find them
no profile links on file
what they talk about
all 8 in the filters
where they keep going back
- ITCS3 editions2021–2023
all 8 in the filters
on a stage with
all 10 in the filters
who talks about the same things
- Lijie Chen9 talks
- Saman Amarasinghe13 talks
- Michael Carbin14 talks
- Jonathan Ragan-Kelley12 talks
- Runzhou Tao6 talks
- Ranjit Jhala19 talks
| title | conference | date |
|---|---|---|
| The Mystery of the Missing String | Lower Bounds, Learning, and Average-Case Complexity | 2023-02-13 |
Equivalence between the simple missing string task and relativized exponential lower bounds: finding a string outside M strings of length N (with M ≈ 2^{εN})… | ||
| Black-box Constructive Proofs are Unavoidable | ITCS 2023 | 2023-01-10 |
Main claim: proving NEXP not in a typical circuit class C is equivalent to the existence of a black-box constructivity — a randomized poly(n)-time oracle… | ||
| On Oracles and Algorithmic Methods for Proving Lower Bounds | ITCS 2023 | 2023-01-10 |
Proves an equivalence between missing string circuit complexity and whether Σ2E requires exponential-size circuits relative to every oracle, constructs uniform… | ||
| Smaller ACC0 Circuits for Symmetric Functions | ITCS 2022 | 2022-01-31 |
Every symmetric Boolean function on n bits admits small constant‑depth circuits using composite moduli: for any ε>0 there exists a modulus m so a depth‑3 mod‑m… | ||
| Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity | ITCS 2022 | 2022-01-31 |
Presents concrete Merlin–Arthur protocols and time bounds: near-linear MA for 3SUM by reducing to counting solutions mod d, encoding inputs as a polynomial… | ||
| On the Usefulness of the Strong Exponential Time Hypothesis | 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing | 2021-02-11 |
Argues Strong Exponential Time Hypothesis is likely false while conceding uncertainty, and shows that chasing that refutation yields concrete results… | ||
| Circuit Depth Reductions | ITCS 2021 | 2021-01-06 |
Proves structural depth reductions: any size-S circuit is an OR of 2^{S/3} formulas (toy lemma) and the main result gives a depth-3 with top fan-in 2^{S/3.9}… | ||
| Time-Space Lower Bounds for Proof Systems with Quantum and Randomized Verifiers | ITCS 2021 | 2021-01-06 |
Proves a concrete lower bound: there is a language in QCMA running in linear time on a QRAM that cannot be decided by small‑space random‑access machines in… | ||
| Portable, type-fancy multidimensional arrays | Typelevel Summit Philadelphia 2019 | 2019-04-01 |
Implements the Zarr spec in portable Scala to store chunked multidimensional arrays (used for single-cell RNA with up to ~2 million cells × ~30,000 genes → ~60… | ||
| Accelerating Single-cell Bioinformatics with N-dimensional Arrays | PyData Miami 2019 | 2019-01-09 |
Claim: parallelize single-cell workflows across Spark Dask Pywren and Apache Beam and store arrays as Zarr instead of HDF5. Implements Zarr format in scanpy… | ||
| A Review of Some Recent Lower Bounds Against Low-Depth Threshold Circuits | Boolean Devices 2018 | 2018-09-10 |
Presents concrete lower bounds: an explicit Andreev-style function needs superlinear gates and roughly n^{1.5}/polylog n size against depth‑3 TC0, proven by a… | ||
| Deterministic APSP, Orthogonal Vectors, and More | Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) | 2015-12-08 |
Claims deterministic subquadratic algorithms for Orthogonal Vectors when d = c log n (randomized version runs in n^{2−ε}; deterministic matches up to… | ||
| Circuit Analysis Algorithms | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Session argues a concrete algorithm–lower-bound duality and gives a worked algorithm that beats brute force for several circuit classes: constant-depth ACC… | ||
| Circuit Complexity and Connections I | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Argues that small improvements in circuit algorithms yield provable lower bounds: a deterministic SAT speedup of roughly 2^n / n^10 already implies NEXP is not… | ||
| Circuit Complexity and Connections II | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Shows concrete equivalences: faster algorithms for restricted circuit SAT give explicit circuit lower bounds, and conversely lower bounds yield derandomization… | ||
| Proof of NEXP Not in ACC | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Proves that showing a faster ACC-SAT algorithm yields circuit lower bounds: a subexponential-time SAT routine for constant-depth mod-m circuits implies some… | ||
| nothing matches | ||