default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID15th ITCS 2024: Berkeley, CA, USA
- Venkatesan Guruswami
:
15th Innovations in Theoretical Computer Science Conference, ITCS 2024, Berkeley, CA, USA, January 30 - February 2, 2024. LIPIcs 287, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2024, ISBN 978-3-95977-309-6 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:24
- Scott Aaronson, Harry Buhrman, William Kretschmer:
A Qubit, a Coin, and an Advice String Walk into a Relational Problem. 1:1-1:24 - Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou:
Quantum Pseudoentanglement. 2:1-2:21 - Maryam Aliakbarpour, Rose Silver, Thomas Steinke, Jonathan R. Ullman:
Differentially Private Medians and Interior Points for Non-Pathological Data. 3:1-3:21 - Josh Alman, Ethan Turok, Hantao Yu, Hengzhi Zhang:
Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming. 4:1-4:23 - Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm, Manolis Zampetakis:
On the Complexity of Computing Sparse Equilibria and Lower Bounds for No-Regret Learning in Games. 5:1-5:24 - Prabhanjan Ananth, Yao-Ting Lin, Henry Yuen:
Pseudorandom Strings from Pseudorandom Quantum States. 6:1-6:22 - Sayan Bandyapadhyay, Anil Maheshwari, Sasanka Roy, Michiel Smid, Kasturi R. Varadarajan:
Geometric Covering via Extraction Theorem. 7:1-7:20 - Siddharth Barman, Anand Krishna, Pooja Kulkarni, Shivika Narang:
Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations. 8:1-8:23 - Roozbeh Bassirian, Bill Fefferman, Kunal Marwaha:
Quantum Merlin-Arthur and Proofs Without Relative Phase. 9:1-9:19 - Gabriel Bathie, R. Ryan Williams:
Towards Stronger Depth Lower Bounds. 10:1-10:24 - Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova:
Property Testing with Online Adversaries. 11:1-11:25 - Aaron Bernstein, Greg Bodwin, Nicole Wein:
Are There Graphs Whose Shortest Path Structure Requires Large Edge Weights? 12:1-12:22 - Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff:
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. 13:1-13:24 - Kaartik Bhushan, Venkata Koppula, Manoj Prabhakaran:
Homomorphic Indistinguishability Obfuscation and Its Applications. 14:1-14:21 - Hadley Black, Eric Blais, Nathaniel Harms:
Testing and Learning Convex Sets in the Ternary Hypercube. 15:1-15:21 - Keller Blackwell, Mary Wootters:
A Characterization of Optimal-Rate Linear Homomorphic Secret Sharing Schemes, and Applications. 16:1-16:20 - Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, Preetum Nakkiran:
Loss Minimization Yields Multicalibration for Large Neural Networks. 17:1-17:21 - Avrim Blum, Melissa Dutz:
Winning Without Observing Payoffs: Exploiting Behavioral Biases to Win Nearly Every Round. 18:1-18:18 - Greg Bodwin, Henry L. Fleischmann:
Spanning Adjacency Oracles in Sublinear Time. 19:1-19:21 - Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam:
Discreteness of Asymptotic Tensor Ranks (Extended Abstract). 20:1-20:14 - Jop Briët, Harry Buhrman, Davi Castro-Silva, Niels M. P. Neumann:
Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract). 21:1-21:11 - Karl Bringmann, Allan Grønlund, Marvin Künnemann, Kasper Green Larsen:
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. 22:1-22:25 - Clément L. Canonne, Yucheng Sun:
Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine. 23:1-23:24 - Matthias C. Caro, Marcel Hinsche, Marios Ioannou, Alexander Nietner, Ryan Sweke:
Classical Verification of Quantum Learning. 24:1-24:23 - Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha:
Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning. 25:1-25:19 - Yi-Jun Chang:
The Distributed Complexity of Locally Checkable Labeling Problems Beyond Paths and Trees. 26:1-26:25 - Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk:
Determinants vs. Algebraic Branching Programs. 27:1-27:13 - Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani:
Extractors for Polynomial Sources over 𝔽2. 28:1-28:24 - Eshan Chattopadhyay, Jyun-Jie Liao:
Recursive Error Reduction for Regular Branching Programs. 29:1-29:20 - Zongchen Chen, Elchanan Mossel:
Influence Maximization in Ising Models. 30:1-30:14 - 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. 31:1-31:23 - Justin Y. Chen, Piotr Indyk, David P. Woodruff:
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions. 32:1-32:22 - Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio:
Testing Intersecting and Union-Closed Families. 33:1-33:23 - Alessandro Chiesa, Ziyi Guan, Burcu Yildiz:
On Parallel Repetition of PCPs. 34:1-34:14 - Romain Cosson, Laurent Massoulié:
Collective Tree Exploration via Potential Function Method. 35:1-35:22 - Varsha Dani, Thomas P. Hayes, Seth Pettie, Jared Saia:
Fraud Detection for Random Walks. 36:1-36:22 - Constantinos Daskalakis, Noah Golowich, Nika Haghtalab, Abhishek Shetty:
Smooth Nash Equilibria: Algorithms and Complexity. 37:1-37:22 - Erik D. Demaine, Yael Kirkpatrick, Rebecca Lin:
Graph Threading. 38:1-38:18 - Atanas Dinev, S. Matthew Weinberg:
Simple and Optimal Online Contention Resolution Schemes for k-Uniform Matroids. 39:1-39:23 - Nico Döttling, Tamer Mour:
On the Black-Box Complexity of Correlation Intractability. 40:1-40:24 - Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Peter Robinson:
The Message Complexity of Distributed Graph Optimization. 41:1-41:26 - Fabien Dufoulon, Michael Moorman, William K. Moses Jr., Gopal Pandurangan:
Time- and Communication-Efficient Overlay Network Construction via Gossip. 42:1-42:23 - Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Gorav Jindal, Vladimir Lysikov:
Homogeneous Algebraic Complexity Theory and Algebraic Formulas. 43:1-43:23 - Tomer Ezra, Michal Feldman, Maya Schlesinger:
On the (In)approximability of Combinatorial Contracts. 44:1-44:22 - Yumou Fei, Leslie Ann Goldberg, Pinyan Lu:
Two-State Spin Systems with Negative Interactions. 45:1-45:13 - Rex Fernando, Yuval Gelles, Ilan Komargodski:
Scalable Distributed Agreement from LWE: Byzantine Agreement, Broadcast, and Leader Election. 46:1-46:23 - Renato Ferreira Pinto Jr., Nathaniel Harms:
Distribution Testing with a Confused Collector. 47:1-47:14 - Yuval Filmus, Edward A. Hirsch, Artur Riazanov, Alexander Smal, Marc Vinyals:
Proving Unsatisfiability with Hitting Formulas. 48:1-48:20 - Nick Fischer, Piotr Kaliciak, Adam Polak:
Deterministic 3SUM-Hardness. 49:1-49:24 - Lukás Folwarczný, Mika Göös, Pavel Hubácek, Gilbert Maystre, Weiqiang Yuan:
One-Way Functions vs. TFNP: Simpler and Improved. 50:1-50:14 - Rafael M. Frongillo, Maneesha Papireddygari, Bo Waggoner:
An Axiomatic Characterization of CFMMs and Equivalence to Prediction Markets. 51:1-51:21 - Haosen Ge, Hamsa Bastani, Osbert Bastani:
Rethinking Fairness for Human-AI Collaboration (Extended Abstract). 52:1-52:1 - Prantar Ghosh, Vihan Shah:
New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification. 53:1-53:22 - Louis Golowich, Tali Kaufman:
NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes. 54:1-54:23 - Gramoz Goranci, Monika Henzinger, Harald Räcke, Sushant Sachdeva, A. R. Sricharan:
Electrical Flows for Polylogarithmic Competitive Oblivious Routing. 55:1-55:22 - Mayank Goswami, Riko Jacob:
An Algorithm for Bichromatic Sorting with Polylog Competitive Ratio. 56:1-56:17 - Nika Haghtalab, Nicole Immorlica, Brendan Lucier, Markus Mobius, Divyarthi Mohan:
Communicating with Anecdotes (Extended Abstract). 57:1-57:2 - Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman:
An Improved Protocol for ExactlyN with More Than 3 Players. 58:1-58:23 - Jason D. Hartline, Aleck C. Johnsen:
Equivocal Blends: Prior Independent Lower Bounds. 59:1-59:21 - Ishay Haviv:
The Chromatic Number of Kneser Hypergraphs via Consensus Division. 60:1-60:17 - Lisa Hellerstein, Naifeng Liu, Kevin Schewior:
Quickly Determining Who Won an Election. 61:1-61:14 - Monika Henzinger, Barna Saha, Martin P. Seybold, Christopher Ye:
On the Complexity of Algorithms with Predictions for Dynamic Graph Problems. 62:1-62:25 - Pavel Hubácek, Erfan Khaniki, Neil Thapen:
TFNP Intersections Through the Lens of Feasible Disjunction. 63:1-63:24 - Tanmay Inamdar, Madhumita Kundu, Pekka Parviainen, M. S. Ramanujan, Saket Saurabh:
Exponential-Time Approximation Schemes via Compression. 64:1-64:22 - Ragesh Jaiswal, Amit Kumar, Jatin Yadav:
FPT Approximation for Capacitated Sum of Radii. 65:1-65:21 - Ce Jin, R. Ryan Williams, Nathaniel Young:
A VLSI Circuit Model Accounting for Wire Delay. 66:1-66:22 - Thomas Karam:
Small Sunflowers and the Structure of Slice Rank Decompositions. 67:1-67:22 - Ari Karchmer:
Distributional PAC-Learning from Nisan's Natural Proofs. 68:1-68:23 - Ohad Klein, Joseph Slote, Alexander Volberg, Haonan Zhang:
Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality. 69:1-69:22 - Weihao Kong, Mingda Qiao, Rajat Sen:
A Combinatorial Approach to Robust PCA. 70:1-70:22 - Euiwoong Lee, Pasin Manurangsi:
Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs. 71:1-71:17 - Xingjian Li, Qipeng Liu, Angelos Pelecanos, Takashi Yamakawa:
Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle. 72:1-72:19 - Minming Li, Peter Robinson, Xianbin Zhu:
Dynamic Maximal Matching in Clique Networks. 73:1-73:21 - Yuhao Li, William Pires, Robert Robere:
Intersection Classes in TFNP and Proof Complexity. 74:1-74:22 - Jiawei Li:
Total NP Search Problems with Abundant Solutions. 75:1-75:23 - Roi Livni:
Making Progress Based on False Discoveries. 76:1-76:18 - Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Meirav Zehavi:
Kernelization of Counting Problems. 77:1-77:23 - Baptiste Louf, Colin McDiarmid, Fiona Skerman:
Modularity and Graph Expansion. 78:1-78:21 - Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang:
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions. 79:1-79:23 - Noam Mazor, Rafael Pass:
The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity Is False. 80:1-80:20 - Jason Milionis, Ciamac C. Moallemi, Tim Roughgarden:
A Myersonian Framework for Optimal Liquidity Provision in Automated Market Makers. 81:1-81:19 - Barak Nehoran, Mark Zhandry:
A Computational Separation Between Quantum No-Cloning and No-Telegraphing. 82:1-82:23 - Ofer Neiman, Idan Shabat:
On the Size Overhead of Pairwise Spanners. 83:1-83:22 - Rian Neogi, Kanstantsin Pashkovich, Chaitanya Swamy:
Budget-Feasible Mechanism Design: Simpler, Better Mechanisms and General Payment Constraints. 84:1-84:22 - Aleksandar Nikolov, Haohua Tang:
General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation. 85:1-85:23 - Charlotte Out, Nicolás Rivera, Thomas Sauerwald, John Sylvester:
Rumors with Changing Credibility. 86:1-86:23 - Shir Peleg, Amir Shpilka, Ben Lee Volk:
Tensor Reconstruction Beyond Constant Rank. 87:1-87:20 - Asaf Petruschka, Shay Sapir, Elad Tzalik:
Color Fault-Tolerant Spanners. 88:1-88:17 - Kevin Pratt:
On Generalized Corners and Matrix Multiplication. 89:1-89:17 - Aaron (Louie) Putterman, Edward Pyne:
Pseudorandom Linear Codes Are List-Decodable to Capacity. 90:1-90:21 - C. Ramya, Pratik Shastri:
Lower Bounds for Planar Arithmetic Circuits. 91:1-91:22 - Joseph Slote:
Parity vs. AC0 with Simple Quantum Preprocessing. 92:1-92:21 - Zhao Song, Lichen Zhang, Ruizhe Zhang:
Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time. 93:1-93:15 - Teresa Anna Steiner:
Differentially Private Approximate Pattern Matching. 94:1-94:18 - Iddo Tzameret, Luming Zhang:
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness. 95:1-95:22 - Gregory Valiant:
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis. 96:1-96:13 - Adam Bene Watts, John Bostanci:
Quantum Event Learning and Gentle Random Measurements. 97:1-97:22 - Ke Wu, Elaine Shi, Hao Chung:
Maximizing Miner Revenue in Transaction Fee Mechanism Design. 98:1-98:23 - Huacheng Yu, Wei Zhan:
Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions. 99:1-99:15 - Huacheng Yu, Wei Zhan:
Sampling, Flowers and Communication. 100:1-100:11 - Mark Zhandry:
Quantum Money from Abelian Group Actions. 101:1-101:23 - Mark Zhandry:
The Space-Time Cost of Purifying Quantum Computations. 102:1-102:22 - Mingxun Zhou, Mengshi Zhao, T.-H. Hubert Chan, Elaine Shi:
Advanced Composition Theorems for Differential Obliviousness. 103:1-103:24
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-04 22:24 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
