ITCS A

120 papers

YearTitle / Authors
202617th Innovations in Theoretical Computer Science Conference, ITCS 2026, Bocconi University, Milan, Italy, January 27-30, 2026
Shubhangi Saraf
2026A Combinatorial Characterization of Constant Mixing Time.
Lap Chi Lau, Raymond Liu
2026A General Framework for Low Soundness Homomorphism Testing.
Tushant Mittal, Sourya Roy
2026A Parameterized-Complexity Framework for Finding Local Optima.
Robert Ganian, Hung P. Hoang, Christian Komusiewicz, Nils Morawietz
2026A Simple and Robust Protocol for Distributed Counting.
Edith Cohen, Moshe Shechner, Uri Stemmer
2026AC⁰[p]-Frege Cannot Efficiently Prove That Constant-Depth Algebraic Circuit Lower Bounds Are Hard.
Jiaqi Lu, Rahul Santhanam, Iddo Tzameret
2026Adversarially-Robust Gossip Algorithms for Approximate Quantile and Mean Computations.
Bernhard Haeupler, Marc Kaufmann, Raghu Raman Ravi, Ulysse Schaller
2026An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem.
Marco Aldi, Sevag Gharibian, Dorian Rudolph
2026Analyzing the Economic Impact of Decentralization on Users.
Amit Levy, S. Matthew Weinberg, Chenghan Zhou
2026Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits.
Bill Fefferman, Soumik Ghosh, Wei Zhan
2026Auditability and the Landscape of Distance to Multicalibration.
Nathan Derhake, Siddartha Devic, Dutch Hansen, Kuan Liu, Vatsal Sharan
2026Average Sensitivity of Geometric Algorithms.
Matthijs Ebbens, Yuichi Yoshida
2026Bayesian Perspective on Memorization and Reconstruction.
Haim Kaplan, Yishay Mansour, Kobbi Nissim, Uri Stemmer
2026Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election.
Yi-Jun Chang, Lyuting Chen, Haoran Zhou
2026Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms.
Aadityan Ganesh, Clayton Thomas, S. Matthew Weinberg
2026Classical and Quantum Polynomial Freiman-Ruzsa Algorithms.
Srinivasan Arunachalam, Davi Castro-Silva, Arkopal Dutt, Tom Gur
2026Cloning Games, Black Holes and Cryptography.
Alexander Poremba, Seyoon Ragavan, Vinod Vaikuntanathan
2026Commuting Local Hamiltonians Beyond 2D.
John Bostanci, Yeongwoo Hwang
2026Computing Equilibrium Points of Electrostatic Potentials.
Abheek Ghosh, Paul W. Goldberg, Alexandros Hollender
2026Debordering Closure Results in Determinantal and Pfaffian Ideals.
Anakin Dey, Zeyu Guo
2026Decentralized Data Archival: New Definitions and Constructions.
Elaine Shi, Rose Silver, Changrui Mu
2026Decoding Balanced Linear Codes with Preprocessing.
Andrej Bogdanov, Rohit Chatterjee, Yunqi Li, Prashant Nalini Vasudevan
2026Delaunay Triangulations with Predictions.
Sergio Cabello, Timothy M. Chan, Panos Giannopoulos
2026Differential Privacy from Axioms.
Guy Blanc, William Pires, Toniann Pitassi
2026Diffie-Hellman Key Exchange from Commutativity to Group Laws.
Dung Hoang Duong, Youming Qiao, Chuanqi Zhang
2026Dimension Reduction for Clustering: The Curious Case of Discrete Centers.
Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir, Sandeep Silwal, Di Yue
2026Dimension-Free Correlated Sampling for the Hypersimplex.
Joseph (Seffi) Naor, Nitya Raju, Abhishek Shetty, Aravind Srinivasan, Renata Valieva, David Wajc
2026Discrepancy Beyond Additive Functions with Applications to Fair Division (Extended Abstract).
Alexandros Hollender, Pasin Manurangsi, Raghu Meka, Warut Suksompong
2026Dudeney's Dissection Is Optimal.
Erik D. Demaine, Tonan Kamata, Ryuhei Uehara
2026Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions.
Keerti Choudhary, Amit Kumar, Lakshay Saggi
2026Efficient Catalytic Graph Algorithms.
James Cook, Edward Pyne
2026FPT Approximations for Connected Maximum Coverage.
Tanmay Inamdar, Satyabrata Jana, Madhumita Kundu, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi
2026Fairness in the k-Server Problem.
Mohammadreza Daneshvaramoli, Mohammad Hajiesmaili, Shahin Kamali, Helia Karisani, Cameron Musco
2026Fixed-Parameter Tractable Submodular Maximization over a Matroid.
Shamisa Nematollahi, Adrian Vladu, Junyao Zhao
2026Forrelation Is Extremally Hard.
Uma Girish, Rocco A. Servedio
2026Fourier Sparsity of Delta Functions and Matching Vector PIRs.
Fatemeh Ghasemi, Swastik Kopparty
2026Front Matter, Table of Contents, Preface, Conference Organization.
2026Fully Quantum Computational Entropies (Extended Abstract).
Noam Avidan, Thomas A. Hahn, Joseph M. Renes, Rotem Arnon Friedman
2026General Computation Using Slidable Tiles with Deterministic Global Forces.
Alberto Avila-Jimenez, David Barreda, Sarah-Laurie Evans, Austin Luchsinger, Aiden Massie, Robert Schweller, Evan Tomai, Tim Wylie
2026Hardness of Dynamic Tree Edit Distance and Friends.
Bingbing Hu, Jakob Nogler, Barna Saha
2026Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits.
Hanlin Ren, Yichuan Wang, Yan Zhong
2026Higher-Order Delsarte Dual LPs: Lifting, Constructions and Completeness.
Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones, Nati Linial, Elyassaf Loyfer
2026How to Use Nondeterminism in Cryptography.
Marshall Ball, Peter Crawford-Kahrl
2026Ideal Private Simultaneous Messages Schemes and Their Applications.
Keitaro Hiwatashi, Reo Eriguchi
2026Identity Check Problem for Shallow Quantum Circuits.
Sergey Bravyi, Natalie Parham, Minh C. Tran
2026Identity Testing for Circuits with Exponentiation Gates.
Jiatu Li, Mengdi Wu
2026Improved Rate for Non-Malleable Codes and Time-Lock Puzzles.
Cody Freitag, Ilan Komargodski, Manu Kondapaneni, Jad Silbak
2026Interactive Proofs for Distribution Testing with Conditional Oracles.
Ari Biswas, Mark Bun, Clément L. Canonne, Satchit Sivakumar
2026Intersection Theorems: A Potential Approach to Proof Complexity Lower Bounds.
Yaroslav Alekseev, Nikita Gaevoy
2026Limitations of Membership Queries in Testable Learning.
Jane Lange, Mingda Qiao
2026Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data.
Keller Blackwell, Mary Wootters
2026Linear Matroid Intersection Is in Catalytic Logspace.
Aryan Agarwala, Yaroslav Alekseev, Antoine Vinciguerra
2026Linear Time Encodable Binary Code Achieving GV Bound with Linear Time Encodable Dual Achieving GV Bound.
Martijn Brehm, Nicolas Resch
2026List Decoding Reed-Solomon Codes in the Lee, Euclidean, and Other Metrics.
Chris Peikert, Alexandra Veliche Hostetler
2026Local Transformations of Bipartite Entanglement Are Rigid.
John Bostanci, Tony Metger, Henry Yuen
2026Lower Bounds Beyond DNF of Parities.
Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
2026Lower Bounds and Separations for Torus Polynomials.
Vaibhav Krishan, Sundar Vishwanathan
2026Lower Bounds for Noncommutative Circuits with Low Syntactic Degree.
Pratik Shastri
2026Lower Bounds on FSS from Dynamic Data Structures.
Niv Gilboa, Daniel Weber
2026Lower Bounds on Tree Covers.
Yu Chen, Zihan Tan, Hangyu Xu
2026Markov Chain Robustness.
David Zuckerman
2026Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs.
Mridul Ahi, Keerti Choudhary, Shlok Pande, Pushpraj, Lakshay Saggi
2026Model-Generic Incrementally Verifiable Computation from Updatable BARGs.
Eden Aldema Tshuva, Rotem Oshman
2026Multi-Quadratic Sum-Of-Squares Lower Bounds Imply VNC ¹ ≠ VNP.
Benjamin Rossman, Davidson Zhu
2026Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems.
Shaddin Dughmi, Yusuf Hakan Kalayci, Xinyu Liu
2026New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String.
Lijie Chen, Yang Hu, Hanlin Ren
2026New Bounds for Circular Trace Reconstruction.
Arnav Burudgunte, Paul Valiant, Hongao Wang
2026New Greedy Spanners and Applications.
Elizaveta Popova, Elad Tzalik
2026On Approximating the f-Divergence Between Two Ising Models.
Weiming Feng, Yucheng Fu
2026On Closure Properties of Read-Once Oblivious Algebraic Branching Programs.
Robert Andrews, Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas
2026On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time.
Tsz Chiu Kwok, Zhewei Wei, Mingji Yang
2026On the Complexity of Unique Quantum Witnesses and Quantum Approximate Counting.
Anurag Anshu, Jonas Haferkamp, Yeongwoo Hwang, Quynh T. Nguyen
2026On the PTAS Complexity of Multidimensional Knapsack.
Ilan Doron-Arad, Ariel Kulik, Pasin Manurangsi
2026On the Power of Computationally Sound Interactive Proofs of Proximity.
Hadar Strauss
2026One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts.
Michal Feldman, Yoav Gal Tzur, Tomasz Ponitka, Maya Schlesinger
2026One-Way Functions and Boundary Hardness of Randomized Time-Bounded Kolmogorov Complexity.
Yanyi Liu, Rafael Pass
2026Online Contention Resolution Schemes for Network Revenue Management and Combinatorial Auctions (Extended Abstract).
Will Ma, Calum MacRury, Jingwei Zhang
2026Optimal Two-Round Communication Lower Bound for Graph Connectivity via Pointer Chasing.
Jaikumar Radhakrishnan, Chaitanya Reddy, Rakesh Venkat
2026Optimal White-Box Adversarial Streaming Lower Bounds for Approximating LIS Length.
Anna Gál, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu
2026Oracle Separations for the Quantum-Classical Polynomial Hierarchy.
Avantika Agarwal, Shalev Ben-David
2026Perfect Simulation of Las Vegas Algorithms via Local Computation.
Xinyu Fu, Yonggang Jiang, Yitong Yin
2026Prior-Independent and Subgame Optimal Online Algorithms.
Jason D. Hartline, Aleck C. Johnsen, Anant Shah
2026Pseudodeterministic Algorithms for Minimum Cut Problems.
Aryan Agarwala, Nithin Varma
2026Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals.
Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, Kewen Wu
2026Query Lower Bounds for Correlation Clustering Under Memory Constraints.
Sumegha Garg, Songhua He, Periklis A. Papakonstantinou
2026Random Unitaries in Constant (Quantum) Time.
Ben Foxman, Natalie Parham, Francisca Vasconcelos, Henry Yuen
2026Range Avoidance and Remote Point: New Algorithms and Hardness.
Shengtang Huang, Xin Li, Yan Zhong
2026Range Longest Increasing Subsequence and Its Relatives.
Karthik C. S., Saladi Rahul
2026Recovering Communities in Structured Random Graphs.
Michael Kapralov, Luca Trevisan, Weronika Wrzos-Kaminska
2026Robust Resource Allocation via Competitive Subsidies.
David X. Lin, Giannis Fikioris, Siddhartha Banerjee, Éva Tardos
2026Robust Streaming Against Low-Memory Adversaries.
Omri Ben-Eliezer, Krzysztof Onak, Sandeep Silwal
2026Samplability Makes Learning Easier.
Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan
2026Semi-Random Graphs, Robust Asymmetry, and Reconstruction.
Julian Asilis, Xi Chen, Dutch Hansen, Shang-Hua Teng
2026Simplicial Covering Dimension of Extremal Concept Classes.
Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak
2026Slice Rank and Partition Rank of the Determinant.
Amichai Lampert, Guy Moshkovitz
2026Smoothed Analysis of Dynamic Graph Algorithms.
Uri Meir, Ami Paz
2026Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion.
Yingxi Li, Ellen Vitercik, Mingwei Yang
2026Supercritical Tradeoff Between Size and Depth for Resolution over Parities.
Dmitry Itsykson, Alexander Knop
2026Symmetric Algebraic Circuits and Homomorphism Polynomials.
Anuj Dawar, Benedikt Pago, Tim Seppelt
2026Symmetric Quantum Computation.
Davi Castro-Silva, Tom Gur, Sergii Strelchuk
2026Testable Algorithms for Approximately Counting Edges and Triangles in Sublinear Time and Space.
Talya Eden, Ronitt Rubinfeld, Arsen Vasilyan
2026Testing Classical Properties from Quantum Data.
Matthias C. Caro, Preksha Naik, Joseph Slote
2026The Curious Case of "XOR Repetition" of Monogamy-Of-Entanglement Games.
Andrea Coladangelo, Qipeng Liu, Ziyi Xie
2026The Hardness of Learning Quantum Circuits and Its Cryptographic Applications.
Bill Fefferman, Soumik Ghosh, Makrand Sinha, Henry Yuen
2026The Learning Stabilizers with Noise Problem.
Alexander Poremba, Yihui Quek, Peter W. Shor
2026The Mixed Birth-Death/death-Birth Moran Process (Extended Abstract).
David A. Brewster, Yichen Huang, Michael Mitzenmacher, Martin A. Nowak
2026The Pure-State Consistency of Local Density Matrices Problem: In PSPACE and Complete for a Class Between QMA and QMA(2).
Jonas Kamminga, Dorian Rudolph
2026The Secretary Problem with Predictions and a Chosen Order.
Helia Karisani, Mohammadreza Daneshvaramoli, Hedyeh Beyhaghi, Mohammad Hajiesmaili, Cameron Musco
2026Time and Space Efficient Deterministic List Decoding.
Joshua Cook, Dana Moshkovitz
2026Total Search Problems in ZPP.
Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, Weiqiang Yuan
2026Triangle Detection in H-Free Graphs.
Amir Abboud, Ron Safier, Nathan Wallheimer
2026Two Bases Suffice for QMA ₁-Completeness.
Henry Ma, Anand Natarajan
2026Unconditional Pseudorandomness Against Shallow Quantum Circuits.
Soumik Ghosh, Sathyawageeswar Subramanian, Wei Zhan
2026Unconditional Quantum Advantage for Sampling with Shallow Circuits.
Adam Bene Watts, Natalie Parham
2026Uniformity Testing Under User-Level Local Privacy.
Clément L. Canonne, Abigail Gentle, Vikrant Singhal
2026Unitary Complexity and the Uhlmann Transformation Problem.
John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, Henry Yuen
2026Universally Optimal Streaming Algorithm for Random Walks in Dense Graphs.
Klim Efremenko, Gillat Kol, Raghuvansh R. Saxena, Zhijun Zhang
2026Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem.
Jin-Yi Cai, Ben Young
2026Weighted Chairman Assignment and Flow-Time Scheduling.
Siyue Liu, Victor Reis
2026Zero-Freeness Is All You Need: A Weitz-Type FPTAS for the Entire Lee-Yang Zero-Free Region.
Shuai Shao, Ke Shi