Portal - ITCS 2023

ITCS 2023	January 10-13, 2023, MIT, Cambridge, Massachusetts, USA
14th Innovations in Theoretical Computer Science Conference (ITCS 2023) Yael Tauman Kalai (Ed.)
ISBN 978-3-95977-263-1, LIPICS Vol. 251	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 33 MB)
Search Publication Server

Authors

Chakraborty, Diptarka

Chakraborty, Sourav

Chakraborty, Suvradip

Chatterjee, Abhranil

Chattopadhyay, Arkadev

Coregliano, Leonardo Nagami

Dobrokhotova-Maikova, Natalia

Jeronimo, Fernando Granha

Kozachinskiy, Alexander

Krauthgamer, Robert

Kretschmer, William

Krishnaswamy, Ravishankar

Mitchell, Joseph S. B.

Papadimitriou, Christos

Sandhu, Juspreet Singh

Sanyal, Swagato

Sarlós, Tamás

Saurabh, Nitin

Saxena, Raghuvansh R.

Schwartzbach, Nikolaj I.

Vassilvitskii, Sergei

Velusamy, Santhoshini

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Tauman Kalai, Yael

Abstract | Document (639 KB) | BibTeX

Worst-Case to Expander-Case Reductions

Authors: Abboud, Amir ; Wallheimer, Nathan

Abstract | Document (879 KB) | BibTeX

Matroid Partition Property and the Secretary Problem

Authors: Abdolazimi, Dorna ; Karlin, Anna R. ; Klein, Nathan ; Oveis Gharan, Shayan

Abstract | Document (635 KB) | BibTeX

Kolmogorov Complexity Characterizes Statistical Zero Knowledge

Authors: Allender, Eric ; Hirahara, Shuichi ; Tirumala, Harsha

Abstract | Document (845 KB) | BibTeX

Communication Complexity of Inner Product in Symmetric Normed Spaces

Authors: Andoni, Alexandr ; Błasiok, Jarosław ; Filtser, Arnold

Abstract | Document (822 KB) | BibTeX

Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations

Authors: Anshu, Anurag ; Metger, Tony

Abstract | Document (585 KB) | BibTeX

On Identity Testing and Noncommutative Rank Computation over the Free Skew Field

Authors: Arvind, V. ; Chatterjee, Abhranil ; Ghosal, Utsab ; Mukhopadhyay, Partha ; Ramya, C.

Abstract | Document (804 KB) | BibTeX

All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method

Authors: Assadi, Sepehr ; Bernstein, Aaron ; Langley, Zachary

Abstract | Document (846 KB) | BibTeX

A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators

Authors: Attias, Idan ; Cohen, Edith ; Shechner, Moshe ; Stemmer, Uri

Abstract | Document (849 KB) | BibTeX

Making Auctions Robust to Aftermarkets

Authors: Babaioff, Moshe ; Immorlica, Nicole ; Li, Yingkai ; Lucier, Brendan

Abstract | Document (744 KB) | BibTeX

Efficiently Testable Circuits

Authors: Baig, Mirza Ahad ; Chakraborty, Suvradip ; Dziembowski, Stefan ; Gałązka, Małgorzata ; Lizurej, Tomasz ; Pietrzak, Krzysztof

Abstract | Document (1,289 KB) | BibTeX

Strategyproof Scheduling with Predictions

Authors: Balkanski, Eric ; Gkatzelis, Vasilis ; Tan, Xizhi

Abstract | Document (954 KB) | BibTeX

Graph Searching with Predictions

Authors: Banerjee, Siddhartha ; Cohen-Addad, Vincent ; Gupta, Anupam ; Li, Zhouzi

Abstract | Document (955 KB) | BibTeX

On Computing Homological Hitting Sets

Authors: Bauer, Ulrich ; Rathod, Abhishek ; Zehavi, Meirav

Abstract | Document (1,243 KB) | BibTeX

On Disperser/Lifting Properties of the Index and Inner-Product Functions

Authors: Beame, Paul ; Koroth, Sajin

Abstract | Document (876 KB) | BibTeX

Is This Correct? Let’s Check!

Authors: Ben-Eliezer, Omri ; Mikulincer, Dan ; Mossel, Elchanan ; Sudan, Madhu

