default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID14th ITCS 2023
- Yael Tauman Kalai:
14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA. LIPIcs 251, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2023, ISBN 978-3-95977-263-1 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:22
- Amir Abboud, Nathan Wallheimer:
Worst-Case to Expander-Case Reductions. 1:1-1:23 - Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan:
Matroid Partition Property and the Secretary Problem. 2:1-2:9 - Eric Allender, Shuichi Hirahara, Harsha Tirumala:
Kolmogorov Complexity Characterizes Statistical Zero Knowledge. 3:1-3:19 - Alexandr Andoni, Jaroslaw Blasiok
, Arnold Filtser:
Communication Complexity of Inner Product in Symmetric Normed Spaces. 4:1-4:22 - Anurag Anshu, Tony Metger:
Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations. 5:1-5:8 - Vikraman Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, C. Ramya:
On Identity Testing and Noncommutative Rank Computation over the Free Skew Field. 6:1-6:23 - Sepehr Assadi, Aaron Bernstein, Zachary Langley:
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method. 7:1-7:24 - Idan Attias, Edith Cohen, Moshe Shechner, Uri Stemmer:
A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators. 8:1-8:19 - Moshe Babaioff, Nicole Immorlica, Yingkai Li, Brendan Lucier:
Making Auctions Robust to Aftermarkets. 9:1-9:23 - Mirza Ahad Baig, Suvradip Chakraborty, Stefan Dziembowski, Malgorzata Galazka, Tomasz Lizurej, Krzysztof Pietrzak:
Efficiently Testable Circuits. 10:1-10:23 - Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan:
Strategyproof Scheduling with Predictions. 11:1-11:22 - Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, Zhouzi Li:
Graph Searching with Predictions. 12:1-12:24 - Ulrich Bauer, Abhishek Rathod, Meirav Zehavi:
On Computing Homological Hitting Sets. 13:1-13:21 - Paul Beame, Sajin Koroth:
On Disperser/Lifting Properties of the Index and Inner-Product Functions. 14:1-14:17 - Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, Madhu Sudan:
Is This Correct? Let's Check! 15:1-15:11 - Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, Kamesh Munagala:
Online Learning and Bandits with Queried Hints. 16:1-16:24 - Nir Bitansky, Tomer Solomon:
Bootstrapping Homomorphic Encryption via Functional Encryption. 17:1-17:23 - Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan:
Certification with an NP Oracle. 18:1-18:22 - Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans:
Matrix Multiplication via Matrix Groups. 19:1-19:16 - Greg Bodwin, Michael Dinitz, Yasamin Nazari:
Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free. 20:1-20:22 - Greg Bodwin, Forest Zhang:
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas. 21:1-21:21 - Romain Bourneuf, Lukás Folwarczný, Pavel Hubácek, Alon Rosen, Nikolaj I. Schwartzbach:
PPP-Completeness and Extremal Combinatorics. 22:1-22:20 - Elette Boyle, Yuval Ishai, Pierre Meyer, Robert Robere, Gal Yehuda:
On Low-End Obfuscation and Learning. 23:1-23:28 - Zvika Brakerski, Ran Canetti, Luowen Qian:
On the Computational Hardness Needed for Quantum Cryptography. 24:1-24:21 - Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer:
Improved Monotonicity Testers via Hypercube Embeddings. 25:1-25:24 - Mark Braverman, Dor Minzer:
Rounding via Low Dimensional Embeddings. 26:1-26:30 - Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, Marc Roth:
Counting Subgraphs in Somewhere Dense Graphs. 27:1-27:14 - Anne Broadbent, Eric Culf:
Rigidity for Monogamy-Of-Entanglement Games. 28:1-28:29 - Harry Buhrman, Noah Linden, Laura Mancinska, Ashley Montanaro, Maris Ozols:
Quantum Majority Vote. 29:1-29:1 - Sam Buss, Noah Fleming, Russell Impagliazzo:
TFNP Characterizations of Proof Systems and Monotone Circuits. 30:1-30:40 - Diptarka Chakraborty, Debarati Das, Robert Krauthgamer:
Clustering Permutations: New Techniques with Streaming Applications. 31:1-31:24 - Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny:
Certificate Games. 32:1-32:24 - Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif:
Lifting to Parity Decision Trees via Stifling. 33:1-33:20 - Lijie Chen:
New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method. 34:1-34:15 - Lijie Chen, Ryan Williams, Tianqi Yang:
Black-Box Constructive Proofs Are Unavoidable. 35:1-35:24 - Albert Cheu, Chao Yan:
Necessary Conditions in Multi-Server Differential Privacy. 36:1-36:21 - Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani:
Quantum Algorithms and the Power of Forgetting. 37:1-37:22 - Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg, Zihan Tan:
A New Conjecture on Hardness of 2-CSP's with Implications to Hardness of Densest k-Subgraph and Other Problems. 38:1-38:23 - Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, Uri Stemmer:
Generalized Private Selection and Testing with High Confidence. 39:1-39:23 - Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones:
Exact Completeness of LP Hierarchies for Linear Codes. 40:1-40:18 - Zhun Deng, Cynthia Dwork, Linjun Zhang:
HappyMap : A Generalized Multicalibration Method. 41:1-41:23 - Papri Dey, Ravi Kannan, Nick Ryder, Nikhil Srivastava:
Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization. 42:1-42:18 - Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii:
Constant-Depth Sorting Networks. 43:1-43:19 - Shahar Dobzinski, Ariel Shaulker:
Rigidity in Mechanism Design and Its Applications. 44:1-44:21 - Fabien Dufoulon, Yuval Emek, Ran Gelles:
Beeping Shortest Paths via Hypergraph Bipartite Decomposition. 45:1-45:24 - Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena:
Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds. 46:1-46:20 - Antoine El-Hayek, Monika Henzinger, Stefan Schmid:
Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks. 47:1-47:21 - Alessandro Epasto, Jieming Mao, Andres Muñoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, Peilin Zhong:
Differentially Private Continual Releases of Streaming Frequency Moment Estimations. 48:1-48:24 - Hamza Fawzi, Omar Fawzi, Samuel O. Scalet:
A Subpolynomial-Time Algorithm for the Free Energy of One-Dimensional Quantum Systems in the Thermodynamic Limit. 49:1-49:6 - Arnold Filtser, Michael Kapralov, Mikhail Makarov:
Expander Decomposition in Dynamic Streams. 50:1-50:13 - Omrit Filtser, Mayank Goswami, Joseph S. B. Mitchell, Valentin Polishchuk:
On Flipping the Fréchet Distance. 51:1-51:22 - Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, Aleksandrs Slivkins:
Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. 52:1-52:1 - Sevag Gharibian, Dorian Rudolph:
Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover Interactive Proofs into Unentanglement. 53:1-53:23 - Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thomas Steinke:
Algorithms with More Granular Differential Privacy Guarantees. 54:1-54:24 - Badih Ghazi, Ravi Kumar, Jelani Nelson, Pasin Manurangsi:
Private Counting of Distinct and k-Occurring Items in Time Windows. 55:1-55:24 - Uma Girish, Ran Raz, Wei Zhan:
Is Untrusted Randomness Helpful? 56:1-56:18 - Paul Goldberg, Jiawei Li:
Consensus Division in an Arbitrary Ratio. 57:1-57:18 - Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha:
An Algorithmic Bridge Between Hamming and Levenshtein Distances. 58:1-58:23 - Oded Goldreich, Guy N. Rothblum, Tal Skverer:
On Interactive Proofs of Proximity with Proof-Oblivious Queries. 59:1-59:16 - Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, Udi Wieder:
Loss Minimization Through the Lens Of Outcome Indistinguishability. 60:1-60:20 - Roy Gotlib, Tali Kaufman:
List Agreement Expansion from Coboundary Expansion. 61:1-61:23 - Vipul Goyal, Chen-Da Liu-Zhang, Justin Raizes, João Ribeiro:
Asynchronous Multi-Party Quantum Computation. 62:1-62:22 - Fabrizio Grandoni, Claire Mathieu, Hang Zhou:
Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm. 63:1-63:13 - Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang:
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom. 64:1-64:20 - Varun Gupta, Ravishankar Krishnaswamy, Sai Sandeep, Janani Sundaresan:
Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments. 65:1-65:17 - Iftach Haitner, Noam Mazor, Jad Silbak:
Incompressiblity and Next-Block Pseudoentropy. 66:1-66:18 - Prahladh Harsha, Daniel Mitropolsky, Alon Rosen:
Downward Self-Reducibility in TFNP. 67:1-67:17 - William He, Benjamin Rossman:
Symmetric Formulas for Products of Permutations. 68:1-68:23 - Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson:
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. 69:1-69:22 - Shuichi Hirahara, Mikito Nanashima:
Learning Versus Pseudorandom Generators in Constant Parallel Time. 70:1-70:18 - Yael Hitron, Merav Parter, Eylon Yogev:
Secure Distributed Network Optimization Against Eavesdroppers. 71:1-71:20 - Lunjia Hu, Charlotte Peale:
Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes. 72:1-72:30 - Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang:
Recovery from Non-Decomposable Distance Oracles. 73:1-73:22 - Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh:
Karchmer-Wigderson Games for Hazard-Free Computation. 74:1-74:25 - Yaonan Jin, Pinyan Lu, Tao Xiao:
Learning Reserve Prices in Second-Price Auctions. 75:1-75:24 - Yujia Jin, Vidya Muthukumar, Aaron Sidford:
The Complexity of Infinite-Horizon General-Sum Stochastic Games. 76:1-76:20 - Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi:
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses. 77:1-77:26 - Tali Kaufman, Ran J. Tessler:
Garland's Technique for Posets and High Dimensional Grassmannian Expanders. 78:1-78:22 - Michael P. Kim, Juan C. Perdomo:
Making Decisions Under Outcome Performativity. 79:1-79:15 - Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Huacheng Yu:
Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly. 80:1-80:15 - Yuqing Kong, Grant Schoenebeck:
False Consensus, Information Theory, and Prediction Markets. 81:1-81:23 - Qipeng Liu:
Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More. 82:1-82:18 - Yang P. Liu:
Vertex Sparsification for Edge Connectivity in Polynomial Time. 83:1-83:15 - Shachar Lovett, Jiapeng Zhang:
Fractional Certificates for Bounded Functions. 84:1-84:13 - Pasin Manurangsi:
Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique. 85:1-85:18 - Uri Meir, Rotem Oshman, Ofer Shayevitz, Yuval Volkov:
Resilience of 3-Majority Dynamics to Non-Uniform Schedulers. 86:1-86:19 - Tomoyuki Morimae, Takashi Yamakawa:
Proofs of Quantumness from Trapdoor Permutations. 87:1-87:14 - Amol Pasarkar, Christos H. Papadimitriou, Mihalis Yannakakis:
Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP. 88:1-88:20 - Toniann Pitassi, Morgan Shirley, Adi Shraibman:
The Strength of Equality Oracles in Communication. 89:1-89:19 - Alexander Poremba:
Quantum Proofs of Deletion for Learning with Errors. 90:1-90:14 - Mingda Qiao, Gregory Valiant:
Online Pen Testing. 91:1-91:26 - Guy N. Rothblum, Gal Yona:
Decision-Making Under Miscalibration. 92:1-92:20 - Aviad Rubinstein, Junyao Zhao:
Beyond Worst-Case Budget-Feasible Mechanism Design. 93:1-93:22 - Cynthia Rush, Fiona Skerman, Alexander S. Wein, Dana Yang:
Is It Easier to Count Communities Than Find Them? 94:1-94:23 - Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg:
An Improved Lower Bound for Matroid Intersection Prophet Inequalities. 95:1-95:20 - Adrian She, Henry Yuen:
Unitary Property Testing Lower Bounds by Polynomials. 96:1-96:17 - Elaine Shi, Hao Chung, Ke Wu:
What Can Cryptography Do for Decentralized Mechanism Design? 97:1-97:22 - Prayaag Venkat:
Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices. 98:1-98:12 - Nikhil Vyas, Ryan Williams:
On Oracles and Algorithmic Methods for Proving Lower Bounds. 99:1-99:26 - Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, Ulrich Schmid:
The Time Complexity of Consensus Under Oblivious Message Adversaries. 100:1-100:28 - Emre Yolcu, Marijn J. H. Heule:
Exponential Separations Using Guarded Extension Variables. 101:1-101:22
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-02-15 00: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:
