ITCS

Publications

2024

Sayan Bandyapadhyay, Anil Maheshwari, Sasanka Roy, Michiel Smid, Kasturi R. Varadarajan
Geometric Covering via Extraction Theorem. ITCS (2024)
Nico Döttling, Tamer Mour
On the Black-Box Complexity of Correlation Intractability. ITCS (2024)
Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. ITCS (2024)
Lukás Folwarczný, Mika Göös, Pavel Hubácek, Gilbert Maystre, Weiqiang Yuan
One-Way Functions vs. TFNP: Simpler and Improved. ITCS (2024)
Yi-Jun Chang
The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees. ITCS (2024)
Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman
An Improved Protocol for ExactlyN with More Than 3 Players. ITCS (2024)
Constantinos Daskalakis, Noah Golowich, Nika Haghtalab, Abhishek Shetty
Smooth Nash Equilibria: Algorithms and Complexity. ITCS (2024)
Kevin Pratt
On Generalized Corners and Matrix Multiplication. ITCS (2024)
Charlotte Out, Nicolás Rivera, Thomas Sauerwald, John Sylvester
Rumors with Changing Credibility. ITCS (2024)
Zhao Song, Lichen Zhang, Ruizhe Zhang
Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time. ITCS (2024)
Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Peter Robinson
The Message Complexity of Distributed Graph Optimization. ITCS (2024)
Huacheng Yu, Wei Zhan
Sampling, Flowers and Communication. ITCS (2024)
Siddharth Barman, Anand Krishna, Pooja Kulkarni, Shivika Narang
Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations. ITCS (2024)
Mayank Goswami, Riko Jacob
An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio. ITCS (2024)
Jop Briët, Harry Buhrman, Davi Castro-Silva, Niels M. P. Neumann
Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract). ITCS (2024)
Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam
Discreteness of Asymptotic Tensor Ranks (Extended Abstract). ITCS (2024)
Zhili Chen, Joshua A. Grochow, Youming Qiao, Gang Tang, Chuanqi Zhang
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials III: Actions by Classical Groups. ITCS (2024)
Monika Henzinger, Barna Saha, Martin P. Seybold, Christopher Ye
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. ITCS (2024)
Rex Fernando, Yuval Gelles, Ilan Komargodski
Scalable Distributed Agreement from LWE: Byzantine Agreement, Broadcast, and Leader Election. ITCS (2024)
Scott Aaronson, Harry Buhrman, William Kretschmer
A Qubit, a Coin, and an Advice String Walk into a Relational Problem. ITCS (2024)
Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani
. ITCS (2024)
Lisa Hellerstein, Naifeng Liu, Kevin Schewior
Quickly Determining Who Won an Election. ITCS (2024)
Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin
Graph Threading. ITCS (2024)
Gregory Valiant
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis. ITCS (2024)
Tomer Ezra, Michal Feldman, Maya Schlesinger
On the (In)approximability of Combinatorial Contracts. ITCS (2024)
Asaf Petruschka, Shay Sapir, Elad Tzalik
Color Fault-Tolerant Spanners. ITCS (2024)
Prantar Ghosh, Vihan Shah
New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification. ITCS (2024)
C. Ramya, Pratik Shastri
Lower Bounds for Planar Arithmetic Circuits. ITCS (2024)
Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, Preetum Nakkiran
Loss Minimization Yields Multicalibration for Large Neural Networks. ITCS (2024)
Barak Nehoran, Mark Zhandry
A Computational Separation Between Quantum No-Cloning and No-Telegraphing. ITCS (2024)
Hadley Black, Eric Blais, Nathaniel Harms
Testing and Learning Convex Sets in the Ternary Hypercube. ITCS (2024)
Noam Mazor, Rafael Pass
The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity Is False. ITCS (2024)
Nika Haghtalab, Nicole Immorlica, Brendan Lucier, Markus Mobius, Divyarthi Mohan
Communicating with Anecdotes (Extended Abstract). ITCS (2024)
Atanas Dinev, S. Matthew Weinberg
Simple and Optimal Online Contention Resolution Schemes for k-Uniform Matroids. ITCS (2024)
Euiwoong Lee, Pasin Manurangsi
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs. ITCS (2024)
Jason Milionis, Ciamac C. Moallemi, Tim Roughgarden
A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers. ITCS (2024)
Louis Golowich, Tali Kaufman
NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes. ITCS (2024)
Weihao Kong, Mingda Qiao, Rajat Sen
A Combinatorial Approach to Robust PCA. ITCS (2024)
Ishay Haviv
The Chromatic Number of Kneser Hypergraphs via Consensus Division. ITCS (2024)
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm, Manolis Zampetakis
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games. ITCS (2024)
Joseph Slote
Parity vs. AC0 with Simple Quantum Preprocessing. ITCS (2024)
Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha
Quantum Merlin-Arthur and Proofs Without Relative Phase. ITCS (2024)
Tanmay Inamdar, Madhumita Kundu, Pekka Parviainen, M. S. Ramanujan, Saket Saurabh
Exponential-Time Approximation Schemes via Compression. ITCS (2024)
Baptiste Louf, Colin McDiarmid, Fiona Skerman
Modularity and Graph Expansion. ITCS (2024)
Ari Karchmer
Distributional PAC-Learning from Nisan's Natural Proofs. ITCS (2024)
Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk
Determinants vs. Algebraic Branching Programs. ITCS (2024)
Matthias C. Caro, Marcel Hinsche, Marios Ioannou, Alexander Nietner, Ryan Sweke
Classical Verification of Quantum Learning. ITCS (2024)
Jason D. Hartline, Aleck C. Johnsen
Equivocal Blends: Prior Independent Lower Bounds. ITCS (2024)
Teresa Anna Steiner
Differentially Private Approximate Pattern Matching. ITCS (2024)

volume 287, 2024

15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA ITCS 287 (2024)