ICTS 2024 — Innovations in Theoretical Computer Science

Gödel’s Lost Letter and P=NP 2024-01-14

In case the Berkeley Simons Institute (1/30–2/2) feels warmer than where you are now

Venkatesan Guruswami (University of California, Berkeley) is the chair of the ITCS 2024 conference. See here for details. Some of the program committee include: Avrim Blum (Toyota Technological Institute at Chicago) and Dana Randall (Georgia Institute of Technology) and Michael Saks (Rutgers University).

The rest are:

Maryam Aliakbarpour, Benny Applebaum, Arnab Bhattacharyya, Kshipra Bhawalkar, Moses Charikar, Vincent Cohen-Addad, Andrea Coladangelo, Jelena Diakonikolas, Ran Duan, Alina Ene, Bill Fefferman, Shuichi Hirahara, Sivakanth Gopi, Fernando Granha Jeromino, William Hoza, Elias Koutsoupias, Michael P. Kim, Bundit Laekhanukit, Jerry Li, Ray Li, Guilio Malavolta, Daniele Micciancio, Dor Minzer, Jonathan Mosheiff, Partha Mukhopadhyay, Rasmus Pagh, Aditya Potukuchi, Eric Price, Robert Robere, Nicolas Resch, Sushant Sachdeva, Hadas Shachnai, Rocco Servedio, Piyush Srivastava, Xiaorui Sun, Magnus Wahlstrom, Matt Weinberg, Manolis Zampetakis, Goran Zuzic.

Innovativeness

ITCS seeks to promote research with a bold agenda, which can be conceptual, technical, or methodological, and whose message will advance and inspire the theory community.

Well, the research has to at least be more innovative than “our” previous sentence. How would you paraphrase this?

We took out the word “innovative” to avoid being circular. To look for how they define it, here is what the ITCS 2024 announcement went on to say:

The program committee welcomes papers introducing a new concept, model or understanding; opening a new line of inquiry within traditional or interdisciplinary areas; introducing new mathematical techniques and methodologies, or new applications of known techniques; putting forth a bold, even if preliminary, vision or line of attack; or unearthing novel or surprising connections between different topics.

Some Papers

Here are the top 20 or so papers at the conference. By “top” we mean the few papers that we found especially interesting. None solve P versus NP but they all have pretty neat results.

Advanced Composition Theorems for Differential Obliviousness Mingxun Zhou (Carnegie Mellon University), Mengshi Zhao (The University of Hong Kong), T-H. Hubert Chan (The University of Hong Kong) and Elaine Shi (Carnegie Mellon University)
A Computational Separation Between Quantum No-cloning and No-telegraphing Barak Nehoran (Princeton University) and Mark Zhandry (NTT Research & Princeton University)
Winning without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every Round Melissa Dutz (Toyota Technological Institute at Chicago) and Avrim Blum (Toyota Technological Institute at Chicago)
Two-State Spin Systems with Negative Interactions Yumou Fei (Peking University), Leslie Ann Goldberg (Department of Computer Science, University of Oxford) and Pinyan Lu (Shanghai University of Finance and Economics)
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra Rajarshi Bhattacharjee (University of Massachusetts Amherst), Gregory Dexter (Purdue University), Cameron Musco (University of Massachusetts Amherst), Archan Ray (University of Massachusetts Amherst), Sushant Sachdeva (University of Toronto) and David P. Woodruff (Carnegie Mellon University)
Graph Threading Erik D. Demaine (MIT), Yael Kirkpatrick (MIT) and Rebecca Lin (MIT)
On generalized corners and matrix multiplication Kevin Pratt (Carnegie Mellon University)
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem Scott Aaronson (UT Austin/OpenAI), Harry Buhrman (QuSoft/CWI/University of Amsterdam) and William Kretschmer (Simons Institute/UC Berkeley)
Simple and Optimal Online Contention Resolution Schemes for ${k}$ -Uniform Matroids Atanas Dinev (Massachusetts Institute of Technology) and S. Matthew Weinberg (Princeton University)
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions Huacheng Yu (Princeton University) and Wei Zhan (University of Chicago)
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games Ioannis Anagnostides (Carnegie Mellon University), Alkis Kalavasis (Yale University), Tuomas Sandholm (Carnegie Mellon University) and Manolis Zampetakis (Yale University)
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis Gregory Valiant (Stanford)
Maximizing Miner Revenue in Transaction Fee Mechanism Design Ke Wu (CMU), Elaine Shi (CMU) and Hao Chung (Carnegie Mellon University)
Learning Arithmetic Circuits in the Presence of Noise: A General Framework and Applications to Unsupervised Learning Pritam Chandra (Microsoft Research), Ankit Garg (Microsoft Research India), Tanmay Sinha (Microsoft Research), Neeraj Kayal (Microsoft Research) and Kunal Mittal (Princeton University)
Influence Maximization in Ising Models Zongchen Chen (University at Buffalo) and Elchanan Mossel (MIT)
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions Arvind V. Mahankali (Stanford University), David P. Woodruff (Carnegie Mellon University) and Ziyu Zhang (Massachusetts Institute of Technology)
Quantum Pseudoentanglement Scott Aaronson (University of Texas, Austin), Adam Bouland (Stanford University), Bill Fefferman (University of Chicago), Soumik Ghosh (University of Chicago), Umesh Vazirani (University of California, Berkeley), Chenyi Zhang (Stanford University) and Zixin Zhou (Stanford University)
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions Justin Y. Chen (MIT), Piotr Indyk (MIT) and David P. Woodruff (Carnegie Mellon University)
A VLSI Circuit Model Accounting for Wire Delay Nathaniel Young (Unaffiliated), Ce Jin (MIT) and Ryan Williams (MIT)
Sampling, Flowers and Communication Huacheng Yu (Princeton University) and Wei Zhan (University of Chicago)

Open Problems

Here is an open problem: What rule did we use to select the above top papers?