Portal - ITCS 2022

ITCS 2022	January 31 to February 3, 2022, Berkeley, CA, USA
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) Mark Braverman (Ed.)
ISBN 978-3-95977-217-4, LIPICS Vol. 215	ISSN 1868-8969

Additional Information

License
Conference Website
Complete volume (PDF, 44 MB)
Search Publication Server

Authors

Biswas, Amartya Shankha

Chattopadhyay, Arkadev

Chattopadhyay, Eshan

Chaudhury, Bhaskar Ray

Christodoulou, Giorgos

Cohen, Sarel

Con, Roni

Coregliano, Leonardo Nagami

Dinesh, Krishnamoorthy

Farach-Colton, Martín

Fawzi, Omar

Fefferman, Bill

Ferreira, Matheus V. X.

Hajiaghayi, MohammadTaghi

Jeronimo, Fernando Granha

Lagodzinski, J.A. Gregor

Lindermayr, Alexander

Mitzenmacher, Michael

Müller-Hermes, Alexander

Srinivasan, Akshayaram

Vaikuntanathan, Vinod

Valiant, Paul

van Melkebeek, Dieter

Varma, Nithin

Vassilevska Williams, Virginia

Front Matter, Table of Contents, Preface, Conference Organization

Authors: Braverman, Mark

Abstract | Document (641 KB) | BibTeX

Maximizing Revenue in the Presence of Intermediaries

Authors: Aggarwal, Gagan ; Bhawalkar, Kshipra ; Guruganesh, Guru ; Perlroth, Andres

Abstract | Document (739 KB) | BibTeX

Algebraic Restriction Codes and Their Applications

Authors: Aggarwal, Divesh ; Döttling, Nico ; Dujmovic, Jesko ; Hajiabadi, Mohammad ; Malavolta, Giulio ; Obremski, Maciej

Abstract | Document (734 KB) | BibTeX

Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity

Authors: Akmal, Shyan ; Chen, Lijie ; Jin, Ce ; Raj, Malvika ; Williams, Ryan

Abstract | Document (934 KB) | BibTeX

Pre-Constrained Encryption

Authors: Ananth, Prabhanjan ; Jain, Abhishek ; Jin, Zhengzhong ; Malavolta, Giulio

Abstract | Document (810 KB) | BibTeX

Domain Sparsification of Discrete Distributions Using Entropic Independence

Authors: Anari, Nima ; Dereziński, Michał ; Vuong, Thuy-Duong ; Yang, Elizabeth

Abstract | Document (768 KB) | BibTeX

Circuit Lower Bounds for Low-Energy States of Quantum Code Hamiltonians

Authors: Anshu, Anurag ; Nirkhe, Chinmay

Abstract | Document (864 KB) | BibTeX

Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems

Authors: Antaki, Shiri ; Liu, Quanquan C. ; Solomon, Shay

Abstract | Document (877 KB) | BibTeX

Secret Sharing, Slice Formulas, and Monotone Real Circuits

Authors: Applebaum, Benny ; Beimel, Amos ; Nir, Oded ; Peter, Naty ; Pitassi, Toniann

Abstract | Document (852 KB) | BibTeX

An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams

Authors: Assadi, Sepehr ; Shah, Vihan

Abstract | Document (901 KB) | BibTeX

Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions

Authors: Assadi, Sepehr ; Wang, Chen

Abstract | Document (900 KB) | BibTeX

Multi-Channel Bayesian Persuasion

Authors: Babichenko, Yakov ; Talgam-Cohen, Inbal ; Xu, Haifeng ; Zabarnyi, Konstantin

Abstract | Document (338 KB) | BibTeX

Randomness Extraction from Somewhat Dependent Sources

Authors: Ball, Marshall ; Goldreich, Oded ; Malkin, Tal

Abstract | Document (711 KB) | BibTeX

Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing

Authors: Bansal, Nikhil ; Jiang, Haotian ; Meka, Raghu ; Singla, Sahil ; Sinha, Makrand

Abstract | Document (841 KB) | BibTeX

Classical Algorithms and Quantum Limitations for Maximum Cut on High-Girth Graphs

Authors: Barak, Boaz ; Marwaha, Kunal

Abstract | Document (1,577 KB) | BibTeX