Abstract | Document (670 KB) | BibTeX

Online Learning and Bandits with Queried Hints

Authors: Bhaskara, Aditya ; Gollapudi, Sreenivas ; Im, Sungjin ; Kollias, Kostas ; Munagala, Kamesh

Abstract | Document (863 KB) | BibTeX

Bootstrapping Homomorphic Encryption via Functional Encryption

Authors: Bitansky, Nir ; Solomon, Tomer

Abstract | Document (812 KB) | BibTeX

Certification with an NP Oracle

Authors: Blanc, Guy ; Koch, Caleb ; Lange, Jane ; Strassle, Carmen ; Tan, Li-Yang

Abstract | Document (931 KB) | BibTeX

Matrix Multiplication via Matrix Groups

Authors: Blasiak, Jonah ; Cohn, Henry ; Grochow, Joshua A. ; Pratt, Kevin ; Umans, Chris

Abstract | Document (715 KB) | BibTeX

Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free

Authors: Bodwin, Greg ; Dinitz, Michael ; Nazari, Yasamin

Abstract | Document (760 KB) | BibTeX

Opponent Indifference in Rating Systems: A Theoretical Case for Sonas

Authors: Bodwin, Greg ; Zhang, Forest

Abstract | Document (800 KB) | BibTeX

PPP-Completeness and Extremal Combinatorics

Authors: Bourneuf, Romain ; Folwarczný, Lukáš ; Hubáček, Pavel ; Rosen, Alon ; Schwartzbach, Nikolaj I.

Abstract | Document (906 KB) | BibTeX

On Low-End Obfuscation and Learning

Authors: Boyle, Elette ; Ishai, Yuval ; Meyer, Pierre ; Robere, Robert ; Yehuda, Gal

Abstract | Document (967 KB) | BibTeX

On the Computational Hardness Needed for Quantum Cryptography

Authors: Brakerski, Zvika ; Canetti, Ran ; Qian, Luowen

Abstract | Document (833 KB) | BibTeX

Improved Monotonicity Testers via Hypercube Embeddings

Authors: Braverman, Mark ; Khot, Subhash ; Kindler, Guy ; Minzer, Dor

Abstract | Document (814 KB) | BibTeX

Rounding via Low Dimensional Embeddings

Authors: Braverman, Mark ; Minzer, Dor

Abstract | Document (908 KB) | BibTeX

Counting Subgraphs in Somewhere Dense Graphs

Authors: Bressan, Marco ; Goldberg, Leslie Ann ; Meeks, Kitty ; Roth, Marc

Abstract | Document (688 KB) | BibTeX

Rigidity for Monogamy-Of-Entanglement Games

Authors: Broadbent, Anne ; Culf, Eric

Abstract | Document (983 KB) | BibTeX

Quantum Majority Vote

Authors: Buhrman, Harry ; Linden, Noah ; Mančinska, Laura ; Montanaro, Ashley ; Ozols, Maris

Abstract | Document (403 KB) | BibTeX

TFNP Characterizations of Proof Systems and Monotone Circuits

Authors: Buss, Sam ; Fleming, Noah ; Impagliazzo, Russell

Abstract | Document (995 KB) | BibTeX

Clustering Permutations: New Techniques with Streaming Applications

Authors: Chakraborty, Diptarka ; Das, Debarati ; Krauthgamer, Robert

Abstract | Document (842 KB) | BibTeX

Certificate Games

Authors: Chakraborty, Sourav ; Gál, Anna ; Laplante, Sophie ; Mittal, Rajat ; Sunny, Anupa

Abstract | Document (836 KB) | BibTeX

Lifting to Parity Decision Trees via Stifling

Authors: Chattopadhyay, Arkadev ; Mande, Nikhil S. ; Sanyal, Swagato ; Sherif, Suhail

Abstract | Document (833 KB) | BibTeX

New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method

Authors: Chen, Lijie

Abstract | Document (820 KB) | BibTeX

Black-Box Constructive Proofs Are Unavoidable

Authors: Chen, Lijie ; Williams, Ryan ; Yang, Tianqi

Abstract | Document (1,021 KB) | BibTeX

Necessary Conditions in Multi-Server Differential Privacy

Authors: Cheu, Albert ; Yan, Chao

