Dimitris Achlioptas
- 1.D. Achlioptas, L. M. Kirousis, E. Kranakis, and D. Krizanc. Rigorous results for random (2 +p)-SAT. In Proceedings of RALCOM 97 (Santorini, Greece), pages 1-13, 1997. Submitted to Theoret. Comput. Sci.Google Scholar
- 2.P. Beame and T. Pitassi. Propositional proof complexity: past, present, and future. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, (65):66-89, 1998.Google Scholar
- 3.B. Bollobfis, C. Borgs, J. Chayes, J. H. Kim, and D. B. Wilson. The scaling window of the 2-SAT transition. Manuscript, 1999.Google Scholar
- 4.A. Z. Broder, A. M. Frieze, and E. Upfal. On the satisfiability and maximum satisfiability of random 3-CNF formulas. In dth Annual A CM-SIAM Symposium on Discrete Algorithms (Austin, TX, 1993), pages 322- 330. ACM, New York, 1993. Google ScholarDigital Library
- 5.M.-T. Chao and J. Franco. Probabilistic analysis of two heuristics for the 3-satisfiability problem. SIAM J. Comput., 15(4):1106-1118, 1986. Google ScholarDigital Library
- 6.V. Chv~tal and B. Reed. Mick gets some (the odds are on his side). In 33th Annual Symposium on Foundations o/Computer Science (Pittsburgh, PA, 199~), pages 620-627. iEEE Comput. Soc. Press, Los Alamitos, CA, 1992.Google ScholarDigital Library
- 7.V. Chv,4tal and E. Szemer~di. Many hard examples for resolution. J. Assoc. Comput. Mach., 35(4):759-768, 1988. Google ScholarDigital Library
- 8.S. A. Cook. The complexity of theorem-proving procedures. In 3rd Annual A CM Symposium on Theory of Computing (Shaker Heights, OH, 1971), pages 151-158. ACM, New York, 1971. Google ScholarDigital Library
- 9.S. A. Cook and D. G. Mitchell. Finding hard instances of the satisfiability problem: a survey. In Satisfiability problem: theory and applications (Piscataway, N J, 1996), pages 1-17. Amer. Math. Soc., Providence, RI, 1997.Google Scholar
- 10.M. Davis, G. Logemann, and D. Loveland. A machine program for theorem-proving. Comm. A CM, 5:394-397, 1962. Google ScholarDigital Library
- 11.M. Davis and H. Putnam. A computing procedure for quantification theory. J. Assoc. Comput. Mach., 7:201- 215, 1960. Google ScholarDigital Library
- 12.O. Dubois and Y. Boufkhaxt. A general upper bound for the satisfiability threshold of random r-SAT formulae. J. Algorithms, 24(2):395-420, 1997. Google ScholarDigital Library
- 13.O. Dubois, Y. Boufkhad, and J. Mandler. Typical random 3-SAT formulae and the satisfiability threshold. In 11th Annual ACM-$IAM Symposium on Discrete Algorithms (San Francisco, CA, 2000), pages 126-127. ACM, New York, 2000. Google ScholarDigital Library
- 14.A. El Maftouhi and W. Fernandez de la Vega. On random 3-SAT. Combin. Probab. Comput., 4(3):189-195, 1995.Google ScholarCross Ref
- 15.W. Fernandez de la Vega. On random 2-SAT. 1992. Manuscript.Google Scholar
- 16.J. Franco. Probabilistic analysis of the pure literal heuristic for the satisfiability problem. Ann. Oper. Res., 1:273-289, 1984.Google ScholarCross Ref
- 17.J. Franco and M. Paul1. Probabilistic analysis of the Davis-Putnam procedure for solving the satisftability problem. Discrete Appl. Math., 5(1):77-87, 1983.Google ScholarCross Ref
- 18.E. Friedgut. Necessary and sufficient conditions for sharp thresholds of graph properties, and the k-SAT problem. J. Amer. Math. Soc., 12:1017-1054, 1999.Google ScholarCross Ref
- 19.A. M. Frieze and S. Suen. Analysis of two simple heuristics on a random instance of k-SAT. J. Algorithms, 20(2):312-355, 1996. Google ScholarDigital Library
- 20.A. Goerdt. A threshold for unsatisfiability. J. Comput. System Sci., 53(3):469-486, 1996. Google ScholarDigital Library
- 21.A. Goldberg. On the complexity of the satisfiability problem. In jth Workshop on Automated Deduction (Austin, TX, 1979), pages 1-6, 1979.Google Scholar
- 22.A. Haken. The intractability of resolution. Theoret. Comput. Sci., 39(2-3):297-308, 1985.Google ScholarCross Ref
- 23.S. Janson, Y. C. Stamatiou, and M. Vamwakari. Bounding the unsatisfiability threshold of random 3-SAT. 1999. Submitted.Google Scholar
- 24.A. Kamath, R. Motwani, K. Palem, and P. Spirakis. Tail bounds for occupancy and the satisfiability threshold conjecture. Random Structures Algorithms, 7(1):59- 80, 1995. Google ScholarDigital Library
- 25.R. Karp and M. Sipser. Maximum matchings in sparse random graphs. In 2~nd Annual Symposium on Foundations of Computer Science, pages 364-375. IEEE Cornput. Soc. Press, Los Alamitos, CA, 1981.Google Scholar
- 26.L. M. Kirousis, E. Kranakis, D. Krizanc, and Y. Sta~ matiou. Approximating the unsatisfiability threshold of random formulas. Random Structures Algorithms, !2(3):253-269, 1998. Google ScholarDigital Library
- 27.T. G. Kurtz. Solutions of ordinary differential equations as limits of pure jump Markov processes. J. Appl. Probability, 7:49-58, 1970.Google ScholarCross Ref
- 28.T. G. Kurtz. Approximation of population processes. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1981.Google Scholar
- 29.A. W. Marshall and I. Olkin. Inequalities: theory of majorization and its applications. Academic Press Inc. {Harcourt Brace Jovanovich Publishers}, New York, 1979.Google Scholar
- 30.R. Monasson and R. Zecchina. Entropy of the K- satisfiability problem. Phys. Rev. Left., 76(21):3881- 3885, 1996.Google ScholarCross Ref
- 31.R. Monasson and R. Zecchina. Statistical mechanics of the random K-satisfiability model. Phys. Rev. E (3), 56(2):1357-1370, 1997.Google ScholarCross Ref
- 32.R. Monasson and R. Zecchina. Tricritical points in random combinatorics: the (2 + p)-SAT case. J. Phys. A, 1998. submitted.Google ScholarCross Ref
- 33.R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky. Phase transition and search cost in the (2 + p)-SAT problem. In Jth Workshop on Physics and Computation, (Boston, MA, 1996).Google Scholar
- 34.R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyansky. Determining computational complexity from characteristic phase transitions. Nature, 400:133-137, 1999.Google ScholarCross Ref
- 35.N. Nedialkov. Computing Rigorous Bounds on the Solution of an Initial Value Problem for an Ordinary Differential Equation. Ph.D. Thesis, University of Toronto, 1999. Google ScholarDigital Library
- 36.D. Redfern. The Maple Handbook: Maple V Release 3. Springer Verlag, New York, third edition, 1994. Google ScholarDigital Library
- 37.B. Selman, D. G. Mitchell, and H. J. Levesque. Generating hard satisfiability problems. Artificial Intelligence, 81(1-2):17-29, 1996. Google ScholarDigital Library
- 38.N. C. Wormald. Differential equations for random processes and random graphs. Ann. Appl. Probab., 5(4):1217-1235, 1995.Google ScholarCross Ref
Index Terms
- Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
Recommendations
Solving MAX-r-SAT above a tight lower bound
SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithmsWe present an exact algorithm that decides, for every fixed r ≥ 2 in time O(m) + 2O(k2) whether a given set of m clauses of size r admits a truth assignment that satisfies at least ((2r - 1)m + k)/2r clauses. Thus Max-r-Sat is fixed-parameter tractable ...
2-Local Random Reductions to 3-Valued Functions
Yao (in a lecture at DIMACS Workshop on structural complexity and cryptography, 1990) showed that if a language L is 2-locally random reducible to a Boolean function, then L ∈ PSPACE/poly. Fortnow & Szegedy quantitatively improved Yao’s result to show ...
Almost 2-SAT Is Fixed-Parameter Tractable (Extended Abstract)
ICALP '08: Proceedings of the 35th international colloquium on Automata, Languages and Programming - Volume Part IWe consider the following problem. Given a <Emphasis Type="SmallCaps">2-cnf</Emphasis>formula, is it possible to remove at most kclauses so that the resulting <Emphasis Type="SmallCaps">2-cnf</Emphasis>formula is satisfiable? This problem is known to ...
Comments