ITCS 2022 Session 6
0Chair: Karthik C. S.
Improved Hardness of BDD and SVP Under Gap-(S)ETH
Huck Bennett (Oregon State University); Chris Peikert and Yi Tang (University of Michigan)
3 + ε Approximation of Tree Edit Distance in Truly Subquadratic Time
Masoud Seddighin (Sharif University of Technology); Saeed Seddighin (Toyota Technological Institute at Chicago)
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity
Shyan Akmal, Lijie Chen, and Ce Jin (MIT); Malvika Raj (UC Berkeley); Ryan Williams (MIT)
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks
Harry Buhrman (QuSoft, CWI, University of Amsterdam); Bruno Loff (University of Porto and INESC-Tec); Subhasree Patro and Florian Speelman (QuSoft, CWI, University of Amsterdam)
Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
François Le Gall (Nagoya University); Saeed Seddighin (Toyota Technological Institute at Chicago)
13th Innovations in Theoretical Computer Science (ITCS) Conference
Other Videos By Simons Institute for the Theory of Computing
| 2022-02-02 | ITCS 2022 Session 12 |
| 2022-02-02 | ITCS 2022 Session 11 |
| 2022-02-02 | ITCS 2022 Session 10 |
| 2022-02-02 | ITCS 2022 Session 9 |
| 2022-02-02 | ITCS 2022 Session 8 |
| 2022-02-01 | ITCS 2022 Graduating Bits |
| 2022-02-01 | ITCS 2022 Session 7 |
| 2022-02-01 | Uniform brackets, containers, and combinatorial Macbeath regions |
| 2022-02-01 | FPT Algorithms for Finding Near-Cliques in $c$-Closed Graphs |
| 2022-02-01 | Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs |
| 2022-02-01 | ITCS 2022 Session 6 |
| 2022-02-01 | ITCS 2022 Session 5 |
| 2022-02-01 | ITCS 2022 Session 4 |
| 2022-02-01 | ITCS 2022 Session 3 |
| 2022-01-31 | ITCS 2022 Session 2 |
| 2022-01-31 | ITCS 2022 Session 1 |
| 2022-01-31 | Randomness Extraction from Somewhat Dependent Sources |
| 2022-01-31 | Noisy Boolean Hidden Matching with Applications |
| 2022-01-31 | Small Circuits Imply Efficient Arthur-Merlin Protocols |
| 2022-01-29 | Multi-Agent Reinforcement Learning (Part II) |
| 2022-01-29 | Multi-Agent Reinforcement Learning (Part I) |