CCC 2022 July 20-23, 2022, Philadelphia, PA, USA

37th Computational Complexity Conference (CCC 2022)



Shachar Lovett (Ed.)
ISBN 978-3-95977-241-9, LIPICS Vol. 234 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 14 MB)
Search Publication Server

Authors
  • Aaronson, Scott
  • Aggarwal, Amol
  • Alman, Josh
  • Arnon, Gal
  • Arvind, Vikraman
  • Bansal, Nikhil
  • Beniamini, Gal
  • Bhandari, Siddharth
  • Blanc, Guy
  • Bogdanov, Andrej
  • Bordage, Sarah
  • Chen, Lijie
  • Chiesa, Alessandro
  • Cook, James
  • Derksen, Harm
  • de Wolf, Ronald
  • Doron, Dean
  • Goldberg, Halley
  • Golowich, Louis
  • Göös, Mika
  • Gryaznov, Svyatoslav
  • Guruswami, Venkatesan
  • Harsha, Prahladh
  • Hirahara, Shuichi
  • Hollender, Alexandros
  • Hoza, William M.
  • Hsieh, Jun-Ting
  • Ingram, DeVon
  • Irani, Sandy
  • Jain, Siddhartha
  • Joglekar, Pushkar S.
  • Kabanets, Valentine
  • Karliner, Dan
  • Karthik C. S.
  • Kelley, Zander
  • Khaniki, Erfan
  • Khot, Subhash
  • Korten, Oliver
  • Kretschmer, William
  • Kush, Deepanshu
  • Lecomte, Victor
  • Lhotel, Mathieu
  • Li, Jiatu
  • Limaye, Nutan
  • Liu, Yanyi
  • Lovett, Shachar
  • Lu, Zhenjian
  • Lyu, Xin
  • Makam, Visu
  • Manohar, Peter
  • Maystre, Gilbert
  • Meka, Raghu
  • Mertz, Ian
  • Mihajlin, Ivan
  • Mohanty, Sidhanth
  • Mosheiff, Jonathan
  • Nanashima, Mikito
  • Nardi, Jade
  • Natarajan, Anand
  • Nirkhe, Chinmay
  • O'Donnell, Ryan
  • Oliveira, Igor C.
  • Pass, Rafael
  • Pires, William
  • Prakriya, Gautam
  • Pratt, Kevin
  • Pudlák, Pavel
  • Pyne, Edward
  • Ramakrishnan, Prasanna
  • Randriam, Hugues
  • Rao, Sujit
  • Robere, Robert
  • Saks, Michael
  • Salama, Roie
  • Santhanam, Rahul
  • Saptharishi, Ramprasad
  • Saraf, Shubhangi
  • Sinha, Makrand
  • Sofronova, Anastasia
  • Sokolov, Dmitry
  • Srinivasan, Srikanth
  • Talebanfard, Navid
  • Tan, Li-Yang
  • Tantau, Till
  • Tao, Ran
  • Ta-Shma, Amnon
  • Tavenas, Sébastien
  • Vadhan, Salil
  • Xu, Jeff
  • Yang, Tianqi
  • Yogev, Eylon
  • Yuen, Henry
  • Zuiddam, Jeroen
    		•

    		  
    Front Matter, Table of Contents, Preface, Conference Organization
    Authors: Lovett, Shachar

    Abstract | Document (565 KB) | BibTeX

    The Approximate Degree of Bipartite Perfect Matching
    Authors: Beniamini, Gal

    Abstract | Document (1,440 KB) | BibTeX

    On the Satisfaction Probability of k-CNF Formulas
    Authors: Tantau, Till

    Abstract | Document (909 KB) | BibTeX

    Hitting Sets for Regular Branching Programs
    Authors: Bogdanov, Andrej ; Hoza, William M. ; Prakriya, Gautam ; Pyne, Edward

    Abstract | Document (878 KB) | BibTeX

    Linear Branching Programs and Directional Affine Extractors
    Authors: Gryaznov, Svyatoslav ; Pudlák, Pavel ; Talebanfard, Navid

    Abstract | Document (795 KB) | BibTeX

    Quantum Search-To-Decision Reductions and the State Synthesis Problem
    Authors: Irani, Sandy ; Natarajan, Anand ; Nirkhe, Chinmay ; Rao, Sujit ; Yuen, Henry

    Abstract | Document (910 KB) | BibTeX

    Almost Polynomial Factor Inapproximability for Parameterized k-Clique
    Authors: Karthik C. S. ; Khot, Subhash

    Abstract | Document (892 KB) | BibTeX

    ?_p-Spread and Restricted Isometry Properties of Sparse Random Matrices
    Authors: Guruswami, Venkatesan ; Manohar, Peter ; Mosheiff, Jonathan

    Abstract | Document (737 KB) | BibTeX

    Trading Time and Space in Catalytic Branching Programs
    Authors: Cook, James ; Mertz, Ian

    Abstract | Document (786 KB) | BibTeX

    Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors
    Authors: Derksen, Harm ; Makam, Visu ; Zuiddam, Jeroen

    Abstract | Document (765 KB) | BibTeX

    New Near-Linear Time Decodable Codes Closer to the GV Bound
    Authors: Blanc, Guy ; Doron, Dean

    Abstract | Document (1,084 KB) | BibTeX

    Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance
    Authors: Hsieh, Jun-Ting ; Mohanty, Sidhanth ; Xu, Jeff

    Abstract | Document (846 KB) | BibTeX

    On Efficient Noncommutative Polynomial Factorization via Higman Linearization
    Authors: Arvind, Vikraman ; Joglekar, Pushkar S.

    Abstract | Document (864 KB) | BibTeX

    A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates
    Authors: Mihajlin, Ivan ; Sofronova, Anastasia

    Abstract | Document (710 KB) | BibTeX

    The Plane Test Is a Local Tester for Multiplicity Codes
    Authors: Karliner, Dan ; Salama, Roie ; Ta-Shma, Amnon

    Abstract | Document (957 KB) | BibTeX

    Pseudorandom Generators, Resolution and Heavy Width
    Authors: Sokolov, Dmitry

    Abstract | Document (880 KB) | BibTeX

    Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity
    Authors: Goldberg, Halley ; Kabanets, Valentine ; Lu, Zhenjian ; Oliveira, Igor C.

    Abstract | Document (1,269 KB) | BibTeX

    Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds
    Authors: Khaniki, Erfan

    Abstract | Document (812 KB) | BibTeX

    High-Dimensional Expanders from Chevalley Groups
    Authors: O'Donnell, Ryan ; Pratt, Kevin

    Abstract | Document (923 KB) | BibTeX

    The Composition Complexity of Majority
    Authors: Lecomte, Victor ; Ramakrishnan, Prasanna ; Tan, Li-Yang

    Abstract | Document (905 KB) | BibTeX

    The Acrobatics of BQP
    Authors: Aaronson, Scott ; Ingram, DeVon ; Kretschmer, William

    Abstract | Document (823 KB) | BibTeX

    Random Restrictions and PRGs for PTFs in Gaussian Space
    Authors: Kelley, Zander ; Meka, Raghu

    Abstract | Document (759 KB) | BibTeX

    Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation
    Authors: Aggarwal, Amol ; Alman, Josh

    Abstract | Document (797 KB) | BibTeX

    Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs
    Authors: Chen, Lijie ; Li, Jiatu ; Yang, Tianqi

    Abstract | Document (1,221 KB) | BibTeX

    Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs
    Authors: Arnon, Gal ; Chiesa, Alessandro ; Yogev, Eylon

    Abstract | Document (721 KB) | BibTeX

    Finding Errorless Pessiland in Error-Prone Heuristica
    Authors: Hirahara, Shuichi ; Nanashima, Mikito

    Abstract | Document (907 KB) | BibTeX

    Symmetry of Information from Meta-Complexity
    Authors: Hirahara, Shuichi

    Abstract | Document (1,062 KB) | BibTeX

    Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs
    Authors: Golowich, Louis ; Vadhan, Salil

    Abstract | Document (686 KB) | BibTeX

    Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms
    Authors: Bansal, Nikhil ; Sinha, Makrand ; de Wolf, Ronald

    Abstract | Document (1,365 KB) | BibTeX

    On Randomized Reductions to the Random Strings
    Authors: Saks, Michael ; Santhanam, Rahul

    Abstract | Document (917 KB) | BibTeX

    Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes
    Authors: Bordage, Sarah ; Lhotel, Mathieu ; Nardi, Jade ; Randriam, Hugues

    Abstract | Document (1,143 KB) | BibTeX

    Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes
    Authors: Bhandari, Siddharth ; Harsha, Prahladh ; Saptharishi, Ramprasad ; Srinivasan, Srikanth

    Abstract | Document (752 KB) | BibTeX

    On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials
    Authors: Limaye, Nutan ; Srinivasan, Srikanth ; Tavenas, Sébastien

    Abstract | Document (776 KB) | BibTeX

    Further Collapses in TFNP
    Authors: Göös, Mika ; Hollender, Alexandros ; Jain, Siddhartha ; Maystre, Gilbert ; Pires, William ; Robere, Robert ; Tao, Ran

    Abstract | Document (780 KB) | BibTeX

    Improved Pseudorandom Generators for AC⁰ Circuits
    Authors: Lyu, Xin

    Abstract | Document (904 KB) | BibTeX

    Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity
    Authors: Liu, Yanyi ; Pass, Rafael

    Abstract | Document (763 KB) | BibTeX

    On One-Way Functions from NP-Complete Problems
    Authors: Liu, Yanyi ; Pass, Rafael

    Abstract | Document (1,043 KB) | BibTeX

    Derandomization from Time-Space Tradeoffs
    Authors: Korten, Oliver

    Abstract | Document (1,138 KB) | BibTeX

    Improved Low-Depth Set-Multilinear Circuit Lower Bounds
    Authors: Kush, Deepanshu ; Saraf, Shubhangi

    Abstract | Document (695 KB) | BibTeX

    		  



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