ITCS - RankMe – RankMe

88 papers

Year	Title / Authors
2020	11th Innovations in Theoretical Computer Science Conference, ITCS 2020, Seattle, Washington, USA, January 12-14, 2020 Thomas Vidick
2020	A New Analysis of Differential Privacy's Generalization Guarantees. Christopher Jung, Katrina Ligett, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, Moshe Shenfeld
2020	A Tight Lower Bound For Non-Coherent Index Erasure. Nathan Lindzey, Ansis Rosmanis
2020	Ad Hoc Multi-Input Functional Encryption. Shweta Agrawal, Michael Clear, Ophir Frieder, Sanjam Garg, Adam O'Neill, Justin Thaler
2020	Advancing Subgroup Fairness via Sleeping Experts. Avrim Blum, Thodoris Lykouris
2020	Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption. James Bartusek, Yuval Ishai, Aayush Jain, Fermi Ma, Amit Sahai, Mark Zhandry
2020	Algorithms and Adaptivity Gaps for Stochastic k-TSP. Haotian Jiang, Jian Li, Daogao Liu, Sahil Singla
2020	Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs. Andrea Lincoln, Nikhil Vyas
2020	Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]. Rahul Ilango
2020	Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence. Ariel Schvartzman, S. Matthew Weinberg, Eitan Zlatin, Albert Zuo
2020	Approximating Cumulative Pebbling Cost Is Unique Games Hard. Jeremiah Blocki, Seunghoon Lee, Samson Zhou
2020	Beyond Natural Proofs: Hardness Magnification and Locality. Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2020	Certified Algorithms: Worst-Case Analysis and Beyond. Konstantin Makarychev, Yury Makarychev
2020	Choice and Bias in Random Walks. Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, John Sylvester
2020	Combinatorial Lower Bounds for 3-Query LDCs. Arnab Bhattacharyya, L. Sunil Chandran, Suprovat Ghoshal
2020	Computation-Aware Data Aggregation. Bernhard Haeupler, D. Ellis Hershkowitz, Anson Kahng, Ariel D. Procaccia
2020	Computational Hardness of Certifying Bounds on Constrained PCA Problems. Afonso S. Bandeira, Dmitriy Kunisky, Alexander S. Wein
2020	Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract). Adam Bouland, Bill Fefferman, Umesh V. Vazirani
2020	Computationally Data-Independent Memory Hard Functions. Mohammad Hassan Ameri, Jeremiah Blocki, Samson Zhou
2020	Consensus vs Broadcast, with and Without Noise (Extended Abstract). Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca, Luca Trevisan
2020	Convertible Codes: New Class of Codes for Efficient Conversion of Coded Data in Distributed Storage. Francisco Maturana, K. V. Rashmi
2020	Cryptography from Information Loss. Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, Prashant Nalini Vasudevan
2020	DEEP-FRI: Sampling Outside the Box Improves Soundness. Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf
2020	Distribution-Free Testing of Linear Functions on ℝⁿ. Noah Fleming, Yuichi Yoshida
2020	Distributional Property Testing in a Quantum World. András Gilyén, Tongyang Li
2020	Equivalence of Systematic Linear Data Structures and Matrix Rigidity. Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian
2020	Fault Tolerant Subgraphs with Applications in Kernelization. William Lochet, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Roohani Sharma, Meirav Zehavi
2020	Finding Skewed Subcubes Under a Distribution. Parikshit Gopalan, Roie Levin, Udi Wieder
2020	From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces. Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, Xiaoming Sun
2020	Front Matter, Table of Contents, Preface, Conference Organization.
2020	Generalized List Decoding. Yihan Zhang, Amitalok J. Budkuley, Sidharth Jaggi
2020	Graph Spanners in the Message-Passing Model. Manuel Fernandez, David P. Woodruff, Taisuke Yasuda
2020	Hard Properties with (Very) Short PCPPs and Their Applications. Omri Ben-Eliezer, Eldar Fischer, Amit Levi, Ron D. Rothblum
2020	Hardness Amplification of Optimization Problems. Elazar Goldenberg, Karthik C. S.
2020	High-Dimensional Expanders from Expanders. Siqi Liu, Sidhanth Mohanty, Elizabeth Yang
2020	Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard. Linda Cai, Clayton Thomas, S. Matthew Weinberg
2020	Incentive Compatible Active Learning. Federico Echenique, Siddharth Prasad
2020	Instance Complexity and Unlabeled Certificates in the Decision Tree Model. Tomer Grossman, Ilan Komargodski, Moni Naor
2020	Interactive Coding with Constant Round and Communication Blowup. Klim Efremenko, Elad Haramaty, Yael Tauman Kalai
2020	Kronecker Powers of Tensors and Strassen's Laser Method. Austin Conner, Joseph M. Landsberg, Fulvio Gesmundo, Emanuele Ventura
2020	Learning and Testing Variable Partitions. Andrej Bogdanov, Baoxiang Wang
2020	Limits to Non-Malleability. Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, Tal Malkin
2020	Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six. Suman K. Bera, Noujan Pashanasangi, C. Seshadhri
2020	Local Access to Huge Random Objects Through Partial Sampling. Amartya Shankha Biswas, Ronitt Rubinfeld, Anak Yodpinyanee
2020	Local-To-Global Agreement Expansion via the Variance Method. Tali Kaufman, David Mass
2020	Low Diameter Graph Decompositions by Approximate Distance Computation. Ruben Becker, Yuval Emek, Christoph Lenzen
2020	Lower Bounds for (Non-Monotone) Comparator Circuits. Anna Gál, Robert Robere
2020	MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture. T.-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin, Elaine Shi
2020	Matching Is as Easy as the Decision Problem, in the NC Model. Nima Anari, Vijay V. Vazirani
2020	Monochromatic Triangles, Intermediate Matrix Products, and Convolutions. Andrea Lincoln, Adam Polak, Virginia Vassilevska Williams
2020	Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples. Ronitt Rubinfeld, Arsen Vasilyan
2020	New Query Lower Bounds for Submodular Function Minimization. Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, S. Matthew Weinberg
2020	OV Graphs Are (Probably) Hard Instances. Josh Alman, Virginia Vassilevska Williams
2020	On Local Testability in the Non-Signaling Setting. Alessandro Chiesa, Peter Manohar, Igor Shinkar
2020	On Oblivious Amplification of Coin-Tossing Protocols. Nir Bitansky, Nathan Geier
2020	On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H. Jin-Yi Cai, Artem Govorov
2020	On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be? Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, Tal Malkin
2020	On the Cryptographic Hardness of Local Search. Nir Bitansky, Idan Gerichter
2020	On the Impossibility of Probabilistic Proofs in Relativized Worlds. Alessandro Chiesa, Siqi Liu
2020	Online Computation with Untrusted Advice. Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, Marc P. Renault
2020	Optimal Single-Choice Prophet Inequalities from Samples. Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg
2020	Parameterization Above a Multiplicative Guarantee. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Meirav Zehavi
2020	Preference-Informed Fairness. Michael P. Kim, Aleksandra Korolova, Guy N. Rothblum, Gal Yona
2020	Pseudo-Deterministic Streaming. Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff
2020	Pseudorandomness and the Minimum Circuit Size Problem. Rahul Santhanam
2020	Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks. Yael Hitron, Nancy A. Lynch, Cameron Musco, Merav Parter
2020	Reducing Inefficiency in Carbon Auctions with Imperfect Competition. Kira Goldner, Nicole Immorlica, Brendan Lucier
2020	Resolution with Counting: Dag-Like Lower Bounds and Different Moduli. Fedor Part, Iddo Tzameret
2020	Robust Algorithms for the Secretary Problem. Domagoj Bradac, Anupam Gupta, Sahil Singla, Goran Zuzic
2020	Sample Complexity Bounds for Influence Maximization. Gal Sadeh, Edith Cohen, Haim Kaplan
2020	Scheduling with Predictions and the Price of Misprediction. Michael Mitzenmacher
2020	Separating Two-Round Secure Computation From Oblivious Transfer. Benny Applebaum, Zvika Brakerski, Sanjam Garg, Yuval Ishai, Akshayaram Srinivasan
2020	Signed Tropical Convexity. Georg Loho, László A. Végh
2020	Smooth and Strong PCPs. Orr Paradise
2020	Smoothed Efficient Algorithms and Reductions for Network Coordination Games. Shant Boodaghians, Rucha Kulkarni, Ruta Mehta
2020	Span Programs and Quantum Space Complexity. Stacey Jeffery
2020	Strategic Payments in Financial Networks. Nils Bertschinger, Martin Hoefer, Daniel Schmand
2020	Strategy-Stealing Is Non-Constructive. Greg Bodwin, Ofer Grossman
2020	Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria. Kousha Etessami, Christos H. Papadimitriou, Aviad Rubinstein, Mihalis Yannakakis
2020	Testing Linear Inequalities of Subgraph Statistics. Lior Gishboliner, Asaf Shapira, Henrique Stagni
2020	Testing Properties of Multiple Distributions with Few Samples. Maryam Aliakbarpour, Sandeep Silwal
2020	The Computational Cost of Asynchronous Neural Communication. Yael Hitron, Merav Parter, Gur Perri
2020	The Random-Query Model and the Memory-Bounded Coupon Collector. Ran Raz, Wei Zhan
2020	Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations. Guy Blanc, Jane Lange, Li-Yang Tan
2020	Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard. Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch
2020	Trade-Offs Between Size and Degree in Polynomial Calculus. Guillaume Lagarde, Jakob Nordström, Dmitry Sokolov, Joseph Swernofsky
2020	Unexpected Power of Random Strings. Shuichi Hirahara
2020	Universal Communication, Universal Graphs, and Graph Labeling. Nathaniel Harms