Indistinguishability Obfuscation of Null Quantum Circuits and Applications

Authors: Bartusek, James ; Malavolta, Giulio

Abstract | Document (631 KB) | BibTeX

An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes

Authors: Baweja, Anubhav ; Jia, Justin ; Woodruff, David P.

Abstract | Document (918 KB) | BibTeX

FPT Algorithms for Finding Near-Cliques in c-Closed Graphs

Authors: Behera, Balaram ; Husić, Edin ; Jain, Shweta ; Roughgarden, Tim ; Seshadhri, C.

Abstract | Document (918 KB) | BibTeX

What Does Dynamic Optimality Mean in External Memory?

Authors: Bender, Michael A. ; Farach-Colton, Martín ; Kuszmaul, William

Abstract | Document (798 KB) | BibTeX

Improved Hardness of BDD and SVP Under Gap-(S)ETH

Authors: Bennett, Huck ; Peikert, Chris ; Tang, Yi

Abstract | Document (765 KB) | BibTeX

Mixing of 3-Term Progressions in Quasirandom Groups

Authors: Bhangale, Amey ; Harsha, Prahladh ; Roy, Sourya

Abstract | Document (654 KB) | BibTeX

Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs

Authors: Bhangale, Amey ; Stanković, Aleksa

Abstract | Document (823 KB) | BibTeX

Separating the NP-Hardness of the Grothendieck Problem from the Little-Grothendieck Problem

Authors: Bhattiprolu, Vijay ; Lee, Euiwoong ; Tulsiani, Madhur

Abstract | Document (811 KB) | BibTeX

Fixed-Parameter Sensitivity Oracles

Authors: Bilò, Davide ; Casel, Katrin ; Choudhary, Keerti ; Cohen, Sarel ; Friedrich, Tobias ; Lagodzinski, J.A. Gregor ; Schirneck, Martin ; Wietheger, Simon

Abstract | Document (860 KB) | BibTeX

Local Access to Random Walks

Authors: Biswas, Amartya Shankha ; Pyne, Edward ; Rubinfeld, Ronitt

Abstract | Document (840 KB) | BibTeX

Vertex Fault-Tolerant Emulators

Authors: Bodwin, Greg ; Dinitz, Michael ; Nazari, Yasamin

Abstract | Document (757 KB) | BibTeX

Bounded Indistinguishability for Simple Sources

Authors: Bogdanov, Andrej ; Dinesh, Krishnamoorthy ; Filmus, Yuval ; Ishai, Yuval ; Kaplan, Avi ; Srinivasan, Akshayaram

Abstract | Document (738 KB) | BibTeX

Locality-Preserving Hashing for Shifts with Connections to Cryptography

Authors: Boyle, Elette ; Dinur, Itai ; Gilboa, Niv ; Ishai, Yuval ; Keller, Nathan ; Klein, Ohad

Abstract | Document (913 KB) | BibTeX

Lattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABE

Authors: Brakerski, Zvika ; Vaikuntanathan, Vinod

Abstract | Document (782 KB) | BibTeX

Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics

Authors: Brandt, Sebastian ; Chang, Yi-Jun ; Grebík, Jan ; Grunau, Christoph ; Rozhoň, Václav ; Vidnyánszky, Zoltán

Abstract | Document (1,307 KB) | BibTeX

PCPs and Instance Compression from a Cryptographic Lens

Authors: Bronfman, Liron ; Rothblum, Ron D.

Abstract | Document (736 KB) | BibTeX

Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks

Authors: Buhrman, Harry ; Loff, Bruno ; Patro, Subhasree ; Speelman, Florian

Abstract | Document (714 KB) | BibTeX

Small Hazard-Free Transducers

Authors: Bund, Johannes ; Lenzen, Christoph ; Medina, Moti

Abstract | Document (1,000 KB) | BibTeX

Faster Sparse Matrix Inversion and Rank Computation in Finite Fields

Authors: Casacuberta, Sílvia ; Kyng, Rasmus

Abstract | Document (807 KB) | BibTeX

Algorithms and Lower Bounds for Comparator Circuits from Shrinkage

Authors: Cavalar, Bruno P. ; Lu, Zhenjian

Abstract | Document (902 KB) | BibTeX

Quantum Distributed Algorithms for Detection of Cliques

