default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID37th CCC 2022: Philadelphia, PA, USA
- Shachar Lovett
:
37th Computational Complexity Conference, CCC 2022, July 20-23, 2022, Philadelphia, PA, USA. LIPIcs 234, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022, ISBN 978-3-95977-241-9 - Front Matter, Table of Contents, Preface, Conference Organization. 0:1-0:16
- Gal Beniamini:
The Approximate Degree of Bipartite Perfect Matching. 1:1-1:26 - Till Tantau:
On the Satisfaction Probability of k-CNF Formulas. 2:1-2:27 - Andrej Bogdanov, William M. Hoza, Gautam Prakriya, Edward Pyne:
Hitting Sets for Regular Branching Programs. 3:1-3:22 - Svyatoslav Gryaznov, Pavel Pudlák, Navid Talebanfard:
Linear Branching Programs and Directional Affine Extractors. 4:1-4:16 - Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, Henry Yuen:
Quantum Search-To-Decision Reductions and the State Synthesis Problem. 5:1-5:19 - Karthik C. S., Subhash Khot:
Almost Polynomial Factor Inapproximability for Parameterized k-Clique. 6:1-6:21 - Venkatesan Guruswami, Peter Manohar, Jonathan Mosheiff:
ℓp-Spread and Restricted Isometry Properties of Sparse Random Matrices. 7:1-7:17 - James Cook, Ian Mertz:
Trading Time and Space in Catalytic Branching Programs. 8:1-8:21 - Harm Derksen, Visu Makam, Jeroen Zuiddam:
Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors. 9:1-9:23 - Guy Blanc, Dean Doron:
New Near-Linear Time Decodable Codes Closer to the GV Bound. 10:1-10:40 - Jun-Ting Hsieh, Sidhanth Mohanty, Jeff Xu:
Certifying Solution Geometry in Random CSPs: Counts, Clusters and Balance. 11:1-11:18 - Vikraman Arvind, Pushkar S. Joglekar:
On Efficient Noncommutative Polynomial Factorization via Higman Linearization. 12:1-12:22 - Ivan Mihajlin, Anastasia Sofronova:
A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates. 13:1-13:15 - Dan Karliner, Roie Salama, Amnon Ta-Shma:
The Plane Test Is a Local Tester for Multiplicity Codes. 14:1-14:33 - Dmitry Sokolov:
Pseudorandom Generators, Resolution and Heavy Width. 15:1-15:22 - Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira:
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. 16:1-16:60 - Erfan Khaniki:
Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds. 17:1-17:15 - Ryan O'Donnell, Kevin Pratt:
High-Dimensional Expanders from Chevalley Groups. 18:1-18:26 - Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan:
The Composition Complexity of Majority. 19:1-19:26 - Scott Aaronson, DeVon Ingram, William Kretschmer:
The Acrobatics of BQP. 20:1-20:17 - Zander Kelley, Raghu Meka:
Random Restrictions and PRGs for PTFs in Gaussian Space. 21:1-21:24 - Amol Aggarwal, Josh Alman:
Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation. 22:1-22:23 - Lijie Chen, Jiatu Li, Tianqi Yang:
Extremely Efficient Constructions of Hash Functions, with Applications to Hardness Magnification and PRFs. 23:1-23:37 - Gal Arnon, Alessandro Chiesa, Eylon Yogev:
Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs. 24:1-24:16 - Shuichi Hirahara, Mikito Nanashima:
Finding Errorless Pessiland in Error-Prone Heuristica. 25:1-25:28 - Shuichi Hirahara:
Symmetry of Information from Meta-Complexity. 26:1-26:41 - Louis Golowich, Salil P. Vadhan:
Pseudorandomness of Expander Random Walks for Symmetric Functions and Permutation Branching Programs. 27:1-27:13 - Nikhil Bansal, Makrand Sinha, Ronald de Wolf:
Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms. 28:1-28:21 - Michael E. Saks, Rahul Santhanam:
On Randomized Reductions to the Random Strings. 29:1-29:30 - Sarah Bordage, Mathieu Lhotel, Jade Nardi, Hugues Randriam:
Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes. 30:1-30:45 - Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan:
Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes. 31:1-31:14 - Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas:
On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. 32:1-32:23 - Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, Ran Tao:
Further Collapses in TFNP. 33:1-33:15 - Xin Lyu:
Improved Pseudorandom Generators for AC⁰ Circuits. 34:1-34:25 - Yanyi Liu, Rafael Pass:
Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity. 35:1-35:17 - Yanyi Liu, Rafael Pass:
On One-Way Functions from NP-Complete Problems. 36:1-36:24 - Oliver Korten:
Derandomization from Time-Space Tradeoffs. 37:1-37:26 - Deepanshu Kush, Shubhangi Saraf:
Improved Low-Depth Set-Multilinear Circuit Lower Bounds. 38:1-38:16
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-21 20:34 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