Abstract | Document (1,140 KB) | BibTeX

Quantum Algorithms and the Power of Forgetting

Authors: Childs, Andrew M. ; Coudron, Matthew ; Gilani, Amin Shiraz

Abstract | Document (914 KB) | BibTeX

A New Conjecture on Hardness of 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems

Authors: Chuzhoy, Julia ; Dalirrooyfard, Mina ; Grinberg, Vadim ; Tan, Zihan

Abstract | Document (761 KB) | BibTeX

Generalized Private Selection and Testing with High Confidence

Authors: Cohen, Edith ; Lyu, Xin ; Nelson, Jelani ; Sarlós, Tamás ; Stemmer, Uri

Abstract | Document (862 KB) | BibTeX

Exact Completeness of LP Hierarchies for Linear Codes

Authors: Coregliano, Leonardo Nagami ; Jeronimo, Fernando Granha ; Jones, Chris

Abstract | Document (757 KB) | BibTeX

HappyMap : A Generalized Multicalibration Method

Authors: Deng, Zhun ; Dwork, Cynthia ; Zhang, Linjun

Abstract | Document (909 KB) | BibTeX

Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization

Authors: Dey, Papri ; Kannan, Ravi ; Ryder, Nick ; Srivastava, Nikhil

Abstract | Document (733 KB) | BibTeX

Constant-Depth Sorting Networks

Authors: Dobrokhotova-Maikova, Natalia ; Kozachinskiy, Alexander ; Podolskii, Vladimir

Abstract | Document (817 KB) | BibTeX

Rigidity in Mechanism Design and Its Applications

Authors: Dobzinski, Shahar ; Shaulker, Ariel

Abstract | Document (741 KB) | BibTeX

Beeping Shortest Paths via Hypergraph Bipartite Decomposition

Authors: Dufoulon, Fabien ; Emek, Yuval ; Gelles, Ran

Abstract | Document (860 KB) | BibTeX

Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds

Authors: Efremenko, Klim ; Kol, Gillat ; Paramonov, Dmitry ; Saxena, Raghuvansh R.

Abstract | Document (817 KB) | BibTeX

Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks

Authors: El-Hayek, Antoine ; Henzinger, Monika ; Schmid, Stefan

Abstract | Document (1,052 KB) | BibTeX

Differentially Private Continual Releases of Streaming Frequency Moment Estimations

Authors: Epasto, Alessandro ; Mao, Jieming ; Medina, Andres Munoz ; Mirrokni, Vahab ; Vassilvitskii, Sergei ; Zhong, Peilin

Abstract | Document (887 KB) | BibTeX

A Subpolynomial-Time Algorithm for the Free Energy of One-Dimensional Quantum Systems in the Thermodynamic Limit

Authors: Fawzi, Hamza ; Fawzi, Omar ; Scalet, Samuel O.

Abstract | Document (633 KB) | BibTeX

Expander Decomposition in Dynamic Streams

Authors: Filtser, Arnold ; Kapralov, Michael ; Makarov, Mikhail

Abstract | Document (655 KB) | BibTeX

On Flipping the Fréchet Distance

Authors: Filtser, Omrit ; Goswami, Mayank ; Mitchell, Joseph S. B. ; Polishchuk, Valentin

Abstract | Document (1,134 KB) | BibTeX

Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence

Authors: Gaitonde, Jason ; Li, Yingkai ; Light, Bar ; Lucier, Brendan ; Slivkins, Aleksandrs

Abstract | Document (342 KB) | BibTeX

Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover Interactive Proofs into Unentanglement

Authors: Gharibian, Sevag ; Rudolph, Dorian

Abstract | Document (969 KB) | BibTeX

Algorithms with More Granular Differential Privacy Guarantees

Authors: Ghazi, Badih ; Kumar, Ravi ; Manurangsi, Pasin ; Steinke, Thomas

Abstract | Document (939 KB) | BibTeX

Private Counting of Distinct and k-Occurring Items in Time Windows

Authors: Ghazi, Badih ; Kumar, Ravi ; Nelson, Jelani ; Manurangsi, Pasin

Abstract | Document (817 KB) | BibTeX

Is Untrusted Randomness Helpful?

Authors: Girish, Uma ; Raz, Ran ; Zhan, Wei

