Complexity theory. Abstracts from the workshop held June 2--7, 2024

DOI10.4171/owr/2024/27MaRDI QIDQ6671624FDOQ6671624

Authors:

Publication date: 27 January 2025

Published in: Oberwolfach Reports (Search for Journal in Brave)

Recommendations

Complexity theory. Abstracts from the workshop held November 11--17, 2018
Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
Complexity theory. Abstracts from the workshop held November 15--21, 2015
Complexity theory. Abstracts from the workshop held November 11--17, 2012.
Complexity theory. Abstracts from the workshop held November 15th -- November 21st, 2009

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Proceedings of conferences of miscellaneous specific interest (00B25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Collections of abstracts of lectures (00B05) General topics in the theory of computing (68Q01)

Cites Work

Fairness through awareness
A probabilistic remark on algebraic program testing
Hardness vs randomness
Title not available (Why is that?)
Fast Probabilistic Algorithms for Verification of Polynomial Identities
Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
The complexity of satisfiability problems
Some optimal inapproximability results
Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
Counting independent sets up to the tree threshold
Derandomized constructions of \(k\)-wise (almost) independent permutations
Many hard examples for resolution
Arithmetic circuits: a chasm at depth 3
Hardness-randomness tradeoffs for bounded depth arithmetic circuits
FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
Derandomizing polynomial identity tests means proving circuit lower bounds
Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
Thresholds and Expectation Thresholds
Random-Self-Reducibility of Complete Sets
How to use indistinguishability obfuscation
Characterizing pseudoentropy and simplifying pseudorandom generator constructions
On Worst‐Case to Average‐Case Reductions for NP Problems
Counting in two-spin models on \(d\)-regular graphs
Are many small sets explicitly small?
Randomness efficient identity testing of multivariate polynomials
Blackbox identity testing for bounded top-fanin depth-3 circuits: the field doesn't matter
Local random quantum circuits are approximate polynomial-designs
Optimal mixing of Glauber dynamics: entropy factorization via high-dimensional expansion
Simple permutations mix well
Simple permutations mix even better
Non-malleable extractors and symmetric key cryptography from weak secrets
Symmetric groups and expander graphs.
On the Complexity of Learning Minimum Time-Bounded Turing Machines
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Title not available (Why is that?)
Derandomization from Algebraic Hardness
A spectral condition for spectral gap: fast mixing in high-temperature Ising models
Modified log-Sobolev inequalities for strongly log-concave distributions
Closure results for polynomial factorization
Improved non-malleable extractors, non-malleable codes and independent source extractors
Strongly refuting random CSPs below the spectral threshold
Sum of squares lower bounds for refuting any CSP
Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs
Local spectral expansion approach to high dimensional expanders. I: Descent of spectral gaps
A proof of the CSP dichotomy conjecture
Thresholds versus fractional expectation-thresholds
High order random walks: beyond spectral gap
Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
Explicit two-source extractors and resilient functions
Towards blackbox identity testing of log-variate circuits
Geometric complexity theory. V: Efficient algorithms for Noether normalization
Improved bounds for the sunflower lemma
Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
Improved analysis of higher order random walks and applications
Tame automorphism groups of polynomial rings with property (T) and infinitely many alternating group quotients
An Almost m-wise Independent Random Permutation of the Cube
Title not available (Why is that?)
Entropic independence: optimal mixing of down-up random walks
An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy
Introduction to Semirandom Models
Average-case hardness of NP from exponential worst-case hardness assumptions
Über höhere Kongruenzen.
Fractionally log-concave and sector-stable polynomials: counting planar matchings and more
A proof of the Kahn–Kalai conjecture
Algorithms and certificates for Boolean CSP refutation: smoothed is no harder than random
On approximability of satisfiable k -CSPs: I
Log-concave polynomials IV: approximate exchange, tight mixing times, and near-optimal sampling of forests
Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
Title not available (Why is that?)
Title not available (Why is that?)
Rapid mixing from spectral independence beyond the Boolean domain
A Near-Linear Time Sampler for the Ising Model with External Field
A simple and sharper proof of the hypergraph Moore bound
A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation
On approximability of satisfiable k-CSPs. II
On approximability of satisfiable k-CSPs. III
From algorithms to connectivity and back: finding a giant component in random \(k\)-SAT
Fast sampling of \(b\)-matchings and \(b\)-edge covers
Universality of spectral independence with applications to fast mixing in spin glasses

This page was built for publication: Complexity theory. Abstracts from the workshop held June 2--7, 2024

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6671624)