ICTS 2024 — Innovations in Theoretical Computer Science
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
-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?
I think there’s a typo in the headline (ICTS -> ITCS).
Right you are—slipped right on by the editor! Problem is that the post is indexed by the headline, so it has to stet.
It is difficult to justify the title of the conference for these papers.
I love this quote: Isaac Newton — ‘To myself I am only a child playing on the beach, while vast oceans of truth lie undiscovered before me’
I was playing this last weekend in how to approach to an elegant solution to SAT even though this won’t be necessary a polynomial time algorithm.
I found out that we would get the third place in a testing of a simple SAT Solver SATPYTHON against the SAT Competition 2022 using the same prerequisites for the participants: The solvers will be executed with a time limit of 5000 seconds and memory limit of 128GB. The results of the test were these ones:
https://www.starexec.org/starexec/secure/details/job.jsp?anonId=6ae56931-6a96-4a12-b8b9-b2252f421c8a
We say that we would get the third place in the section NoLimits Track from the competition since the third place was for the Solver kissat_inc just solving 198 benchmarks instances. Indeed, SATPYTHON solved 204 instances which is very close to the second place (the Solver kissat_pre) which solved 206 while the first place (the Cloud Solver vbs) that solved 238. The results of the competition in the section NoLimits Track were these ones:
https://satcompetition.github.io/2022/results.html
Note that, the Solver SATPYTHON was implemented in Python 2.7 with only 119 code lines (including comments and empty lines). Everybody could check for free the source in linux of this Solver SATPYTHON in the following URL link:
https://github.com/frankvegadelgado/sat_py/releases/tag/v1.0.0
Now, I feel like if I were a kid that finds a sea shell in the vast beach’s sand! 🙂
Keep playing in the beach’s sand and getting amused for the sea shells I find! 🙂
https://www.researchgate.net/publication/377656601_Note_for_the_P_versus_NP_Problem
I was staring at this short proof above feeling the same sensation that felt the mathematician Maryam Mirzakhani: her husband told us that she was happy when she had a brilliant idea and she liked to stay in that moment of joy before she realized that it could be wrong.
We introduce a new variant using the logic operator Xor such that we show that the Monotone Weighted Xor 2-satisfiability problem (MWX2SAT) is NP-complete and P at the same time. Now, the proof is clear, clean and elegant.
https://www.researchgate.net/publication/377656601_Note_for_the_P_versus_NP_Problem
We kept playing and developed a polynomial time algorithm for a well-know NP-complete problem. We created a GitHub repository with the software solution in Python.
https://github.com/frankvegadelgado/alma