Abstract | Document (705 KB) | BibTeX

Consensus Division in an Arbitrary Ratio

Authors: Goldberg, Paul ; Li, Jiawei

Abstract | Document (906 KB) | BibTeX

An Algorithmic Bridge Between Hamming and Levenshtein Distances

Authors: Goldenberg, Elazar ; Kociumaka, Tomasz ; Krauthgamer, Robert ; Saha, Barna

Abstract | Document (990 KB) | BibTeX

On Interactive Proofs of Proximity with Proof-Oblivious Queries

Authors: Goldreich, Oded ; Rothblum, Guy N. ; Skverer, Tal

Abstract | Document (729 KB) | BibTeX

Loss Minimization Through the Lens Of Outcome Indistinguishability

Authors: Gopalan, Parikshit ; Hu, Lunjia ; Kim, Michael P. ; Reingold, Omer ; Wieder, Udi

Abstract | Document (722 KB) | BibTeX

List Agreement Expansion from Coboundary Expansion

Authors: Gotlib, Roy ; Kaufman, Tali

Abstract | Document (770 KB) | BibTeX

Asynchronous Multi-Party Quantum Computation

Authors: Goyal, Vipul ; Liu-Zhang, Chen-Da ; Raizes, Justin ; Ribeiro, João

Abstract | Document (721 KB) | BibTeX

Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm

Authors: Grandoni, Fabrizio ; Mathieu, Claire ; Zhou, Hang

Abstract | Document (713 KB) | BibTeX

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

Authors: Grewal, Sabee ; Iyer, Vishnu ; Kretschmer, William ; Liang, Daniel

Abstract | Document (831 KB) | BibTeX

Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments

Authors: Gupta, Varun ; Krishnaswamy, Ravishankar ; Sandeep, Sai ; Sundaresan, Janani

Abstract | Document (763 KB) | BibTeX

Incompressiblity and Next-Block Pseudoentropy

Authors: Haitner, Iftach ; Mazor, Noam ; Silbak, Jad

Abstract | Document (743 KB) | BibTeX

Downward Self-Reducibility in TFNP

Authors: Harsha, Prahladh ; Mitropolsky, Daniel ; Rosen, Alon

Abstract | Document (2,012 KB) | BibTeX

Symmetric Formulas for Products of Permutations

Authors: He, William ; Rossman, Benjamin

Abstract | Document (865 KB) | BibTeX

A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems

Authors: Henzinger, Monika ; Jin, Billy ; Peng, Richard ; Williamson, David P.

Abstract | Document (1,032 KB) | BibTeX

Learning Versus Pseudorandom Generators in Constant Parallel Time

Authors: Hirahara, Shuichi ; Nanashima, Mikito

Abstract | Document (685 KB) | BibTeX

Secure Distributed Network Optimization Against Eavesdroppers

Authors: Hitron, Yael ; Parter, Merav ; Yogev, Eylon

Abstract | Document (807 KB) | BibTeX

Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes

Authors: Hu, Lunjia ; Peale, Charlotte

Abstract | Document (1,159 KB) | BibTeX

Recovery from Non-Decomposable Distance Oracles

Authors: Hu, Zhuangfei ; Li, Xinda ; Woodruff, David P. ; Zhang, Hongyang ; Zhang, Shufan

Abstract | Document (1,079 KB) | BibTeX

Karchmer-Wigderson Games for Hazard-Free Computation

Authors: Ikenmeyer, Christian ; Komarath, Balagopal ; Saurabh, Nitin

Abstract | Document (802 KB) | BibTeX

Learning Reserve Prices in Second-Price Auctions

Authors: Jin, Yaonan ; Lu, Pinyan ; Xiao, Tao

Abstract | Document (985 KB) | BibTeX

The Complexity of Infinite-Horizon General-Sum Stochastic Games

Authors: Jin, Yujia ; Muthukumar, Vidya ; Sidford, Aaron

Abstract | Document (1,245 KB) | BibTeX

Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses

Authors: Jones, Chris ; Marwaha, Kunal ; Sandhu, Juspreet Singh ; Shi, Jonathan

Abstract | Document (1,001 KB) | BibTeX

Garland’s Technique for Posets and High Dimensional Grassmannian Expanders

