ITCS 2020 January 12-14, 2020, Seattle, Washington, USA

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)



Thomas Vidick (Ed.)
ISBN 978-3-95977-134-4, LIPICS Vol. 151 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 62 MB)
Search Publication Server


Authors
  • Agrawal, Shweta
  • Aliakbarpour, Maryam
  • Alman, Josh
  • Ameri, Mohammad Hassan
  • Anari, Nima
  • Angelopoulos, Spyros
  • Applebaum, Benny
  • Ball, Marshall
  • Bandeira, Afonso S.
  • Bartusek, James
  • Becker, Ruben
  • Bei, Xiaohui
  • Ben-Eliezer, Omri
  • Ben-Sasson, Eli
  • Bera, Suman K.
  • Bertschinger, Nils
  • Bhattacharyya, Arnab
  • Biswas, Amartya Shankha
  • Bitansky, Nir
  • Blanc, Guy
  • Blocki, Jeremiah
  • Blum, Avrim
  • Bodwin, Greg
  • Bogdanov, Andrej
  • Boodaghians, Shant
  • Bouland, Adam
  • Boyle, Elette
  • Bradac, Domagoj
  • Brakerski, Zvika
  • Budkuley, Amitalok J.
  • Cai, Jin-Yi
  • Cai, Linda
  • Chan, T-H. Hubert
  • Chandran, L. Sunil
  • Chen, Lijie
  • Chen, Shiteng
  • Chiesa, Alessandro
  • Chung, Kai-Min
  • Clear, Michael
  • Clementi, Andrea
  • Cohen, Edith
  • Conner, Austin
  • Dachman-Soled, Dana
  • Degwekar, Akshay
  • Demaine, Erik D.
  • Deshpande, Apoorvaa
  • Dürr, Christoph
  • Echenique, Federico
  • Efremenko, Klim
  • Emek, Yuval
  • Etessami, Kousha
  • Fefferman, Bill
  • Fernández V, Manuel
  • Fischer, Eldar
  • Fleming, Noah
  • Fomin, Fedor V.
  • Frieder, Ophir
  • Garg, Sanjam
  • Geier, Nathan
  • Georgakopoulos, Agelos
  • Gerichter, Idan
  • Gesmundo, Fulvio
  • Ghoshal, Suprovat
  • Gilyén, András
  • Gishboliner, Lior
  • Goldberg, Lior
  • Goldenberg, Elazar
  • Goldner, Kira
  • Goldwasser, Shafi
  • Golovach, Petr A.
  • Gopalan, Parikshit
  • Govorov, Artem
  • Graur, Andrei
  • Grossman, Ofer
  • Grossman, Tomer
  • Gualà, Luciano
  • Guan, Ji
  • Gupta, Anupam
  • Gál, Anna
  • Haeupler, Bernhard
  • Haramaty, Elad
  • Harms, Nathaniel
  • Haslegrave, John
  • Hendrickson, Dylan H.
  • Hershkowitz, D. Ellis
  • Hirahara, Shuichi
  • Hitron, Yael
  • Hoefer, Martin
  • Holmgren, Justin
  • Ilango, Rahul
  • Immorlica, Nicole
  • Ishai, Yuval
  • Jaggi, Sidharth
  • Jain, Aayush
  • Jeffery, Stacey
  • Jiang, Haotian
  • Jin, Shendan
  • Jung, Christopher
  • Kahng, Anson
  • Kalai, Yael Tauman
  • Kamali, Shahin
  • Kaplan, Haim
  • Karthik C. S.,
  • Kaufman, Tali
  • Kim, Michael P.
  • Komargodski, Ilan
  • Kopparty, Swastik
  • Korolova, Aleksandra
  • Kulkarni, Mukul
  • Kulkarni, Rucha
  • Kunisky, Dmitriy
  • Lagarde, Guillaume
  • Landsberg, Joseph M.
  • Lange, Jane
  • Lee, Seunghoon
  • Lenzen, Christoph
  • Levi, Amit
  • Levin, Roie
  • Li, Jian
  • Li, Tongyang
  • Ligett, Katrina
  • Lin, Wei-Kai
  • Lincoln, Andrea
  • Lindzey, Nathan
  • Liu, Daogao
  • Liu, Siqi
  • Liu, Tianren
  • Lochet, William
  • Loho, Georg
  • Lokshtanov, Daniel
  • Lucier, Brendan
  • Lykouris, Thodoris
  • Lynch, Jayson
  • Lynch, Nancy
  • Ma, Fermi
  • Makarychev, Konstantin
  • Makarychev, Yury
  • Malkin, Tal
  • Manohar, Peter
  • Mass, David
  • Maturana, Francisco
  • Mehta, Ruta
  • Misra, Pranabendu
  • Mitzenmacher, Michael
  • Mohanty, Sidhanth
  • Musco, Cameron
  • Naor, Moni
  • Natale, Emanuele
  • Natarajan Ramamoorthy, Sivaramakrishnan
  • Neel, Seth
  • Nordström, Jakob
  • O'Neill, Adam
  • Oliveira, Igor C.
  • Panolan, Fahad
  • Papadimitriou, Christos
  • Paradise, Orr
  • Part, Fedor
  • Parter, Merav
  • Pashanasangi, Noujan
  • Pasquale, Francesco
  • Perri, Gur
  • Pich, Ján
  • Polak, Adam
  • Pollner, Tristan
  • Prasad, Siddharth
  • Procaccia, Ariel D.
  • Qiao, Youming
  • Rajgopal, Ninad
  • Ramaswamy, Vidhya
  • Rashmi, K. V.
  • Rashtchian, Cyrus
  • Raz, Ran
  • Renault, Marc
  • Robere, Robert
  • Rosen, Alon
  • Rosmanis, Ansis
  • Roth, Aaron
  • Rothblum, Guy N.
  • Rothblum, Ron D.
  • Rubinfeld, Ronitt
  • Rubinstein, Aviad
  • Sadeh, Gal
  • Sahai, Amit
  • Santhanam, Rahul
  • Saraf, Shubhangi
  • Sauerwald, Thomas
  • Saurabh, Saket
  • Schmand, Daniel
  • Schvartzman, Ariel
  • Scornavacca, Giacomo
  • Seshadhri, C.
  • Shapira, Asaf
  • Sharifi-Malvajerdi, Saeed
  • Sharma, Roohani
  • Shenfeld, Moshe
  • Shi, Elaine
  • Shinkar, Igor
  • Silwal, Sandeep
  • Singla, Sahil
  • Sokolov, Dmitry
  • Srinivasan, Akshayaram
  • Stagni, Henrique
  • Sun, Xiaoming
  • Swernofsky, Joseph
  • Sylvester, John
  • Tan, Li-Yang
  • Thaler, Justin
  • Thomas, Clay
  • Trevisan, Luca
  • Tzameret, Iddo
  • Vaikuntanathan, Vinod
  • Vasilyan, Arsen
  • Vassilevska Williams, Virginia
  • Vasudevan, Prashant Nalini
  • Vazirani, Umesh
  • Vazirani, Vijay V.
  • Ventura, Emanuele
  • Vidick, Thomas
  • Vyas, Nikhil
  • Végh, László A.
  • Wang, Baoxiang
  • Wang, Jack Z.
  • Wein, Alexander S.
  • Weinberg, S. Matthew
  • Wieder, Udi
  • Woodruff, David P.
  • Yang, Elizabeth
  • Yannakakis, Mihalis
  • Yasuda, Taisuke
  • Yodpinyanee, Anak
  • Yona, Gal
  • Yoshida, Yuichi
  • Zehavi, Meirav
  • Zhan, Wei
  • Zhandry, Mark
  • Zhang, Yihan
  • Zhou, Samson
  • Zlatin, Eitan
  • Zuo, Albert
  • Zuzic, Goran

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Vidick, Thomas

    Abstract | Document (369 KB) | BibTeX

    Hardness Amplification of Optimization Problems
    Authors: Goldenberg, Elazar ; Karthik C. S.,

    Abstract | Document (473 KB) | BibTeX

    Smooth and Strong PCPs
    Authors: Paradise, Orr

    Abstract | Document (791 KB) | BibTeX

    Approximately Strategyproof Tournament Rules: On Large Manipulating Sets and Cover-Consistence
    Authors: Schvartzman, Ariel ; Weinberg, S. Matthew ; Zlatin, Eitan ; Zuo, Albert

    Abstract | Document (822 KB) | BibTeX

    Span Programs and Quantum Space Complexity
    Authors: Jeffery, Stacey

    Abstract | Document (639 KB) | BibTeX

    DEEP-FRI: Sampling Outside the Box Improves Soundness
    Authors: Ben-Sasson, Eli ; Goldberg, Lior ; Kopparty, Swastik ; Saraf, Shubhangi

    Abstract | Document (711 KB) | BibTeX

    On the Cryptographic Hardness of Local Search
    Authors: Bitansky, Nir ; Gerichter, Idan

    Abstract | Document (680 KB) | BibTeX

    Interactive Coding with Constant Round and Communication Blowup
    Authors: Efremenko, Klim ; Haramaty, Elad ; Kalai, Yael Tauman

    Abstract | Document (647 KB) | BibTeX

    From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces
    Authors: Bei, Xiaohui ; Chen, Shiteng ; Guan, Ji ; Qiao, Youming ; Sun, Xiaoming

    Abstract | Document (770 KB) | BibTeX

    Hard Properties with (Very) Short PCPPs and Their Applications
    Authors: Ben-Eliezer, Omri ; Fischer, Eldar ; Levi, Amit ; Rothblum, Ron D.

    Abstract | Document (715 KB) | BibTeX

    Kronecker Powers of Tensors and Strassen’s Laser Method
    Authors: Conner, Austin ; Landsberg, Joseph M. ; Gesmundo, Fulvio ; Ventura, Emanuele

    Abstract | Document (690 KB) | BibTeX

    Algorithms and Lower Bounds for Cycles and Walks: Small Space and Sparse Graphs
    Authors: Lincoln, Andrea ; Vyas, Nikhil

    Abstract | Document (584 KB) | BibTeX

    High-Dimensional Expanders from Expanders
    Authors: Liu, Siqi ; Mohanty, Sidhanth ; Yang, Elizabeth

    Abstract | Document (1,004 KB) | BibTeX

    Approximating Cumulative Pebbling Cost Is Unique Games Hard
    Authors: Blocki, Jeremiah ; Lee, Seunghoon ; Zhou, Samson

    Abstract | Document (744 KB) | BibTeX

    Scheduling with Predictions and the Price of Misprediction
    Authors: Mitzenmacher, Michael

    Abstract | Document (448 KB) | BibTeX

    Reducing Inefficiency in Carbon Auctions with Imperfect Competition
    Authors: Goldner, Kira ; Immorlica, Nicole ; Lucier, Brendan

    Abstract | Document (744 KB) | BibTeX

    Preference-Informed Fairness
    Authors: Kim, Michael P. ; Korolova, Aleksandra ; Rothblum, Guy N. ; Yona, Gal

    Abstract | Document (577 KB) | BibTeX

    On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H
    Authors: Cai, Jin-Yi ; Govorov, Artem

    Abstract | Document (546 KB) | BibTeX

    Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria
    Authors: Etessami, Kousha ; Papadimitriou, Christos ; Rubinstein, Aviad ; Yannakakis, Mihalis

    Abstract | Document (636 KB) | BibTeX

    Resolution with Counting: Dag-Like Lower Bounds and Different Moduli
    Authors: Part, Fedor ; Tzameret, Iddo

    Abstract | Document (809 KB) | BibTeX

    The Random-Query Model and the Memory-Bounded Coupon Collector
    Authors: Raz, Ran ; Zhan, Wei

    Abstract | Document (430 KB) | BibTeX

    Strategy-Stealing Is Non-Constructive
    Authors: Bodwin, Greg ; Grossman, Ofer

    Abstract | Document (537 KB) | BibTeX

    Distribution-Free Testing of Linear Functions on ℝⁿ
    Authors: Fleming, Noah ; Yoshida, Yuichi

    Abstract | Document (586 KB) | BibTeX

    Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks
    Authors: Hitron, Yael ; Lynch, Nancy ; Musco, Cameron ; Parter, Merav

    Abstract | Document (1,761 KB) | BibTeX

    Signed Tropical Convexity
    Authors: Loho, Georg ; Végh, László A.

    Abstract | Document (681 KB) | BibTeX

    Distributional Property Testing in a Quantum World
    Authors: Gilyén, András ; Li, Tongyang

    Abstract | Document (691 KB) | BibTeX

    On Local Testability in the Non-Signaling Setting
    Authors: Chiesa, Alessandro ; Manohar, Peter ; Shinkar, Igor

    Abstract | Document (722 KB) | BibTeX

    Local Access to Huge Random Objects Through Partial Sampling
    Authors: Biswas, Amartya Shankha ; Rubinfeld, Ronitt ; Yodpinyanee, Anak

    Abstract | Document (1,427 KB) | BibTeX

    Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples
    Authors: Rubinfeld, Ronitt ; Vasilyan, Arsen

    Abstract | Document (668 KB) | BibTeX

    Sample Complexity Bounds for Influence Maximization
    Authors: Sadeh, Gal ; Cohen, Edith ; Kaplan, Haim

    Abstract | Document (784 KB) | BibTeX

    On Oblivious Amplification of Coin-Tossing Protocols
    Authors: Bitansky, Nir ; Geier, Nathan

    Abstract | Document (484 KB) | BibTeX

    A New Analysis of Differential Privacy’s Generalization Guarantees
    Authors: Jung, Christopher ; Ligett, Katrina ; Neel, Seth ; Roth, Aaron ; Sharifi-Malvajerdi, Saeed ; Shenfeld, Moshe

    Abstract | Document (526 KB) | BibTeX

    Robust Algorithms for the Secretary Problem
    Authors: Bradac, Domagoj ; Gupta, Anupam ; Singla, Sahil ; Zuzic, Goran

    Abstract | Document (646 KB) | BibTeX

    Universal Communication, Universal Graphs, and Graph Labeling
    Authors: Harms, Nathaniel

    Abstract | Document (621 KB) | BibTeX

    Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]
    Authors: Ilango, Rahul

    Abstract | Document (684 KB) | BibTeX

    Equivalence of Systematic Linear Data Structures and Matrix Rigidity
    Authors: Natarajan Ramamoorthy, Sivaramakrishnan ; Rashtchian, Cyrus

    Abstract | Document (592 KB) | BibTeX

    Computationally Data-Independent Memory Hard Functions
    Authors: Ameri, Mohammad Hassan ; Blocki, Jeremiah ; Zhou, Samson

    Abstract | Document (669 KB) | BibTeX

    Learning and Testing Variable Partitions
    Authors: Bogdanov, Andrej ; Wang, Baoxiang

    Abstract | Document (9,662 KB) | BibTeX

    Linear Time Subgraph Counting, Graph Degeneracy, and the Chasm at Size Six
    Authors: Bera, Suman K. ; Pashanasangi, Noujan ; Seshadhri, C.

    Abstract | Document (615 KB) | BibTeX

    Parameterization Above a Multiplicative Guarantee
    Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Lokshtanov, Daniel ; Panolan, Fahad ; Saurabh, Saket ; Zehavi, Meirav

    Abstract | Document (738 KB) | BibTeX

    Ad Hoc Multi-Input Functional Encryption
    Authors: Agrawal, Shweta ; Clear, Michael ; Frieder, Ophir ; Garg, Sanjam ; O'Neill, Adam ; Thaler, Justin

    Abstract | Document (845 KB) | BibTeX

    Unexpected Power of Random Strings
    Authors: Hirahara, Shuichi

    Abstract | Document (509 KB) | BibTeX

    Consensus vs Broadcast, with and Without Noise (Extended Abstract)
    Authors: Clementi, Andrea ; Gualà, Luciano ; Natale, Emanuele ; Pasquale, Francesco ; Scornavacca, Giacomo ; Trevisan, Luca

    Abstract | Document (532 KB) | BibTeX

    Testing Linear Inequalities of Subgraph Statistics
    Authors: Gishboliner, Lior ; Shapira, Asaf ; Stagni, Henrique

    Abstract | Document (431 KB) | BibTeX

    Top-Down Induction of Decision Trees: Rigorous Guarantees and Inherent Limitations
    Authors: Blanc, Guy ; Lange, Jane ; Tan, Li-Yang

    Abstract | Document (851 KB) | BibTeX

    Algorithms and Adaptivity Gaps for Stochastic k-TSP
    Authors: Jiang, Haotian ; Li, Jian ; Liu, Daogao ; Singla, Sahil

    Abstract | Document (666 KB) | BibTeX

    Strategic Payments in Financial Networks
    Authors: Bertschinger, Nils ; Hoefer, Martin ; Schmand, Daniel

    Abstract | Document (536 KB) | BibTeX

    Fault Tolerant Subgraphs with Applications in Kernelization
    Authors: Lochet, William ; Lokshtanov, Daniel ; Misra, Pranabendu ; Saurabh, Saket ; Sharma, Roohani ; Zehavi, Meirav

    Abstract | Document (969 KB) | BibTeX

    The Computational Cost of Asynchronous Neural Communication
    Authors: Hitron, Yael ; Parter, Merav ; Perri, Gur

    Abstract | Document (2,208 KB) | BibTeX

    Certified Algorithms: Worst-Case Analysis and Beyond
    Authors: Makarychev, Konstantin ; Makarychev, Yury

    Abstract | Document (488 KB) | BibTeX

    Low Diameter Graph Decompositions by Approximate Distance Computation
    Authors: Becker, Ruben ; Emek, Yuval ; Lenzen, Christoph

    Abstract | Document (710 KB) | BibTeX

    Generalized List Decoding
    Authors: Zhang, Yihan ; Budkuley, Amitalok J. ; Jaggi, Sidharth

    Abstract | Document (1,239 KB) | BibTeX

    Online Computation with Untrusted Advice
    Authors: Angelopoulos, Spyros ; Dürr, Christoph ; Jin, Shendan ; Kamali, Shahin ; Renault, Marc

    Abstract | Document (462 KB) | BibTeX

    Monochromatic Triangles, Intermediate Matrix Products, and Convolutions
    Authors: Lincoln, Andrea ; Polak, Adam ; Vassilevska Williams, Virginia

    Abstract | Document (542 KB) | BibTeX

    Matching Is as Easy as the Decision Problem, in the NC Model
    Authors: Anari, Nima ; Vazirani, Vijay V.

    Abstract | Document (584 KB) | BibTeX

    Advancing Subgroup Fairness via Sleeping Experts
    Authors: Blum, Avrim ; Lykouris, Thodoris

    Abstract | Document (567 KB) | BibTeX

    Instance Complexity and Unlabeled Certificates in the Decision Tree Model
    Authors: Grossman, Tomer ; Komargodski, Ilan ; Naor, Moni

    Abstract | Document (810 KB) | BibTeX

    On the Impossibility of Probabilistic Proofs in Relativized Worlds
    Authors: Chiesa, Alessandro ; Liu, Siqi

    Abstract | Document (722 KB) | BibTeX

    Lower Bounds for (Non-Monotone) Comparator Circuits
    Authors: Gál, Anna ; Robere, Robert

    Abstract | Document (468 KB) | BibTeX

    A Tight Lower Bound For Non-Coherent Index Erasure
    Authors: Lindzey, Nathan ; Rosmanis, Ansis

    Abstract | Document (726 KB) | BibTeX

    Optimal Single-Choice Prophet Inequalities from Samples
    Authors: Rubinstein, Aviad ; Wang, Jack Z. ; Weinberg, S. Matthew

    Abstract | Document (459 KB) | BibTeX

    Implementation in Advised Strategies: Welfare Guarantees from Posted-Price Mechanisms When Demand Queries Are NP-Hard
    Authors: Cai, Linda ; Thomas, Clay ; Weinberg, S. Matthew

    Abstract | Document (687 KB) | BibTeX

    Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard
    Authors: Demaine, Erik D. ; Hendrickson, Dylan H. ; Lynch, Jayson

    Abstract | Document (1,423 KB) | BibTeX

    Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract)
    Authors: Bouland, Adam ; Fefferman, Bill ; Vazirani, Umesh

    Abstract | Document (204 KB) | BibTeX

    New Query Lower Bounds for Submodular Function Minimization
    Authors: Graur, Andrei ; Pollner, Tristan ; Ramaswamy, Vidhya ; Weinberg, S. Matthew

    Abstract | Document (536 KB) | BibTeX

    Computation-Aware Data Aggregation
    Authors: Haeupler, Bernhard ; Hershkowitz, D. Ellis ; Kahng, Anson ; Procaccia, Ariel D.

    Abstract | Document (995 KB) | BibTeX

    Convertible Codes: New Class of Codes for Efficient Conversion of Coded Data in Distributed Storage
    Authors: Maturana, Francisco ; Rashmi, K. V.

    Abstract | Document (688 KB) | BibTeX

    Incentive Compatible Active Learning
    Authors: Echenique, Federico ; Prasad, Siddharth

    Abstract | Document (523 KB) | BibTeX

    Pseudorandomness and the Minimum Circuit Size Problem
    Authors: Santhanam, Rahul

    Abstract | Document (572 KB) | BibTeX

    Testing Properties of Multiple Distributions with Few Samples
    Authors: Aliakbarpour, Maryam ; Silwal, Sandeep

    Abstract | Document (705 KB) | BibTeX

    Beyond Natural Proofs: Hardness Magnification and Locality
    Authors: Chen, Lijie ; Hirahara, Shuichi ; Oliveira, Igor C. ; Pich, Ján ; Rajgopal, Ninad ; Santhanam, Rahul

    Abstract | Document (883 KB) | BibTeX

    Separating Two-Round Secure Computation From Oblivious Transfer
    Authors: Applebaum, Benny ; Brakerski, Zvika ; Garg, Sanjam ; Ishai, Yuval ; Srinivasan, Akshayaram

    Abstract | Document (517 KB) | BibTeX

    Trade-Offs Between Size and Degree in Polynomial Calculus
    Authors: Lagarde, Guillaume ; Nordström, Jakob ; Sokolov, Dmitry ; Swernofsky, Joseph

    Abstract | Document (543 KB) | BibTeX

    Smoothed Efficient Algorithms and Reductions for Network Coordination Games
    Authors: Boodaghians, Shant ; Kulkarni, Rucha ; Mehta, Ruta

    Abstract | Document (509 KB) | BibTeX

    Local-To-Global Agreement Expansion via the Variance Method
    Authors: Kaufman, Tali ; Mass, David

    Abstract | Document (470 KB) | BibTeX

    MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture
    Authors: Chan, T-H. Hubert ; Chung, Kai-Min ; Lin, Wei-Kai ; Shi, Elaine

    Abstract | Document (854 KB) | BibTeX

    Choice and Bias in Random Walks
    Authors: Georgakopoulos, Agelos ; Haslegrave, John ; Sauerwald, Thomas ; Sylvester, John

    Abstract | Document (642 KB) | BibTeX

    Graph Spanners in the Message-Passing Model
    Authors: Fernández V, Manuel ; Woodruff, David P. ; Yasuda, Taisuke

    Abstract | BibTeX

    Computational Hardness of Certifying Bounds on Constrained PCA Problems
    Authors: Bandeira, Afonso S. ; Kunisky, Dmitriy ; Wein, Alexander S.

    Abstract | Document (640 KB) | BibTeX

    Pseudo-Deterministic Streaming
    Authors: Goldwasser, Shafi ; Grossman, Ofer ; Mohanty, Sidhanth ; Woodruff, David P.

    Abstract | Document (636 KB) | BibTeX

    Limits to Non-Malleability
    Authors: Ball, Marshall ; Dachman-Soled, Dana ; Kulkarni, Mukul ; Malkin, Tal

    Abstract | Document (680 KB) | BibTeX

    Cryptography from Information Loss
    Authors: Ball, Marshall ; Boyle, Elette ; Degwekar, Akshay ; Deshpande, Apoorvaa ; Rosen, Alon ; Vaikuntanathan, Vinod ; Vasudevan, Prashant Nalini

    Abstract | Document (621 KB) | BibTeX

    Affine Determinant Programs: A Framework for Obfuscation and Witness Encryption
    Authors: Bartusek, James ; Ishai, Yuval ; Jain, Aayush ; Ma, Fermi ; Sahai, Amit ; Zhandry, Mark

    Abstract | Document (767 KB) | BibTeX

    OV Graphs Are (Probably) Hard Instances
    Authors: Alman, Josh ; Vassilevska Williams, Virginia

    Abstract | Document (537 KB) | BibTeX

    Finding Skewed Subcubes Under a Distribution
    Authors: Gopalan, Parikshit ; Levin, Roie ; Wieder, Udi

    Abstract | Document (661 KB) | BibTeX

    Combinatorial Lower Bounds for 3-Query LDCs
    Authors: Bhattacharyya, Arnab ; Chandran, L. Sunil ; Ghoshal, Suprovat

    Abstract | Document (479 KB) | BibTeX

    On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?
    Authors: Ball, Marshall ; Holmgren, Justin ; Ishai, Yuval ; Liu, Tianren ; Malkin, Tal

    Abstract | Document (650 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI