ITCS 2021 January 6-8, 2021, Virtual Conference

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)



James R. Lee (Ed.)
ISBN 978-3-95977-177-1, LIPICS Vol. 185 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 42 MB)
Search Publication Server


Authors
  • Aharonov, Dorit
  • Ahmadian, Sara
  • Anari, Nima
  • Angelopoulos, Spyros
  • Arunachalam, Srinivasan
  • Arunachaleswaran, Eshwar Ram
  • Ashlagi, Itai
  • Babaioff, Moshe
  • Barak, Boaz
  • Bartlett, Peter L.
  • Bechtel, Curtis
  • Ben-Eliezer, Omri
  • Beyersdorff, Olaf
  • Beyhaghi, Hedyeh
  • Bhatia, Kush
  • Bhattacharya, Anup
  • Bishnu, Arijit
  • Blocki, Jeremiah
  • Böhm, Benjamin
  • Borst, Sander
  • Braverman, Mark
  • Briët, Jop
  • Bubeck, Sébastien
  • Buchbinder, Niv
  • Burrell, Noah
  • Cai, Yang
  • Charikar, Moses
  • Chen, Lijie
  • Chen, Xi
  • Chou, Chi-Ning
  • Cinkoske, Mike
  • Coester, Christian
  • Cohen, Michael B.
  • Cole, Richard
  • Correa, José
  • Couteau, Geoffroy
  • Dadush, Daniel
  • Dafni, Neta
  • Dagan, Yuval
  • De, Anindya
  • Ding, Kimberly
  • Dinur, Irit
  • Dixon, Peter
  • Dragan, Anca D.
  • Dughmi, Shaddin
  • Dutta, Pranjal
  • Dütting, Paul
  • Dziembowski, Stefan
  • Efremenko, Klim
  • Eldar, Lior
  • Emek, Yuval
  • Fabiański, Grzegorz
  • Farshim, Pooya
  • Faust, Sebastian
  • Feng, Weiming
  • Feng, Yiding
  • Filmus, Yuval
  • Fischer, Eldar
  • Fischer, Felix
  • Fraigniaud, Pierre
  • Gao, Xun
  • Garg, Ankit
  • Garg, Shivam
  • Ghazi, Badih
  • Girish, Uma
  • Goel, Surbhi
  • Goldwasser, Shafi
  • Golovnev, Alexander
  • Gordon, Deborah M.
  • Grilo, Alex B.
  • Grochow, Joshua A.
  • Grossman, Ofer
  • Guruswami, Venkatesan
  • Harsha, Prahladh
  • Hartline, Jason
  • Haviv, Ishay
  • He, Kun
  • Hoefer, Martin
  • Holmgren, Justin
  • Hoza, William M.
  • Hu, Nathan
  • Immorlica, Nicole
  • Impagliazzo, Russell
  • Kane, Daniel
  • Kannan, Sampath
  • Kash, Ian A.
  • Kelman, Esty
  • Khot, Subhash
  • Kindler, Guy
  • Kleinberg, Robert
  • Klivans, Adam
  • Kol, Gillat
  • Komargodski, Ilan
  • Korten, Oliver
  • Kothari, Robin
  • Kretschmer, William
  • Kulikov, Alexander S.
  • Kumar, Mrinal
  • Kumar, Ravi
  • Kumar, Vinayak M.
  • Kuszmaul, William
  • Kutten, Shay
  • Labib, Farrokh
  • Lau, Joshua
  • Lee, Chin Ho
  • Lee, James R.
  • Le Gall, François
  • Leverrier, Anthony
  • Levi, Amit
  • Lifshitz, Noam
  • Lindzey, Nathan
  • Lin, Jiabao
  • Liu, Allen
  • Londe, Vivien
  • Lucier, Brendan
  • Mahmoody, Mohammad
  • Manurangsi, Pasin
  • Mardia, Jay
  • McGuire, Sam
  • Meir, Or
  • Meir, Uri
  • Metger, Tony
  • Minzer, Dor
  • Mishra, Gopinath
  • Mitropolsky, Daniel
  • Mittal, Kunal
  • Moran, Shay
  • Mosheiff, Jonathan
  • Mudigonda, Abhijit S.
  • Musco, Cameron
  • Musco, Christopher
  • Nadimpalli, Shivam
  • Nanashima, Mikito
  • Narayanan, Shyam
  • Nenadov, Rajko
  • Netrapalli, Praneeth
  • Niazadeh, Rad
  • Nishimura, Harumichi
  • Olver, Neil
  • Pallavoor, Ramesh Krishnan S.
  • Papadimitriou, Christos
  • Papp, Pál András
  • Paramonov, Dmitry
  • Pavan, A.
  • Paz, Ami
  • Peng, Binghui
  • Podder, Supartha
  • Psomas, Alexandros
  • Pyne, Edward
  • Qiao, Youming
  • Raskhodnikova, Sofya
  • Raz, Ran
  • Reichman, Daniel
  • Remscrim, Zachary
  • Ren, Michael
  • Resch, Nicolas
  • Riahi, Siavash
  • Ritossa, Angus
  • Ron-Zewi, Noga
  • Rosenthal, Gregory
  • Rossman, Benjamin
  • Roth, Aaron
  • Rothblum, Guy N.
  • Rubinstein, Aviad
  • Saberi, Amin
  • Safra, Muli
  • Saxena, Nitin
  • Saxena, Raghuvansh R.
  • Schewior, Kevin
  • Schild, Aaron
  • Schoenebeck, Grant
  • Schramm, Tselil
  • Sellke, Mark
  • Servedio, Rocco A.
  • Shafer, Jonathan
  • Shaltiel, Ronen
  • Sherif, Suhail
  • Shi, Elaine
  • Shiragur, Kirankumar
  • Shi, Yangguang
  • Sidford, Aaron
  • Silas, Shashwat
  • Sinha, Makrand
  • Sinha, Sandip
  • Solomon, Noam
  • Solomon, Shay
  • Song, Zhao
  • Steger, Angelika
  • Steinhardt, Jacob
  • Sun, Xiaoming
  • Su, Pascal
  • Tal, Avishay
  • Tardos, Éva
  • Thierauf, Thomas
  • Thomas, Clayton
  • Tian, Kevin
  • Tulsiani, Madhur
  • Upasana, Anannya
  • Vadhan, Salil
  • van den Brand, Jan
  • Varma, Nithin
  • Vazirani, Vijay V.
  • Velegkas, Grigoris
  • Vidick, Thomas
  • Vinodchandran, N. V.
  • Vinyals, Marc
  • Volk, Ben Lee
  • Wattenhofer, Roger
  • Wein, Alexander S.
  • Weinberg, S. Matthew
  • Weinstein, Omri
  • Westover, Alek
  • Williams, R. Ryan
  • Woodruff, David P.
  • Wootters, Mary
  • Yannakakis, Mihalis
  • Yehudayoff, Amir
  • Yin, Yitong
  • Yoshida, Yuichi
  • Yu, Fang-Yi
  • Yu, Nengkun
  • Zadimoghaddam, Morteza
  • Zémor, Gilles
  • Zhao, Geng
  • Zhou, Samson
  • Ziani, Juba
  • Ziliotto, Bruno

  •   
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Lee, James R.

    Abstract | Document (341 KB) | BibTeX

    The Entropy of Lies: Playing Twenty Questions with a Liar
    Authors: Dagan, Yuval ; Filmus, Yuval ; Kane, Daniel ; Moran, Shay

    Abstract | Document (498 KB) | BibTeX

    Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?)
    Authors: Impagliazzo, Russell ; McGuire, Sam

    Abstract | Document (568 KB) | BibTeX

    Algorithmic Persuasion with Evidence
    Authors: Hoefer, Martin ; Manurangsi, Pasin ; Psomas, Alexandros

    Abstract | Document (606 KB) | BibTeX

    The Complexity of Finding Fair Independent Sets in Cycles
    Authors: Haviv, Ishay

    Abstract | Document (514 KB) | BibTeX

    Sharp Threshold Rates for Random Codes
    Authors: Guruswami, Venkatesan ; Mosheiff, Jonathan ; Resch, Nicolas ; Silas, Shashwat ; Wootters, Mary

    Abstract | Document (548 KB) | BibTeX

    Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation
    Authors: Musco, Cameron ; Musco, Christopher ; Woodruff, David P.

    Abstract | Document (565 KB) | BibTeX

    Pseudorandom Generators for Unbounded-Width Permutation Branching Programs
    Authors: Hoza, William M. ; Pyne, Edward ; Vadhan, Salil

    Abstract | Document (622 KB) | BibTeX

    Pipeline Interventions
    Authors: Arunachaleswaran, Eshwar Ram ; Kannan, Sampath ; Roth, Aaron ; Ziani, Juba

    Abstract | Document (550 KB) | BibTeX

    A Polynomial Degree Bound on Equations for Non-Rigid Matrices and Small Linear Circuits
    Authors: Kumar, Mrinal ; Volk, Ben Lee

    Abstract | Document (497 KB) | BibTeX

    The Strongish Planted Clique Hypothesis and Its Consequences
    Authors: Manurangsi, Pasin ; Rubinstein, Aviad ; Schramm, Tselil

    Abstract | Document (582 KB) | BibTeX

    Sample Efficient Identity Testing and Independence Testing of Quantum States
    Authors: Yu, Nengkun

    Abstract | Document (627 KB) | BibTeX

    Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
    Authors: Beyersdorff, Olaf ; Böhm, Benjamin

    Abstract | Document (680 KB) | BibTeX

    The Quantum Supremacy Tsirelson Inequality
    Authors: Kretschmer, William

    Abstract | Document (528 KB) | BibTeX

    Approximately Strategyproof Tournament Rules in the Probabilistic Setting
    Authors: Ding, Kimberly ; Weinberg, S. Matthew

    Abstract | Document (588 KB) | BibTeX

    Even the Easiest(?) Graph Coloring Problem Is Not Easy in Streaming!
    Authors: Bhattacharya, Anup ; Bishnu, Arijit ; Mishra, Gopinath ; Upasana, Anannya

    Abstract | Document (566 KB) | BibTeX

    The Variable-Processor Cup Game
    Authors: Kuszmaul, William ; Westover, Alek

    Abstract | Document (534 KB) | BibTeX

    Comparison Graphs: A Unified Method for Uniformity Testing
    Authors: Meir, Uri

    Abstract | Document (487 KB) | BibTeX

    Circular Trace Reconstruction
    Authors: Narayanan, Shyam ; Ren, Michael

    Abstract | Document (558 KB) | BibTeX

    Self-Testing of a Single Quantum Device Under Computational Assumptions
    Authors: Metger, Tony ; Vidick, Thomas

    Abstract | Document (466 KB) | BibTeX

    Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime
    Authors: Chen, Xi ; De, Anindya ; Lee, Chin Ho ; Servedio, Rocco A. ; Sinha, Sandip

    Abstract | Document (655 KB) | BibTeX

    Metrical Service Systems with Transformations
    Authors: Bubeck, Sébastien ; Buchbinder, Niv ; Coester, Christian ; Sellke, Mark

    Abstract | Document (527 KB) | BibTeX

    Tight Hardness Results for Training Depth-2 ReLU Networks
    Authors: Goel, Surbhi ; Klivans, Adam ; Manurangsi, Pasin ; Reichman, Daniel

    Abstract | Document (554 KB) | BibTeX

    A Largish Sum-Of-Squares Implies Circuit Hardness and Derandomization
    Authors: Dutta, Pranjal ; Saxena, Nitin ; Thierauf, Thomas

    Abstract | Document (648 KB) | BibTeX

    Circuit Depth Reductions
    Authors: Golovnev, Alexander ; Kulikov, Alexander S. ; Williams, R. Ryan

    Abstract | Document (565 KB) | BibTeX

    Dynamic Inference in Probabilistic Graphical Models
    Authors: Feng, Weiming ; He, Kun ; Sun, Xiaoming ; Yin, Yitong

    Abstract | Document (679 KB) | BibTeX

    Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality
    Authors: Kelman, Esty ; Khot, Subhash ; Kindler, Guy ; Minzer, Dor ; Safra, Muli

    Abstract | Document (496 KB) | BibTeX

    On Rich 2-to-1 Games
    Authors: Braverman, Mark ; Khot, Subhash ; Minzer, Dor

    Abstract | Document (597 KB) | BibTeX

    Distributed Quantum Proofs for Replicated Data
    Authors: Fraigniaud, Pierre ; Le Gall, François ; Nishimura, Harumichi ; Paz, Ami

    Abstract | Document (599 KB) | BibTeX

    On Basing Auxiliary-Input Cryptography on NP-Hardness via Nonadaptive Black-Box Reductions
    Authors: Nanashima, Mikito

    Abstract | Document (474 KB) | BibTeX

    Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits
    Authors: Barak, Boaz ; Chou, Chi-Ning ; Gao, Xun

    Abstract | Document (664 KB) | BibTeX

    On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
    Authors: Grochow, Joshua A. ; Qiao, Youming

    Abstract | Document (617 KB) | BibTeX

    Bounds on the QAC^0 Complexity of Approximating Parity
    Authors: Rosenthal, Gregory

    Abstract | Document (542 KB) | BibTeX

    Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists)
    Authors: Ron-Zewi, Noga ; Shaltiel, Ronen ; Varma, Nithin

    Abstract | Document (603 KB) | BibTeX

    Is the Space Complexity of Planted Clique Recovery the Same as That of Detection?
    Authors: Mardia, Jay

    Abstract | Document (659 KB) | BibTeX

    Algorithms and Hardness for Multidimensional Range Updates and Queries
    Authors: Lau, Joshua ; Ritossa, Angus

    Abstract | Document (617 KB) | BibTeX

    Two Combinatorial MA-Complete Problems
    Authors: Aharonov, Dorit ; Grilo, Alex B.

    Abstract | Document (652 KB) | BibTeX

    Delegated Stochastic Probing
    Authors: Bechtel, Curtis ; Dughmi, Shaddin

    Abstract | Document (464 KB) | BibTeX

    Explicit SoS Lower Bounds from High-Dimensional Expanders
    Authors: Dinur, Irit ; Filmus, Yuval ; Harsha, Prahladh ; Tulsiani, Madhur

    Abstract | Document (548 KB) | BibTeX

    Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum Turing Machines
    Authors: Remscrim, Zachary

    Abstract | Document (611 KB) | BibTeX

    On the Complexity of #CSP^d
    Authors: Lin, Jiabao

    Abstract | Document (464 KB) | BibTeX

    Interactive Proofs for Verifying Machine Learning
    Authors: Goldwasser, Shafi ; Rothblum, Guy N. ; Shafer, Jonathan ; Yehudayoff, Amir

    Abstract | Document (641 KB) | BibTeX

    Ordered Graph Limits and Their Applications
    Authors: Ben-Eliezer, Omri ; Fischer, Eldar ; Levi, Amit ; Yoshida, Yuichi

    Abstract | Document (598 KB) | BibTeX

    Error Correcting Codes for Uncompressed Messages
    Authors: Grossman, Ofer ; Holmgren, Justin

    Abstract | Document (611 KB) | BibTeX

    Total Functions in the Polynomial Hierarchy
    Authors: Kleinberg, Robert ; Korten, Oliver ; Mitropolsky, Daniel ; Papadimitriou, Christos

    Abstract | Document (624 KB) | BibTeX

    Relaxing Common Belief for Social Networks
    Authors: Burrell, Noah ; Schoenebeck, Grant

    Abstract | Document (652 KB) | BibTeX

    Tiered Random Matching Markets: Rank Is Proportional to Popularity
    Authors: Ashlagi, Itai ; Braverman, Mark ; Saberi, Amin ; Thomas, Clayton ; Zhao, Geng

    Abstract | Document (516 KB) | BibTeX

    Black-Box Uselessness: Composing Separations in Cryptography
    Authors: Couteau, Geoffroy ; Farshim, Pooya ; Mahmoody, Mohammad

    Abstract | Document (542 KB) | BibTeX

    Pseudobinomiality of the Sticky Random Walk
    Authors: Guruswami, Venkatesan ; Kumar, Vinayak M.

    Abstract | Document (556 KB) | BibTeX

    Robust Quantum Entanglement at (Nearly) Room Temperature
    Authors: Eldar, Lior

    Abstract | Document (605 KB) | BibTeX

    Time-Space Lower Bounds for Simulating Proof Systems with Quantum and Randomized Verifiers
    Authors: Mudigonda, Abhijit S. ; Williams, R. Ryan

    Abstract | Document (615 KB) | BibTeX

    Online Search with a Hint
    Authors: Angelopoulos, Spyros

    Abstract | Document (472 KB) | BibTeX

    Sequential Defaulting in Financial Networks
    Authors: Papp, Pál András ; Wattenhofer, Roger

    Abstract | Document (492 KB) | BibTeX

    No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization
    Authors: Garg, Ankit ; Kothari, Robin ; Netrapalli, Praneeth ; Sherif, Suhail

    Abstract | Document (526 KB) | BibTeX

    Quantum Versus Randomized Communication Complexity, with Efficient Players
    Authors: Girish, Uma ; Raz, Ran ; Tal, Avishay

    Abstract | Document (543 KB) | BibTeX

    Agnostic Learning with Unknown Utilities
    Authors: Bhatia, Kush ; Bartlett, Peter L. ; Dragan, Anca D. ; Steinhardt, Jacob

    Abstract | Document (620 KB) | BibTeX

    On Distributed Differential Privacy and Counting Distinct Elements
    Authors: Chen, Lijie ; Ghazi, Badih ; Kumar, Ravi ; Manurangsi, Pasin

    Abstract | Document (647 KB) | BibTeX

    A Generalized Matching Reconfiguration Problem
    Authors: Solomon, Noam ; Solomon, Shay

    Abstract | Document (483 KB) | BibTeX

    Sensitivity Analysis of the Maximum Matching Problem
    Authors: Yoshida, Yuichi ; Zhou, Samson

    Abstract | Document (613 KB) | BibTeX

    Computational Complexity of the Hylland-Zeckhauser Scheme for One-Sided Matching Markets
    Authors: Vazirani, Vijay V. ; Yannakakis, Mihalis

    Abstract | Document (501 KB) | BibTeX

    An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability
    Authors: Nenadov, Rajko ; Steger, Angelika ; Su, Pascal

    Abstract | Document (708 KB) | BibTeX

    Communication Memento: Memoryless Communication Complexity
    Authors: Arunachalam, Srinivasan ; Podder, Supartha

    Abstract | Document (569 KB) | BibTeX

    Relative Lipschitzness in Extragradient Methods and a Direct Recipe for Acceleration
    Authors: Cohen, Michael B. ; Sidford, Aaron ; Tian, Kevin

    Abstract | Document (569 KB) | BibTeX

    Training (Overparametrized) Neural Networks in Near-Linear Time
    Authors: van den Brand, Jan ; Peng, Binghui ; Song, Zhao ; Weinstein, Omri

    Abstract | Document (588 KB) | BibTeX

    A New Connection Between Node and Edge Depth Robust Graphs
    Authors: Blocki, Jeremiah ; Cinkoske, Mike

    Abstract | Document (560 KB) | BibTeX

    Towards Local Testability for Quantum Coding
    Authors: Leverrier, Anthony ; Londe, Vivien ; Zémor, Gilles

    Abstract | Document (421 KB) | BibTeX

    Complete Problems for Multi-Pseudodeterministic Computations
    Authors: Dixon, Peter ; Pavan, A. ; Vinodchandran, N. V.

    Abstract | Document (522 KB) | BibTeX

    Online Paging with a Vanishing Regret
    Authors: Emek, Yuval ; Kutten, Shay ; Shi, Yangguang

    Abstract | Document (615 KB) | BibTeX

    Differentially Oblivious Turing Machines
    Authors: Komargodski, Ilan ; Shi, Elaine

    Abstract | Document (572 KB) | BibTeX

    Quantitative Correlation Inequalities via Semigroup Interpolation
    Authors: De, Anindya ; Nadimpalli, Shivam ; Servedio, Rocco A.

    Abstract | Document (551 KB) | BibTeX

    Shrinkage of Decision Lists and DNF Formulas
    Authors: Rossman, Benjamin

    Abstract | Document (570 KB) | BibTeX

    Block Rigidity: Strong Multiplayer Parallel Repetition Implies Super-Linear Lower Bounds for Turing Machines
    Authors: Mittal, Kunal ; Raz, Ran

    Abstract | Document (452 KB) | BibTeX

    Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma
    Authors: Dziembowski, Stefan ; Fabiański, Grzegorz ; Faust, Sebastian ; Riahi, Siavash

    Abstract | Document (589 KB) | BibTeX

    Majorizing Measures for the Optimizer
    Authors: Borst, Sander ; Dadush, Daniel ; Olver, Neil ; Sinha, Makrand

    Abstract | Document (545 KB) | BibTeX

    Randomness and Fairness in Two-Sided Matching with Limited Interviews
    Authors: Beyhaghi, Hedyeh ; Tardos, Éva

    Abstract | Document (475 KB) | BibTeX

    Counterexamples to the Low-Degree Conjecture
    Authors: Holmgren, Justin ; Wein, Alexander S.

    Abstract | Document (402 KB) | BibTeX

    High-Entropy Dual Functions and Locally Decodable Codes (Extended Abstract)
    Authors: Briët, Jop ; Labib, Farrokh

    Abstract | Document (252 KB) | BibTeX

    Buying Data over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions
    Authors: Immorlica, Nicole ; Kash, Ian A. ; Lucier, Brendan

    Abstract | Document (559 KB) | BibTeX

    Learning and Strongly Truthful Multi-Task Peer Prediction: A Variational Approach
    Authors: Schoenebeck, Grant ; Yu, Fang-Yi

    Abstract | Document (601 KB) | BibTeX

    Distributed Load Balancing: A New Framework and Improved Guarantees
    Authors: Ahmadian, Sara ; Liu, Allen ; Peng, Binghui ; Zadimoghaddam, Morteza

    Abstract | Document (557 KB) | BibTeX

    Erasure-Resilient Sublinear-Time Graph Algorithms
    Authors: Levi, Amit ; Pallavoor, Ramesh Krishnan S. ; Raskhodnikova, Sofya ; Varma, Nithin

    Abstract | Document (618 KB) | BibTeX

    How to Sell Information Optimally: An Algorithmic Study
    Authors: Cai, Yang ; Velegkas, Grigoris

    Abstract | Document (580 KB) | BibTeX

    Computation over the Noisy Broadcast Channel with Malicious Parties
    Authors: Efremenko, Klim ; Kol, Gillat ; Paramonov, Dmitry ; Saxena, Raghuvansh R.

    Abstract | Document (549 KB) | BibTeX

    Sampling Arborescences in Parallel
    Authors: Anari, Nima ; Hu, Nathan ; Saberi, Amin ; Schild, Aaron

    Abstract | Document (548 KB) | BibTeX

    Non-Quasi-Linear Agents in Quasi-Linear Mechanisms (Extended Abstract)
    Authors: Babaioff, Moshe ; Cole, Richard ; Hartline, Jason ; Immorlica, Nicole ; Lucier, Brendan

    Abstract | Document (197 KB) | BibTeX

    A Model for Ant Trail Formation and its Convergence Properties (Extended Abstract)
    Authors: Charikar, Moses ; Garg, Shivam ; Gordon, Deborah M. ; Shiragur, Kirankumar

    Abstract | Document (202 KB) | BibTeX

    Unknown I.I.D. Prophets: Better Bounds, Streaming Algorithms, and a New Impossibility (Extended Abstract)
    Authors: Correa, José ; Dütting, Paul ; Fischer, Felix ; Schewior, Kevin ; Ziliotto, Bruno

    Abstract | Document (227 KB) | BibTeX

    Complexity Measures on the Symmetric Group and Beyond (Extended Abstract)
    Authors: Dafni, Neta ; Filmus, Yuval ; Lifshitz, Noam ; Lindzey, Nathan ; Vinyals, Marc

    Abstract | Document (319 KB) | BibTeX

    Batching and Optimal Multi-Stage Bipartite Allocations (Extended Abstract)
    Authors: Feng, Yiding ; Niazadeh, Rad

    Abstract | Document (208 KB) | BibTeX

    Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract)
    Authors: Filmus, Yuval ; Meir, Or ; Tal, Avishay

    Abstract | Document (425 KB) | BibTeX

      




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