| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Ingerid Fosli, Yuval Ishai, Victor I. Kolobov, Mary Wootters |
On the Download Rate of Homomorphic Secret Sharing.  |
ITCS  |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Noah Fleming, Toniann Pitassi, Robert Robere |
Extremely Deep Proofs. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuchi Chawla 0001, Meena Jagadeesan |
Individual Fairness in Advertising Auctions Through Inverse Proportionality. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuichi Hirahara, Rahul Santhanam |
Errorless Versus Error-Prone Average-Case Complexity. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman (eds.) |
13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA. |
ITCS |
2022 |
DBLP BibTeX RDF |
|
| 1 | Omar Fawzi, Alexander Müller-Hermes, Ala Shayeghi |
A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepehr Assadi, Vihan Shah |
An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Shyan Akmal, Lijie Chen 0001, Ce Jin 0001, Malvika Raj, Ryan Williams 0001 |
Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Gregory Rosenthal, Henry Yuen |
Interactive Proofs for Synthesizing Quantum States and Unitaries. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Yevgeniy Dodis, Harish Karthikeyan, Daniel Wichs |
Small-Box Cryptography. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Bruno Pasqualotto Cavalar, Zhenjian Lu |
Algorithms and Lower Bounds for Comparator Circuits from Shrinkage. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Huck Bennett, Chris Peikert, Yi Tang |
Improved Hardness of BDD and SVP Under Gap-(S)ETH. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Keren Censor-Hillel, Yannic Maus, Shahar Romem Peled, Tigran Tonoyan |
Distributed Vertex Cover Reconfiguration. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Amey Bhangale, Aleksa Stankovic |
Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Uma Girish, Ran Raz |
Eliminating Intermediate Measurements Using Pseudorandom Generators. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Xue Chen, Kuan Cheng, Xin Li 0006, Minghui Ouyang |
Improved Decoding of Expander Codes. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Luca Ganassali, Laurent Massoulié, Marc Lelarge |
Correlation Detection in Trees for Planted Graph Alignment. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Front Matter, Table of Contents, Preface, Conference Organization. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Shuichi Hirahara, Neekon Vafa |
Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Vipul Goyal, Justin Raizes, Pratik Soni |
Time-Traveling Simulators Using Blockchains and Their Applications. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Noah Shutty, Mary Wootters |
Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Balaram Behera, Edin Husic, Shweta Jain 0003, Tim Roughgarden, C. Seshadhri 0001 |
FPT Algorithms for Finding Near-Cliques in c-Closed Graphs. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael A. Bender, Martin Farach-Colton, William Kuszmaul |
What Does Dynamic Optimality Mean in External Memory? |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Sam Olesker-Taylor, Luca Zanetti |
Geometric Bounds on the Fastest Mixing Markov Chain. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Kunal Marwaha |
Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepehr Assadi, Chen Wang 0027 |
Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Greg Bodwin, Michael Dinitz, Yasamin Nazari |
Vertex Fault-Tolerant Emulators. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Vijay Bhattiprolu, Euiwoong Lee, Madhur Tulsiani |
Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Ezra, Ron D. Rothblum |
Small Circuits Imply Efficient Arthur-Merlin Protocols. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Yang P. Liu, Ashwin Sah, Mehtaab Sawhney |
A Gaussian Fixed Point Random Walk. |
ITCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Kunal Mittal, Ran Raz |
Block Rigidity: Strong Multiplayer Parallel Repetition Implies Super-Linear Lower Bounds for Turing Machines. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Komargodski, Elaine Shi |
Differentially Oblivious Turing Machines. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm |
The Strongish Planted Clique Hypothesis and Its Consequences. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Shyam Narayanan, Michael Ren |
Circular Trace Reconstruction. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Gregory Rosenthal |
Bounds on the QAC^0 Complexity of Approximating Parity. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuichi Yoshida, Samson Zhou |
Sensitivity Analysis of the Maximum Matching Problem. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, Amir Yehudayoff |
Interactive Proofs for Verifying Machine Learning. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De, Shivam Nadimpalli, Rocco A. Servedio |
Quantitative Correlation Inequalities via Semigroup Interpolation. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Kimberly Ding, S. Matthew Weinberg |
Approximately Strategyproof Tournament Rules in the Probabilistic Setting. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Uma Girish, Ran Raz, Avishay Tal |
Quantum Versus Randomized Communication Complexity, with Efficient Players. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Kush Bhatia, Peter L. Bartlett, Anca D. Dragan, Jacob Steinhardt |
Agnostic Learning with Unknown Utilities. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua A. Grochow, Youming Qiao |
On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena |
Computation over the Noisy Broadcast Channel with Malicious Parties. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz |
Distributed Quantum Proofs for Replicated Data. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Anthony Leverrier, Vivien Londe, Gilles Zémor |
Towards Local Testability for Quantum Coding. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Grant Schoenebeck, Fang-Yi Yu |
Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Srinivasan Arunachalam, Supartha Podder |
Communication Memento: Memoryless Communication Complexity. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Geoffroy Couteau, Pooya Farshim, Mohammad Mahmoody |
Black-Box Uselessness: Composing Separations in Cryptography. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | William M. Hoza, Edward Pyne, Salil P. Vadhan |
Pseudorandom Generators for Unbounded-Width Permutation Branching Programs. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Filmus, Or Meir, Avishay Tal |
Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Esty Kelman, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra |
Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yang Cai 0001, Grigoris Velegkas |
How to Sell Information Optimally: An Algorithmic Study. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nicole Immorlica, Ian A. Kash, Brendan Lucier |
Buying Data over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Moshe Babaioff, Richard Cole 0001, Jason D. Hartline, Nicole Immorlica, Brendan Lucier |
Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract). |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Front Matter, Table of Contents, Preface, Conference Organization. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin Hoefer 0001, Pasin Manurangsi, Alexandros Psomas 0001 |
Algorithmic Persuasion with Evidence. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Noam Solomon, Shay Solomon |
A Generalized Matching Reconfiguration Problem. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jop Briët, Farrokh Labib |
High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract). |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Benjamin Rossman |
Shrinkage of Decision Lists and DNF Formulas. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma |
Erasure-Resilient Sublinear-Time Graph Algorithms. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Sander Borst, Daniel Dadush, Neil Olver, Makrand Sinha |
Majorizing Measures for the Optimizer. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Noah Burrell, Grant Schoenebeck |
Relaxing Common Belief for Social Networks. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael B. Cohen, Aaron Sidford, Kevin Tian |
Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, Christos H. Papadimitriou |
Total Functions in the Polynomial Hierarchy. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jay Mardia |
Is the Space Complexity of Planted Clique Recovery the Same as That of Detection? |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | William Kretschmer |
The Quantum Supremacy Tsirelson Inequality. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Lior Eldar |
Robust Quantum Entanglement at (Nearly) Room Temperature. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Emek, Shay Kutten, Yangguang Shi |
Online Paging with a Vanishing Regret. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Dagan, Yuval Filmus, Daniel Kane 0001, Shay Moran |
The Entropy of Lies: Playing Twenty Questions with a Liar. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jeremiah Blocki, Mike Cinkoske |
A New Connection Between Node and Edge Depth Robust Graphs. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen 0001, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha |
Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Joshua Lau, Angus Ritossa |
Algorithms and Hardness for Multidimensional Range Updates and Queries. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, Mary Wootters |
Sharp Threshold Rates for Random Codes. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Vinayak Kumar |
Pseudobinomiality of the Sticky Random Walk. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jiabao Lin |
On the Complexity of #CSP^d. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Weiming Feng 0001, Kun He 0011, Xiaoming Sun 0001, Yitong Yin |
Dynamic Inference in Probabilistic Graphical Models. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Tony Metger, Thomas Vidick |
Self-Testing of a Single Quantum Device Under Computational Assumptions. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Cameron Musco, Christopher Musco, David P. Woodruff |
Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani |
Explicit SoS Lower Bounds from High-Dimensional Expanders. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Rajko Nenadov, Angelika Steger, Pascal Su |
An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ofer Grossman, Justin Holmgren |
Error Correcting Codes for Uncompressed Messages. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Spyros Angelopoulos 0001 |
Online Search with a Hint. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Surbhi Goel, Adam R. Klivans, Pasin Manurangsi, Daniel Reichman 0001 |
Tight Hardness Results for Training Depth-2 ReLU Networks. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | José Correa 0001, Paul Dütting, Felix A. Fischer, Kevin Schewior, Bruno Ziliotto |
Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility (Extended Abstract). |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Moses Charikar, Shivam Garg 0001, Deborah M. Gordon, Kirankumar Shiragur |
A Model for Ant Trail Formation and its Convergence Properties (Extended Abstract). |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nengkun Yu |
Sample Efficient Identity Testing and Independence Testing of Quantum States. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Omri Ben-Eliezer, Eldar Fischer, Amit Levi, Yuichi Yoshida |
Ordered Graph Limits and Their Applications. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Stefan Dziembowski, Grzegorz Fabianski, Sebastian Faust, Siavash Riahi 0002 |
Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Subhash Khot, Dor Minzer |
On Rich 2-to-1 Games. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Russell Impagliazzo, Sam McGuire |
Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?). |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan van den Brand, Binghui Peng, Zhao Song 0002, Omri Weinstein |
Training (Overparametrized) Neural Networks in Near-Linear Time. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Pranjal Dutta, Nitin Saxena 0001, Thomas Thierauf |
A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif |
No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mikito Nanashima |
On Basing Auxiliary-Input Cryptography on NP-Hardness via Nonadaptive Black-Box Reductions. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Abhijit Mudigonda, R. Ryan Williams |
Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | James R. Lee (eds.) |
12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference. |
ITCS |
2021 |
DBLP BibTeX RDF |
|
| 1 | Sara Ahmadian, Allen Liu, Binghui Peng, Morteza Zadimoghaddam |
Distributed Load Balancing: A New Framework and Improved Guarantees. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mrinal Kumar 0001, Ben Lee Volk |
A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Olaf Beyersdorff, Benjamin Böhm 0001 |
Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Sébastien Bubeck, Niv Buchbinder, Christian Coester, Mark Sellke |
Metrical Service Systems with Transformations. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license