Authors: Censor-Hillel, Keren ; Fischer, Orr ; Le Gall, François ; Leitersdorf, Dean ; Oshman, Rotem

Abstract | Document (1,005 KB) | BibTeX

Distributed Vertex Cover Reconfiguration

Authors: Censor-Hillel, Keren ; Maus, Yannic ; Romem-Peled, Shahar ; Tonoyan, Tigran

Abstract | Document (937 KB) | BibTeX

Adversarially Robust Coloring for Graph Streams

Authors: Chakrabarti, Amit ; Ghosh, Prantar ; Stoeckl, Manuel

Abstract | Document (915 KB) | BibTeX

Smaller ACC0 Circuits for Symmetric Functions

Authors: Chapman, Brynmor ; Williams, R. Ryan

Abstract | Document (766 KB) | BibTeX

Monotone Complexity of Spanning Tree Polynomial Re-Visited

Authors: Chattopadhyay, Arkadev ; Datta, Rajit ; Ghosal, Utsab ; Mukhopadhyay, Partha

Abstract | Document (733 KB) | BibTeX

The Space Complexity of Sampling

Authors: Chattopadhyay, Eshan ; Goodman, Jesse ; Zuckerman, David

Abstract | Document (820 KB) | BibTeX

On the Existence of Competitive Equilibrium with Chores

Authors: Chaudhury, Bhaskar Ray ; Garg, Jugal ; McGlaughlin, Peter ; Mehta, Ruta

Abstract | Document (665 KB) | BibTeX

Individual Fairness in Advertising Auctions Through Inverse Proportionality

Authors: Chawla, Shuchi ; Jagadeesan, Meena

Abstract | Document (883 KB) | BibTeX

Improved Decoding of Expander Codes

Authors: Chen, Xue ; Cheng, Kuan ; Li, Xin ; Ouyang, Minghui

Abstract | Document (484 KB) | BibTeX

Cursed yet Satisfied Agents

Authors: Chen, Yiling ; Eden, Alon ; Wang, Juntao

Abstract | Document (332 KB) | BibTeX

Average-Case Hardness of NP and PH from Worst-Case Fine-Grained Assumptions

Authors: Chen, Lijie ; Hirahara, Shuichi ; Vafa, Neekon

Abstract | Document (811 KB) | BibTeX

Symmetric Sparse Boolean Matrix Factorization and Applications

Authors: Chen, Sitan ; Song, Zhao ; Tao, Runzhou ; Zhang, Ruizhe

Abstract | Document (918 KB) | BibTeX

Quantum Meets the Minimum Circuit Size Problem

Authors: Chia, Nai-Hui ; Chou, Chi-Ning ; Zhang, Jiayu ; Zhang, Ruizhe

Abstract | Document (682 KB) | BibTeX

Larger Corner-Free Sets from Combinatorial Degenerations

Authors: Christandl, Matthias ; Fawzi, Omar ; Ta, Hoang ; Zuiddam, Jeroen

Abstract | Document (764 KB) | BibTeX

Optimal Deterministic Clock Auctions and Beyond

Authors: Christodoulou, Giorgos ; Gkatzelis, Vasilis ; Schoepflin, Daniel

Abstract | Document (795 KB) | BibTeX

Nonlinear Repair Schemes of Reed-Solomon Codes.

Authors: Con, Roni ; Tamo, Itzhak

Abstract | Document (299 KB) | BibTeX

A Complete Linear Programming Hierarchy for Linear Codes

Authors: Coregliano, Leonardo Nagami ; Jeronimo, Fernando Granha ; Jones, Chris

Abstract | Document (805 KB) | BibTeX

Lower Bounds for Symmetric Circuits for the Determinant

Authors: Dawar, Anuj ; Wilsenach, Gregory

Abstract | Document (868 KB) | BibTeX

Convex Influences

Authors: De, Anindya ; Nadimpalli, Shivam ; Servedio, Rocco A.

Abstract | Document (804 KB) | BibTeX

The Importance of the Spectral Gap in Estimating Ground-State Energies

Authors: Deshpande, Abhinav ; Gorshkov, Alexey V. ; Fefferman, Bill

Abstract | Document (534 KB) | BibTeX

Mechanism Design with Moral Bidders

