The asymptotic k-SAT threshold

DOI10.1145/2591796.2591822zbMath1315.68146OpenAlexW2963572639MaRDI QIDQ5259616

Amin Coja-Oghlan

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2591796.2591822

zbMATH Keywords

phase transitionsrandom structuressecond moment methodsurvey propagation\(k\)-SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (17)

Average-case complexity without the black swans ⋮ Random subcube intersection graphs. I: Cliques and covering ⋮ Random Instances of Problems in NP – Algorithms and Statistical Physics ⋮ Biased random k‐SAT ⋮ The asymptotic \(k\)-SAT threshold ⋮ CHAMP: a multipass algorithm for Max Sat based on saver variables ⋮ Go-MOCE: greedy order method of conditional expectations for Max Sat ⋮ Network models: structure and function. Abstracts from the workshop held December 10--16, 2017 ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Optimal testing for planted satisfiability problems ⋮ Unnamed Item ⋮ Generalised and quotient models for random and/or~trees and application to satisfiability ⋮ Satisfiability threshold for random regular \textsc{nae-sat} ⋮ Probabilistic characterization of random Max \(r\)-Sat ⋮ The Normalized Autocorrelation Length of Random Max  $$r$$ -Sat Converges in Probability to $$(1-1/2^r)/r$$ ⋮ Speed and concentration of the covering time for structured coupon collectors ⋮ Using the method of conditional expectations to supply an improved starting point for CCLS

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for privately releasing marginals via convex relaxations
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Faster Algorithms for Privately Releasing Marginals
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Characterizing the sample complexity of private learners
• Faster private release of marginals on small databases
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Advances in Cryptology – CRYPTO 2004
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography

This page was built for publication: The asymptotic k-SAT threshold