| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Mingxun Zhou, Mengshi Zhao, T.-H. Hubert Chan, Elaine Shi |
Advanced Composition Theorems for Differential Obliviousness.  |
ITCS  |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou |
Quantum Pseudoentanglement. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova |
Property Testing with Online Adversaries. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Ohad Klein, Joseph Slote, Alexander Volberg, Haonan Zhang |
Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Zongchen Chen, Elchanan Mossel |
Influence Maximization in Ising Models. |
ITCS |
2024 |
DBLP DOI BibTeX RDF |
|
| 1 | Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha |
An Algorithmic Bridge Between Hamming and Levenshtein Distances. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson |
A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Adrian She, Henry Yuen |
Unitary Property Testing Lower Bounds by Polynomials. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Antoine El-Hayek, Monika Henzinger, Stefan Schmid 0001 |
Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Greg Bodwin, Michael Dinitz, Yasamin Nazari |
Epic Fail: Emulators Can Tolerate Polynomially Many Edge Faults for Free. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi |
Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Sam Buss, Noah Fleming, Russell Impagliazzo |
TFNP Characterizations of Proof Systems and Monotone Circuits. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Front Matter, Table of Contents, Preface, Conference Organization. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Greg Bodwin, Forest Zhang |
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Prayaag Venkat |
Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Blanc, Caleb Koch, Jane Lange, Carmen Strassle, Li-Yang Tan |
Certification with an NP Oracle. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Shachar Lovett, Jiapeng Zhang |
Fractional Certificates for Bounded Functions. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Yujia Jin, Vidya Muthukumar, Aaron Sidford |
The Complexity of Infinite-Horizon General-Sum Stochastic Games. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, Madhu Sudan 0001 |
Is This Correct? Let's Check! |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Beame, Sajin Koroth |
On Disperser/Lifting Properties of the Index and Inner-Product Functions. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Albert Cheu, Chao Yan |
Necessary Conditions in Multi-Server Differential Privacy. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones |
Exact Completeness of LP Hierarchies for Linear Codes. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Aditya Bhaskara, Sreenivas Gollapudi, Sungjin Im, Kostas Kollias, Kamesh Munagala |
Online Learning and Bandits with Queried Hints. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Tomoyuki Morimae, Takashi Yamakawa |
Proofs of Quantumness from Trapdoor Permutations. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | William He, Benjamin Rossman |
Symmetric Formulas for Products of Permutations. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena |
Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhun Deng, Cynthia Dwork, Linjun Zhang |
HappyMap : A Generalized Multicalibration Method. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander Poremba |
Quantum Proofs of Deletion for Learning with Errors. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Papri Dey, Ravi Kannan, Nick Ryder, Nikhil Srivastava |
Bit Complexity of Jordan Normal Form and Polynomial Spectral Factorization. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir V. Podolskii |
Constant-Depth Sorting Networks. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, Udi Wieder |
Loss Minimization Through the Lens Of Outcome Indistinguishability. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Christian Ikenmeyer, Balagopal Komarath, Nitin Saurabh |
Karchmer-Wigderson Games for Hazard-Free Computation. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Diptarka Chakraborty, Debarati Das 0001, Robert Krauthgamer |
Clustering Permutations: New Techniques with Streaming Applications. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Roy Gotlib, Tali Kaufman |
List Agreement Expansion from Coboundary Expansion. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, Shayan Oveis Gharan |
Matroid Partition Property and the Secretary Problem. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Emre Yolcu, Marijn J. H. Heule |
Exponential Separations Using Guarded Extension Variables. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Mingda Qiao, Gregory Valiant |
Online Pen Testing. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Prahladh Harsha, Daniel Mitropolsky, Alon Rosen |
Downward Self-Reducibility in TFNP. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandr Andoni, Jaroslaw Blasiok, Arnold Filtser |
Communication Complexity of Inner Product in Symmetric Normed Spaces. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Uma Girish, Ran Raz, Wei Zhan |
Is Untrusted Randomness Helpful? |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Moshe Babaioff, Nicole Immorlica, Yingkai Li, Brendan Lucier |
Making Auctions Robust to Aftermarkets. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Shahar Dobzinski, Ariel Shaulker |
Rigidity in Mechanism Design and Its Applications. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Romain Bourneuf, Lukás Folwarczný, Pavel Hubácek, Alon Rosen, Nikolaj I. Schwartzbach |
PPP-Completeness and Extremal Combinatorics. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Ulrich Bauer, Abhishek Rathod, Meirav Zehavi |
On Computing Homological Hitting Sets. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Toniann Pitassi, Morgan Shirley, Adi Shraibman |
The Strength of Equality Oracles in Communication. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Arnold Filtser, Michael Kapralov, Mikhail Makarov |
Expander Decomposition in Dynamic Streams. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid 0001, Ulrich Schmid 0001 |
The Time Complexity of Consensus Under Oblivious Message Adversaries. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Idan Attias, Edith Cohen, Moshe Shechner, Uri Stemmer |
A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Huacheng Yu |
Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Edith Cohen, Xin Lyu 0002, Jelani Nelson, Tamás Sarlós, Uri Stemmer |
Generalized Private Selection and Testing with High Confidence. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Ryan Williams 0001, Tianqi Yang 0001 |
Black-Box Constructive Proofs Are Unavoidable. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Iftach Haitner, Noam Mazor, Jad Silbak |
Incompressiblity and Next-Block Pseudoentropy. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Alessandro Epasto, Jieming Mao, Andres Muñoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, Peilin Zhong |
Differentially Private Continual Releases of Streaming Frequency Moment Estimations. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuqing Kong, Grant Schoenebeck |
False Consensus, Information Theory, and Prediction Markets. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Zvika Brakerski, Ran Canetti, Luowen Qian |
On the Computational Hardness Needed for Quantum Cryptography. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepehr Assadi, Aaron Bernstein, Zachary Langley |
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael P. Kim, Juan C. Perdomo |
Making Decisions Under Outcome Performativity. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Vikraman Arvind, Abhranil Chatterjee 0001, Utsab Ghosal, Partha Mukhopadhyay, C. Ramya |
On Identity Testing and Noncommutative Rank Computation over the Free Skew Field. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Fabrizio Grandoni 0001, Claire Mathieu, Hang Zhou 0001 |
Unsplittable Euclidean Capacitated Vehicle Routing: A (2+ε)-Approximation Algorithm. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Jason Gaitonde, Yingkai Li, Bar Light, Brendan Lucier, Aleksandrs Slivkins |
Budget Pacing in Repeated Auctions: Regret and Efficiency Without Convergence. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Tali Kaufman, Ran J. Tessler |
Garland's Technique for Posets and High Dimensional Grassmannian Expanders. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Yael Tauman Kalai (eds.) |
14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA. |
ITCS |
2023 |
DBLP BibTeX RDF |
|
| 1 | Nir Bitansky, Tomer Solomon |
Bootstrapping Homomorphic Encryption via Functional Encryption. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, Suhail Sherif |
Lifting to Parity Decision Trees via Stifling. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhuangfei Hu, Xinda Li 0001, David P. Woodruff, Hongyang Zhang 0001, Shufan Zhang |
Recovery from Non-Decomposable Distance Oracles. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Vyas 0001, Ryan Williams 0001 |
On Oracles and Algorithmic Methods for Proving Lower Bounds. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Qipeng Liu 0001 |
Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001 |
New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Yael Hitron, Merav Parter, Eylon Yogev |
Secure Distributed Network Optimization Against Eavesdroppers. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Dor Minzer |
Rounding via Low Dimensional Embeddings. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Goldberg 0001, Jiawei Li |
Consensus Division in an Arbitrary Ratio. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich 0001, Guy N. Rothblum, Tal Skverer |
On Interactive Proofs of Proximity with Proof-Oblivious Queries. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Anurag Anshu, Tony Metger |
Concentration Bounds for Quantum States and Limitations on the QAOA from Polynomial Approximations. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Sourav Chakraborty 0001, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny |
Certificate Games. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Yang P. Liu |
Vertex Sparsification for Edge Connectivity in Polynomial Time. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Marco Bressan 0002, Leslie Ann Goldberg, Kitty Meeks, Marc Roth |
Counting Subgraphs in Somewhere Dense Graphs. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Sevag Gharibian, Dorian Rudolph |
Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover Interactive Proofs into Unentanglement. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Badih Ghazi, Ravi Kumar 0001, Jelani Nelson, Pasin Manurangsi |
Private Counting of Distinct and k-Occurring Items in Time Windows. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Uri Meir, Rotem Oshman, Ofer Shayevitz, Yuval Volkov |
Resilience of 3-Majority Dynamics to Non-Uniform Schedulers. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy N. Rothblum, Gal Yona |
Decision-Making Under Miscalibration. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuichi Hirahara, Mikito Nanashima |
Learning Versus Pseudorandom Generators in Constant Parallel Time. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Sabee Grewal, Vishnu Iyer, William Kretschmer, Daniel Liang |
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Raghuvansh R. Saxena, Santhoshini Velusamy, S. Matthew Weinberg |
An Improved Lower Bound for Matroid Intersection Prophet Inequalities. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Lunjia Hu, Charlotte Peale |
Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Aviad Rubinstein, Junyao Zhao 0001 |
Beyond Worst-Case Budget-Feasible Mechanism Design. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer |
Improved Monotonicity Testers via Hypercube Embeddings. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Shuichi Hirahara, Harsha Tirumala |
Kolmogorov Complexity Characterizes Statistical Zero Knowledge. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans |
Matrix Multiplication via Matrix Groups. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Varun Gupta 0004, Ravishankar Krishnaswamy, Sai Sandeep, Janani Sundaresan |
Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Balkanski, Vasilis Gkatzelis, Xizhi Tan |
Strategyproof Scheduling with Predictions. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Elette Boyle, Yuval Ishai, Pierre Meyer, Robert Robere, Gal Yehuda |
On Low-End Obfuscation and Learning. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Yaonan Jin, Pinyan Lu, Tao Xiao |
Learning Reserve Prices in Second-Price Auctions. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Fabien Dufoulon, Yuval Emek, Ran Gelles |
Beeping Shortest Paths via Hypergraph Bipartite Decomposition. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Cynthia Rush, Fiona Skerman, Alexander S. Wein, Dana Yang |
Is It Easier to Count Communities Than Find Them? |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Noah Linden, Laura Mancinska, Ashley Montanaro, Maris Ozols |
Quantum Majority Vote. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Hamza Fawzi, Omar Fawzi, Samuel O. Scalet |
A Subpolynomial-Time Algorithm for the Free Energy of One-Dimensional Quantum Systems in the Thermodynamic Limit. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Badih Ghazi, Ravi Kumar 0001, Pasin Manurangsi, Thomas Steinke 0002 |
Algorithms with More Granular Differential Privacy Guarantees. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Amol Pasarkar, Christos H. Papadimitriou, Mihalis Yannakakis |
Extremal Combinatorics, Iterated Pigeonhole Arguments and Generalizations of PPP. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Abboud, Nathan Wallheimer |
Worst-Case to Expander-Case Reductions. |
ITCS |
2023 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license