Authors: Dobzinski, Shahar ; Oren, Sigal

Abstract | Document (730 KB) | BibTeX

Small-Box Cryptography

Authors: Dodis, Yevgeniy ; Karthikeyan, Harish ; Wichs, Daniel

Abstract | Document (796 KB) | BibTeX

Interaction-Preserving Compilers for Secure Computation

Authors: Döttling, Nico ; Goyal, Vipul ; Malavolta, Giulio ; Raizes, Justin

Abstract | Document (675 KB) | BibTeX

Matroid Secretary Is Equivalent to Contention Resolution

Authors: Dughmi, Shaddin

Abstract | Document (867 KB) | BibTeX

Uniform Brackets, Containers, and Combinatorial Macbeath Regions

Authors: Dutta, Kunal ; Ghosh, Arijit ; Moran, Shay

Abstract | Document (642 KB) | BibTeX

Multiscale Entropic Regularization for MTS on General Metric Spaces

Authors: Ebrahimnejad, Farzam ; Lee, James R.

Abstract | Document (1,059 KB) | BibTeX

Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs

Authors: Ebrahimnejad, Farzam ; Nagda, Ansh ; Gharan, Shayan Oveis

Abstract | Document (549 KB) | BibTeX

Embeddings and Labeling Schemes for A*

Authors: Eden, Talya ; Indyk, Piotr ; Xu, Haike

Abstract | Document (742 KB) | BibTeX

A Unifying Framework for Characterizing and Computing Width Measures

Authors: Eiben, Eduard ; Ganian, Robert ; Hamm, Thekla ; Jaffke, Lars ; Kwon, O-joung

Abstract | Document (948 KB) | BibTeX

Reduction from Non-Unique Games to Boolean Unique Games

Authors: Eldan, Ronen ; Moshkovitz, Dana

Abstract | Document (874 KB) | BibTeX

Pseudorandom Self-Reductions for NP-Complete Problems

Authors: Elrazik, Reyad Abed ; Robere, Robert ; Schuster, Assaf ; Yehuda, Gal

Abstract | Document (681 KB) | BibTeX

Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for All Distributions

Authors: Essaidi, Meryem ; Ferreira, Matheus V. X. ; Weinberg, S. Matthew

Abstract | Document (730 KB) | BibTeX

Small Circuits Imply Efficient Arthur-Merlin Protocols

Authors: Ezra, Michael ; Rothblum, Ron D.

Abstract | Document (768 KB) | BibTeX

A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation

Authors: Fawzi, Omar ; Müller-Hermes, Alexander ; Shayeghi, Ala

Abstract | Document (739 KB) | BibTeX

On Semi-Algebraic Proofs and Algorithms

Authors: Fleming, Noah ; Göös, Mika ; Grosser, Stefan ; Robere, Robert

Abstract | Document (888 KB) | BibTeX

Extremely Deep Proofs

Authors: Fleming, Noah ; Pitassi, Toniann ; Robere, Robert

Abstract | Document (772 KB) | BibTeX

On the Download Rate of Homomorphic Secret Sharing

Authors: Fosli, Ingerid ; Ishai, Yuval ; Kolobov, Victor I. ; Wootters, Mary

Abstract | Document (834 KB) | BibTeX

A Variant of the VC-Dimension with Applications to Depth-3 Circuits

Authors: Frankl, Peter ; Gryaznov, Svyatoslav ; Talebanfard, Navid

Abstract | Document (761 KB) | BibTeX

Continuous Tasks and the Asynchronous Computability Theorem

Authors: Galeana, Hugo Rincon ; Rajsbaum, Sergio ; Schmid, Ulrich

Abstract | Document (834 KB) | BibTeX

Correlation Detection in Trees for Planted Graph Alignment

Authors: Ganassali, Luca ; Massoulié, Laurent ; Lelarge, Marc

Abstract | Document (735 KB) | BibTeX

On Polynomially Many Queries to NP or QMA Oracles

Authors: Gharibian, Sevag ; Rudolph, Dorian

Abstract | Document (1,220 KB) | BibTeX

Eliminating Intermediate Measurements Using Pseudorandom Generators

Authors: Girish, Uma ; Raz, Ran

Abstract | Document (729 KB) | BibTeX

Sample-Based Proofs of Proximity

