| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Francisco Maturana, K. V. Rashmi |
Convertible Codes: New Class of Codes for Efficient Conversion of Coded Data in Distributed Storage.  |
ITCS  |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, S. Matthew Weinberg |
New Query Lower Bounds for Submodular Function Minimization. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Rahul Santhanam |
Pseudorandomness and the Minimum Circuit Size Problem. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, Tal Malkin |
On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be? |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Yihan Zhang 0001, Amitalok J. Budkuley, Sidharth Jaggi |
Generalized List Decoding. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Yael Hitron, Merav Parter, Gur Perri |
The Computational Cost of Asynchronous Neural Communication. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Maryam Aliakbarpour, Sandeep Silwal |
Testing Properties of Multiple Distributions with Few Samples. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Noah Fleming, Yuichi Yoshida |
Distribution-Free Testing of Linear Functions on ℝⁿ. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuichi Hirahara |
Unexpected Power of Random Strings. |
ITCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Prahladh Harsha, Tali Kaufman, Noga Ron-Zewi |
From Local to Robust Testing via Agreement Testing. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Filmus, Ryan O'Donnell, Xinyu Wu |
A Log-Sobolev Inequality for the Multislice, with Applications. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Preetum Nakkiran, Madhu Sudan 0001 |
Algorithmic Polarization for Hidden Markov Models. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush, Nutan Limaye, Srikanth Srinivasan 0001 |
A #SAT Algorithm for Small Constant-Depth Circuits with PTF Gates. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Chi-Ning Chou, Kai-Min Chung, Chi-Jen Lu |
On the Algorithmic Power of Spiking Neural Networks. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff |
On the Communication Complexity of Key-Agreement Protocols. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Igor Carboni Oliveira, Rahul Santhanam, Roei Tell |
Expander-Based Cryptography Meets Natural Proofs. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Wei Chen 0013, Shang-Hua Teng, Hanrui Zhang |
Capturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivity. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Oded Goldreich 0001, Tom Gur |
Every Set in P Is Strongly Testable Under a Suitable Encoding. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Schild |
A Schur Complement Cheeger Inequality. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De, Philip M. Long, Rocco A. Servedio |
Density Estimation for Shift-Invariant Multidimensional Distributions. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Nick Arnosti, S. Matthew Weinberg |
Bitcoin: A Natural Oligopoly. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Sumegha Garg, Jon Schneider |
The Space Complexity of Mirror Games. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, Avi Wigderson |
Spanoids - An Abstraction of Spanning Structures, and a Barrier for LCCs. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi 0001, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, William S. Zwicker |
Almost Envy-Free Allocations with Connected Bundles. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Pravesh K. Kothari, David Steurer |
Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | André Chailloux |
A Note on the Quantum Query Complexity of Permutation Symmetric Functions. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Krzysztof Pietrzak |
Proofs of Catalytic Space. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Potechin |
Sum of Squares Lower Bounds from Symmetry and a Good Story. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Krzysztof Pietrzak |
Simple Verifiable Delay Functions. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Timothy M. Chan, Sariel Har-Peled, Mitchell Jones |
On Locality-Sensitive Orderings and Their Applications. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Levi, Erik Waingarten |
Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | |
Front Matter, Table of Contents, Preface, Conference Organization. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani |
"Quantum Supremacy" and the Complexity of Random Circuit Sampling. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Deeparnab Chakrabarty, C. Seshadhri 0001 |
Adaptive Boolean Monotonicity Testing in Total Influence Time. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Elette Boyle, Rio LaVigne, Vinod Vaikuntanathan |
Adversarially Robust Property-Preserving Hash Functions. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Constantinos Daskalakis, Ioannis Panageas |
Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Cynthia Dwork, Christina Ilvento |
Fairness Under Composition. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Shipra Agrawal 0001, Mohammad Shadravan, Cliff Stein 0001 |
Submodular Secretary Problem with Shortlists. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, Sankeerth Rao |
Torus Polynomials: An Algebraic Approach to ACC Lower Bounds. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Dorit Aharonov, Leo Zhou |
Hamiltonian Sparsification and Gap-Simulation. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ce Jin 0001 |
Simulating Random Walks on Graphs in the Streaming Model. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ravi Kumar 0001, Manish Purohit, Aaron Schild, Zoya Svitkina, Erik Vee |
Semi-Online Bipartite Matching. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Benny Applebaum, Prashant Nalini Vasudevan |
Placing Conditional Disclosure of Secrets in the Communication Complexity Universe. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel M. Kane, Richard Ryan Williams |
The Orthogonal Vectors Conjecture for Branching Programs and Formulas. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Christos H. Papadimitriou, Santosh S. Vempala |
Random Projection in the Brain and Computation with Assemblies of Neurons. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma |
Erasures vs. Errors in Local Decoding and Property Testing. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, Huaxiong Wang |
Secret Sharing with Binary Shares. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Yan Jin, Elchanan Mossel, Govind Ramnarayan |
Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepehr Assadi, Michael Kapralov, Sanjeev Khanna |
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Klaus Jansen, Kim-Manuel Klein, Marten Maack, Malin Rau |
Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Markus Bläser, Gorav Jindal |
On the Complexity of Symmetric Polynomials. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Adi Rosén, Florent Urrutia |
A New Approach to Multi-Party Peer-to-Peer Communication Complexity. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Anna Gál, Avishay Tal, Adrian Trejo Nuñez |
Cubic Formula Size Lower Bounds Based on Compositions with Majority. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Zachary Chase 0001, Siddharth Prasad |
Learning Time Dependent Choice. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jingcheng Liu 0001, Alistair Sinclair, Piyush Srivastava 0001 |
Fisher Zeros and Correlation Decay in the Ising Model. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Eden Saig |
The Complexity of User Retention. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Dylan M. McKay, Richard Ryan Williams |
Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Ruosong Wang |
Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Omri Ben-Eliezer |
Testing Local Properties of Arrays. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Alessandro Chiesa, Peter Manohar, Igor Shinkar |
Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandr Andoni, Robert Krauthgamer, Yosef Pogrow |
On Solving Linear Systems in Sublinear Time. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Mika Göös, Pritish Kamath, Robert Robere, Dmitry Sokolov 0001 |
Adventures in Monotone Complexity and TFNP. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, Anand Natarajan |
Algorithms, Bounds, and Strategies for Entangled XOR Games. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Klaus Jansen, Lars Rohwedder |
On Integer Programming and Convolution. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich 0001, Dana Ron |
The Subgraph Testing Model. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Linus Hamilton, Ankur Moitra |
The Paulsen Problem Made Simple. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, Avishay Tal |
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Thibaut Horel, Sunoo Park, Silas Richelson, Vinod Vaikuntanathan |
How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Shaddin Dughmi, David Kempe 0001, Ruixin Qiang |
Alea Iacta Est: Auctions, Persuasion, Interim Rules, and Dice. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Pravesh K. Kothari, Ryan O'Donnell, Tselil Schramm |
SOS Lower Bounds with Hard Constraints: Think Global, Act Local. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Troy Lee, Maharshi Ray, Miklos Santha |
Strategies for Quantum Races. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Kim Thang Nguyen |
Game Efficiency Through Linear Programming Duality. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Merav Parter, Ronitt Rubinfeld, Ali Vakilian, Anak Yodpinyanee |
Local Computation Algorithms for Spanners. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Per Austrin, Petteri Kaski, Kaie Kubjas |
Tensor Network Complexity of Multilinear Maps. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Karthik C. S., Pasin Manurangsi |
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Nati Linial, Toniann Pitassi, Adi Shraibman |
On the Communication Complexity of High-Dimensional Permutations. |
ITCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Anat Ganor, Gillat Kol, Ran Raz |
A Candidate for a Strong Separation of Information and Communication. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuqing Kong, Grant Schoenebeck |
Equilibrium Selection in Information Elicitation without Verification via Information Monotonicity. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Lokshtanov, Pranabendu Misra, Fahad Panolan, Saket Saurabh 0001, Meirav Zehavi |
Quasipolynomial Representation of Transversal Matroids with Applications in Parameterized Complexity. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Bürgisser, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter 0005, Avi Wigderson |
Alternating Minimization, Scaling Algorithms, and the Null-Cone Problem from Invariant Theory. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, Makrand Sinha |
Edge Estimation with Independent Set Oracles. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Srikanth Srinivasan 0001, Madhu Sudan 0001 |
Local Decoding and Testing of Polynomials over Grids. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Avrim Blum (eds.) |
10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA |
ITCS |
2018 |
DBLP BibTeX RDF |
|
| 1 | Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan |
Minimum Circuit Size, Graph Isomorphism, and Related Problems. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson |
Barriers for Rank Methods in Arithmetic Complexity. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich 0001, Guy N. Rothblum |
Simple Doubly-Efficient Interactive Proof Systems for Locally-Characterizable Sets. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Itay Berman, Ron D. Rothblum, Vinod Vaikuntanathan |
Zero-Knowledge Proofs of Proximity. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Yishay Mansour, Aleksandrs Slivkins, Zhiwei Steven Wu |
Competing Bandits: Learning Under Competition. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Abboud, Aviad Rubinstein |
Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Alessandro Chiesa, Tom Gur |
Proofs of Proximity for Distribution Testing. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul W. Goldberg, Christos H. Papadimitriou |
Towards a Unified Complexity Theory of Total Functions. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin Groß 0001, Anupam Gupta 0001, Amit Kumar 0001, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt 0001, José Verschae |
A Local-Search Algorithm for Steiner Forest. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuqing Kong, Grant Schoenebeck |
Optimizing Bayesian Information Revelation Strategy in Prediction Markets: the Alice Bob Alice Case. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Josh Alman, Virginia Vassilevska Williams |
Further Limitations of the Known Approaches for Matrix Multiplication. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Georgios Piliouras, Leonard J. Schulman |
Learning Dynamics and the Co-Evolution of Competing Sexual Species. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde |
Size, Cost and Capacity: A Semantic Technique for Hard Random QBFs. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Rafael M. Frongillo, Bo Waggoner |
An Axiomatic Study of Scoring Rule Markets. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Dana Moshkovitz, Michal Moshkovitz |
Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Ben-Or, Lior Eldar |
A Quasi-Random Approach to Matrix Spectral Analysis. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Jacob Steinhardt, Moses Charikar, Gregory Valiant |
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. |
ITCS |
2018 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license