| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Nima Anari, Nathan Hu, Amin Saberi, Aaron Schild |
Sampling Arborescences in Parallel.  |
ITCS  |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Badih Ghazi, Ravi Kumar 0001, Pasin Manurangsi |
On Distributed Differential Privacy and Counting Distinct Elements. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, Marc Vinyals |
Complexity Measures on the Symmetric Group and Beyond (Extended Abstract). |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Anup Bhattacharya, Arijit Bishnu, Gopinath Mishra, Anannya Upasana |
Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming! |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander Golovnev, Alexander S. Kulikov, R. Ryan Williams |
Circuit Depth Reductions. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Dorit Aharonov, Alex B. Grilo |
Two Combinatorial MA-Complete Problems. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Uri Meir |
Comparison Graphs: A Unified Method for Uniformity Testing. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Pál András Papp, Roger Wattenhofer |
Sequential Defaulting in Financial Networks. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Itai Ashlagi, Mark Braverman, Amin Saberi, Clayton Thomas, Geng Zhao 0002 |
Tiered Random Matching Markets: Rank Is Proportional to Popularity. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Dixon 0002, A. Pavan 0001, N. V. Vinodchandran |
Complete Problems for Multi-Pseudodeterministic Computations. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Ron-Zewi, Ronen Shaltiel, Nithin Varma |
Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists). |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Chi-Ning Chou, Xun Gao |
Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshwar Ram Arunachaleswaran, Sampath Kannan, Aaron Roth 0001, Juba Ziani |
Pipeline Interventions. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ishay Haviv |
The Complexity of Finding Fair Independent Sets in Cycles. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Hedyeh Beyhaghi, Éva Tardos |
Randomness and Fairness in Two-Sided Matching with Limited Interviews. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yiding Feng, Rad Niazadeh |
Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract). |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Zachary Remscrim |
Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | William Kuszmaul, Alek Westover |
The Variable-Processor Cup Game. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Justin Holmgren, Alexander S. Wein |
Counterexamples to the Low-Degree Conjecture. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Curtis Bechtel, Shaddin Dughmi |
Delegated Stochastic Probing. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Vijay V. Vazirani, Mihalis Yannakakis |
Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets. |
ITCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Shant Boodaghians, Rucha Kulkarni, Ruta Mehta |
Smoothed Efficient Algorithms and Reductions for Network Coordination Games. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Shweta Agrawal, Michael Clear, Ophir Frieder, Sanjam Garg, Adam O'Neill, Justin Thaler |
Ad Hoc Multi-Input Functional Encryption. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael P. Kim, Aleksandra Korolova, Guy N. Rothblum, Gal Yona |
Preference-Informed Fairness. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Alessandro Chiesa, Siqi Liu 0005 |
On the Impossibility of Probabilistic Proofs in Relativized Worlds. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam |
Beyond Natural Proofs: Hardness Magnification and Locality. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Lior Gishboliner, Asaf Shapira, Henrique Stagni |
Testing Linear Inequalities of Subgraph Statistics. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch |
Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Domagoj Bradac, Anupam Gupta 0001, Sahil Singla 0001, Goran Zuzic |
Robust Algorithms for the Secretary Problem. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Nathan Lindzey, Ansis Rosmanis |
A Tight Lower Bound For Non-Coherent Index Erasure. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Siqi Liu 0005, Sidhanth Mohanty, Elizabeth Yang |
High-Dimensional Expanders from Expanders. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Tal Malkin |
Limits to Non-Malleability. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Avrim Blum, Thodoris Lykouris |
Advancing Subgroup Fairness via Sleeping Experts. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Christopher Jung 0001, Katrina Ligett, Seth Neel, Aaron Roth 0001, Saeed Sharifi-Malvajerdi, Moshe Shenfeld |
A New Analysis of Differential Privacy's Generalization Guarantees. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Nathaniel Harms |
Universal Communication, Universal Graphs, and Graph Labeling. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Suman K. Bera 0001, Noujan Pashanasangi, C. Seshadhri 0001 |
Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Klim Efremenko, Elad Haramaty, Yael Tauman Kalai |
Interactive Coding with Constant Round and Communication Blowup. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Federico Echenique, Siddharth Prasad |
Incentive Compatible Active Learning. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Nalini Vasudevan |
Cryptography from Information Loss. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | T.-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin, Elaine Shi |
MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Greg Bodwin, Ofer Grossman |
Strategy-Stealing Is Non-Constructive. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Alessandro Chiesa, Peter Manohar, Igor Shinkar |
On Local Testability in the Non-Signaling Setting. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Front Matter, Table of Contents, Preface, Conference Organization. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Gal Sadeh, Edith Cohen, Haim Kaplan |
Sample Complexity Bounds for Influence Maximization. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Raz, Wei Zhan |
The Random-Query Model and the Memory-Bounded Coupon Collector. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Linda Cai, Clayton Thomas, S. Matthew Weinberg |
Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh 0001, Meirav Zehavi |
Parameterization Above a Multiplicative Guarantee. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Blanc, Jane Lange, Li-Yang Tan |
Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, Xiaoming Sun 0001 |
From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein |
Computational Hardness of Certifying Bounds on Constrained PCA Problems. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Mitzenmacher |
Scheduling with Predictions and the Price of Misprediction. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Ronitt Rubinfeld, Arsen Vasilyan |
Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Nima Anari, Vijay V. Vazirani |
Matching Is as Easy as the Decision Problem, in the NC Model. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Ariel Schvartzman, S. Matthew Weinberg, Eitan Zlatin, Albert Zuo |
Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Elazar Goldenberg, Karthik C. S. |
Hardness Amplification of Optimization Problems. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis |
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg |
Optimal Single-Choice Prophet Inequalities from Samples. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Bernhard Haeupler, D. Ellis Hershkowitz, Anson Kahng, Ariel D. Procaccia |
Computation-Aware Data Aggregation. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam Bouland, Bill Fefferman, Umesh V. Vazirani |
Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract). |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Nir Bitansky, Idan Gerichter |
On the Cryptographic Hardness of Local Search. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | András Gilyén, Tongyang Li |
Distributional Property Testing in a Quantum World. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Tali Kaufman, David Mass |
Local-To-Global Agreement Expansion via the Variance Method. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | James Bartusek, Yuval Ishai, Aayush Jain, Fermi Ma, Amit Sahai, Mark Zhandry |
Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Rahul Ilango |
Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Ruben Becker, Yuval Emek, Christoph Lenzen 0001 |
Low Diameter Graph Decompositions by Approximate Distance Computation. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff |
Pseudo-Deterministic Streaming. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Konstantin Makarychev, Yury Makarychev |
Certified Algorithms: Worst-Case Analysis and Beyond. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Kira Goldner, Nicole Immorlica, Brendan Lucier |
Reducing Inefficiency in Carbon Auctions with Imperfect Competition. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian |
Equivalence of Systematic Linear Data Structures and Matrix Rigidity. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas Vidick (eds.) |
11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA. |
ITCS |
2020 |
DBLP BibTeX RDF |
|
| 1 | Nir Bitansky, Nathan Geier |
On Oblivious Amplification of Coin-Tossing Protocols. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Anna Gál, Robert Robere |
Lower Bounds for (Non-Monotone) Comparator Circuits. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrej Bogdanov, Baoxiang Wang 0001 |
Learning and Testing Variable Partitions. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohammad Hassan Ameri, Jeremiah Blocki, Samson Zhou |
Computationally Data-Independent Memory Hard Functions. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Austin Conner, Joseph M. Landsberg, Fulvio Gesmundo, Emanuele Ventura |
Kronecker Powers of Tensors and Strassen's Laser Method. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | William Lochet, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh 0001, Roohani Sharma, Meirav Zehavi |
Fault Tolerant Subgraphs with Applications in Kernelization. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Yael Hitron, Nancy A. Lynch, Cameron Musco, Merav Parter |
Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Stacey Jeffery |
Span Programs and Quantum Space Complexity. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Spyros Angelopoulos 0001, Christoph Dürr, Shendan Jin, Shahin Kamali, Marc P. Renault |
Online Computation with Untrusted Advice. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, John Sylvester 0001 |
Choice and Bias in Random Walks. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Amartya Shankha Biswas, Ronitt Rubinfeld, Anak Yodpinyanee |
Local Access to Huge Random Objects Through Partial Sampling. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Haotian Jiang, Jian Li 0015, Daogao Liu, Sahil Singla 0001 |
Algorithms and Adaptivity Gaps for Stochastic k-TSP. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Nils Bertschinger, Martin Hoefer 0001, Daniel Schmand |
Strategic Payments in Financial Networks. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-Yi Cai, Artem Govorov |
On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Jeremiah Blocki, Seunghoon Lee, Samson Zhou |
Approximating Cumulative Pebbling Cost Is Unique Games Hard. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Orr Paradise |
Smooth and Strong PCPs. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Tomer Grossman, Ilan Komargodski, Moni Naor |
Instance Complexity and Unlabeled Certificates in the Decision Tree Model. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Parikshit Gopalan, Roie Levin, Udi Wieder |
Finding Skewed Subcubes Under a Distribution. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Josh Alman, Virginia Vassilevska Williams |
OV Graphs Are (Probably) Hard Instances. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrea Lincoln, Adam Polak 0001, Virginia Vassilevska Williams |
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Georg Loho, László A. Végh |
Signed Tropical Convexity. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf |
DEEP-FRI: Sampling Outside the Box Improves Soundness. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, Luca Trevisan |
Consensus vs Broadcast, with and Without Noise (Extended Abstract). |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Guillaume Lagarde, Jakob Nordström, Dmitry Sokolov 0001, Joseph Swernofsky |
Trade-Offs Between Size and Degree in Polynomial Calculus. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Benny Applebaum, Zvika Brakerski, Sanjam Garg, Yuval Ishai, Akshayaram Srinivasan |
Separating Two-Round Secure Computation From Oblivious Transfer. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrea Lincoln, Nikhil Vyas 0001 |
Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Arnab Bhattacharyya 0001, L. Sunil Chandran, Suprovat Ghoshal |
Combinatorial Lower Bounds for 3-Query LDCs. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Omri Ben-Eliezer, Eldar Fischer, Amit Levi, Ron D. Rothblum |
Hard Properties with (Very) Short PCPPs and Their Applications. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Fedor Part, Iddo Tzameret |
Resolution with Counting: Dag-Like Lower Bounds and Different Moduli. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Manuel Fernandez, David P. Woodruff, Taisuke Yasuda 0002 |
Graph Spanners in the Message-Passing Model. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license