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