Authors: Kaufman, Tali ; Tessler, Ran J.

Abstract | Document (762 KB) | BibTeX

Making Decisions Under Outcome Performativity

Authors: Kim, Michael P. ; Perdomo, Juan C.

Abstract | Document (621 KB) | BibTeX

Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

Authors: Kol, Gillat ; Paramonov, Dmitry ; Saxena, Raghuvansh R. ; Yu, Huacheng

Abstract | Document (757 KB) | BibTeX

False Consensus, Information Theory, and Prediction Markets

Authors: Kong, Yuqing ; Schoenebeck, Grant

Abstract | Document (1,093 KB) | BibTeX

Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More

Authors: Liu, Qipeng

Abstract | Document (721 KB) | BibTeX

Vertex Sparsification for Edge Connectivity in Polynomial Time

Authors: Liu, Yang P.

Abstract | Document (738 KB) | BibTeX

Fractional Certificates for Bounded Functions

Authors: Lovett, Shachar ; Zhang, Jiapeng

Abstract | Document (693 KB) | BibTeX

Improved Inapproximability of VC Dimension and Littlestone’s Dimension via (Unbalanced) Biclique

Authors: Manurangsi, Pasin

Abstract | Document (743 KB) | BibTeX

Resilience of 3-Majority Dynamics to Non-Uniform Schedulers

Authors: Meir, Uri ; Oshman, Rotem ; Shayevitz, Ofer ; Volkov, Yuval

Abstract | Document (700 KB) | BibTeX

Proofs of Quantumness from Trapdoor Permutations

Authors: Morimae, Tomoyuki ; Yamakawa, Takashi

Abstract | Document (697 KB) | BibTeX

Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP

Authors: Pasarkar, Amol ; Papadimitriou, Christos ; Yannakakis, Mihalis

Abstract | Document (797 KB) | BibTeX

The Strength of Equality Oracles in Communication

Authors: Pitassi, Toniann ; Shirley, Morgan ; Shraibman, Adi

Abstract | Document (793 KB) | BibTeX

Quantum Proofs of Deletion for Learning with Errors

Authors: Poremba, Alexander

Abstract | Document (851 KB) | BibTeX

Online Pen Testing

Authors: Qiao, Mingda ; Valiant, Gregory

Abstract | Document (858 KB) | BibTeX

Decision-Making Under Miscalibration

Authors: Rothblum, Guy N. ; Yona, Gal

Abstract | Document (922 KB) | BibTeX

Beyond Worst-Case Budget-Feasible Mechanism Design

Authors: Rubinstein, Aviad ; Zhao, Junyao

Abstract | Document (909 KB) | BibTeX

Is It Easier to Count Communities Than Find Them?

Authors: Rush, Cynthia ; Skerman, Fiona ; Wein, Alexander S. ; Yang, Dana

Abstract | Document (764 KB) | BibTeX

An Improved Lower Bound for Matroid Intersection Prophet Inequalities

Authors: Saxena, Raghuvansh R. ; Velusamy, Santhoshini ; Weinberg, S. Matthew

Abstract | Document (835 KB) | BibTeX

Unitary Property Testing Lower Bounds by Polynomials

Authors: She, Adrian ; Yuen, Henry

Abstract | Document (724 KB) | BibTeX

What Can Cryptography Do for Decentralized Mechanism Design?

Authors: Shi, Elaine ; Chung, Hao ; Wu, Ke

Abstract | Document (866 KB) | BibTeX

Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices

Authors: Venkat, Prayaag

Abstract | Document (728 KB) | BibTeX

On Oracles and Algorithmic Methods for Proving Lower Bounds

Authors: Vyas, Nikhil ; Williams, Ryan

Abstract | Document (945 KB) | BibTeX

The Time Complexity of Consensus Under Oblivious Message Adversaries

Authors: Winkler, Kyrill ; Paz, Ami ; Rincon Galeana, Hugo ; Schmid, Stefan ; Schmid, Ulrich

Abstract | Document (955 KB) | BibTeX

Exponential Separations Using Guarded Extension Variables

Authors: Yolcu, Emre ; Heule, Marijn J. H.

Abstract | Document (855 KB) | BibTeX

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI

14th Innovations in Theoretical Computer Science Conference (ITCS 2023)