Authors: Goldberg, Guy ; N. Rothblum, Guy

Abstract | Document (738 KB) | BibTeX

Testing Distributions of Huge Objects

Authors: Goldreich, Oded ; Ron, Dana

Abstract | Document (859 KB) | BibTeX

Omnipredictors

Authors: Gopalan, Parikshit ; Kalai, Adam Tauman ; Reingold, Omer ; Sharan, Vatsal ; Wieder, Udi

Abstract | Document (922 KB) | BibTeX

Mixing in Non-Quasirandom Groups

Authors: Gowers, W. T. ; Viola, Emanuele

Abstract | Document (549 KB) | BibTeX

Time-Traveling Simulators Using Blockchains and Their Applications

Authors: Goyal, Vipul ; Raizes, Justin ; Soni, Pratik

Abstract | Document (713 KB) | BibTeX

Online Multivalid Learning: Means, Moments, and Prediction Intervals

Authors: Gupta, Varun ; Jung, Christopher ; Noarov, Georgy ; Pai, Mallesh M. ; Roth, Aaron

Abstract | Document (787 KB) | BibTeX

Adaptive Massively Parallel Constant-Round Tree Contraction

Authors: Hajiaghayi, MohammadTaghi ; Knittel, Marina ; Saleh, Hamed ; Su, Hsin-Hao

Abstract | Document (1,288 KB) | BibTeX

Errorless Versus Error-Prone Average-Case Complexity

Authors: Hirahara, Shuichi ; Santhanam, Rahul

Abstract | Document (790 KB) | BibTeX

Excluding PH Pessiland

Authors: Hirahara, Shuichi ; Santhanam, Rahul

Abstract | Document (833 KB) | BibTeX

Nash-Bargaining-Based Models for Matching Markets: One-Sided and Two-Sided; Fisher and Arrow-Debreu

Authors: Hosseini, Mojtaba ; Vazirani, Vijay V.

Abstract | Document (904 KB) | BibTeX

Symbolic Determinant Identity Testing and Non-Commutative Ranks of Matrix Lie Algebras

Authors: Ivanyos, Gábor ; Mittal, Tushant ; Qiao, Youming

Abstract | Document (818 KB) | BibTeX

Explicit Abelian Lifts and Quantum LDPC Codes

Authors: Jeronimo, Fernando Granha ; Mittal, Tushant ; O'Donnell, Ryan ; Paredes, Pedro ; Tulsiani, Madhur

Abstract | Document (853 KB) | BibTeX

Almost-Orthogonal Bases for Inner Product Polynomials

Authors: Jones, Chris ; Potechin, Aaron

Abstract | Document (759 KB) | BibTeX

Sublinear-Time Computation in the Presence of Online Erasures

Authors: Kalemaj, Iden ; Raskhodnikova, Sofya ; Varma, Nithin

Abstract | Document (903 KB) | BibTeX

Noisy Boolean Hidden Matching with Applications

Authors: Kapralov, Michael ; Musipatla, Amulya ; Tardos, Jakab ; Woodruff, David P. ; Zhou, Samson

Abstract | Document (851 KB) | BibTeX

On Fairness and Stability in Two-Sided Matchings

Authors: Karni, Gili ; Rothblum, Guy N. ; Yona, Gal

Abstract | Document (662 KB) | BibTeX

Optimal Bounds for Dominating Set in Graph Streams

Authors: Khanna, Sanjeev ; Konrad, Christian

Abstract | Document (909 KB) | BibTeX

Deterministic Dynamic Matching in Worst-Case Update Time

Authors: Kiss, Peter

Abstract | Document (841 KB) | BibTeX

More Dominantly Truthful Multi-Task Peer Prediction with a Finite Number of Tasks

Authors: Kong, Yuqing

Abstract | Document (1,651 KB) | BibTeX

Dynamic Matching Algorithms Under Vertex Updates

Authors: Le, Hung ; Milenković, Lazar ; Solomon, Shay ; Vassilevska Williams, Virginia

Abstract | Document (1,021 KB) | BibTeX

Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems

Authors: Le Gall, François ; Seddighin, Saeed

Abstract | Document (763 KB) | BibTeX

Optimal Sub-Gaussian Mean Estimation in Very High Dimensions

Authors: Lee, Jasper C.H. ; Valiant, Paul

Abstract | Document (704 KB) | BibTeX

Double Coverage with Machine-Learned Advice

Authors: Lindermayr, Alexander ; Megow, Nicole ; Simon, Bertrand

Abstract | Document (836 KB) | BibTeX

Beating Classical Impossibility of Position Verification

Authors: Liu, Jiahui ; Liu, Qipeng ; Qian, Luowen

Abstract | Document (557 KB) | BibTeX

A Gaussian Fixed Point Random Walk

Authors: Liu, Yang P. ; Sah, Ashwin ; Sawhney, Mehtaab

Abstract | Document (700 KB) | BibTeX

Correlation-Intractable Hash Functions via Shift-Hiding

Authors: Lombardi, Alex ; Vaikuntanathan, Vinod

Abstract | Document (753 KB) | BibTeX

Balanced Allocations with Incomplete Information: The Power of Two Queries

Authors: Los, Dimitrios ; Sauerwald, Thomas

Abstract | Document (1,136 KB) | BibTeX

Lifting with Sunflowers

Authors: Lovett, Shachar ; Meka, Raghu ; Mertz, Ian ; Pitassi, Toniann ; Zhang, Jiapeng

Abstract | Document (966 KB) | BibTeX

Interactive Communication in Bilateral Trade

Authors: Mao, Jieming ; Paes Leme, Renato ; Wang, Kangning

Abstract | Document (738 KB) | BibTeX

Support Recovery in Universal One-Bit Compressed Sensing

Authors: Mazumdar, Arya ; Pal, Soumyabrata

Abstract | Document (866 KB) | BibTeX

Keep That Card in Mind: Card Guessing with Limited Memory

Authors: Menuhin, Boaz ; Naor, Moni

Abstract | Document (791 KB) | BibTeX

A Spectral Approach to Polytope Diameter

Authors: Narayanan, Hariharan ; Shah, Rikhav ; Srivastava, Nikhil

Abstract | Document (934 KB) | BibTeX

Geometric Bounds on the Fastest Mixing Markov Chain

Authors: Olesker-Taylor, Sam ; Zanetti, Luca

Abstract | Document (359 KB) | BibTeX

Lower Bounds on Stabilizer Rank

Authors: Peleg, Shir ; Volk, Ben Lee ; Shpilka, Amir

Abstract | Document (547 KB) | BibTeX

Beating the Folklore Algorithm for Dynamic Matching

Authors: Roghani, Mohammad ; Saberi, Amin ; Wajc, David

Abstract | Document (833 KB) | BibTeX

Interactive Proofs for Synthesizing Quantum States and Unitaries

Authors: Rosenthal, Gregory ; Yuen, Henry

Abstract | Document (560 KB) | BibTeX

Budget-Smoothed Analysis for Submodular Maximization

Authors: Rubinstein, Aviad ; Zhao, Junyao

Abstract | Document (870 KB) | BibTeX

Uniform Bounds for Scheduling with Job Size Estimates

Authors: Scully, Ziv ; Grosof, Isaac ; Mitzenmacher, Michael

Abstract | Document (906 KB) | BibTeX

3+ε Approximation of Tree Edit Distance in Truly Subquadratic Time

Authors: Seddighin, Masoud ; Seddighin, Saeed

Abstract | Document (1,012 KB) | BibTeX

On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization

Authors: Shaltiel, Ronen ; Viola, Emanuele

Abstract | Document (821 KB) | BibTeX

Low-Bandwidth Recovery of Linear Functions of Reed-Solomon-Encoded Data

Authors: Shutty, Noah ; Wootters, Mary

Abstract | Document (785 KB) | BibTeX

Efficient Reconstruction of Depth Three Arithmetic Circuits with Top Fan-In Two

Authors: Sinha, Gaurav

Abstract | Document (1,020 KB) | BibTeX

Polynomial Identity Testing via Evaluation of Rational Functions

Authors: van Melkebeek, Dieter ; Morgan, Andrew

Abstract | Document (692 KB) | BibTeX

Probing to Minimize

Authors: Wang, Weina ; Gupta, Anupam ; Williams, Jalani K.

Abstract | Document (1,052 KB) | BibTeX

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

13th Innovations in Theoretical Computer Science Conference (ITCS 2022)