More Web Proxy on the site http://driver.im/

research-article

Clique is hard on average for regular resolution

Authors:

Albert Atserias,

Ilario Bonacina,

Susanna F. de Rezende,

Massimo Lauria,

Jakob Nordström,

Alexander RazborovAuthors Info & Claims

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Pages 866 - 877

https://doi.org/10.1145/3188745.3188856

Published: 20 June 2018 Publication History

Abstract

We prove that for k ≪ n^1/4 regular resolution requires length n^Ω(k) to establish that an Erdos-Renyi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional n^Ω(k) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.

Supplementary Material

MP4 File (6b-2.mp4)

Download
29.98 MB

References

[1]

Noga Alon, Michael Krivelevich, and Benny Sudakov. 1998.

[2]

Finding a large hidden clique in a random graph. Random Structures and Algorithms 13, 3-4 (1998), 457–466.

Digital Library

[3]

Roberto J. Bayardo Jr. and Robert Schrag. 1997. Using CSP Look-Back Techniques to Solve Real-World SAT Instances. In Proceedings of the 14th National Conference on Artificial Intelligence (AAAI ’97). 203–208.

Digital Library

[4]

Paul Beame, Russell Impagliazzo, and Ashish Sabharwal. 2007. The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. Computational Complexity 16, 3 (Oct. 2007), 245–297. Preliminary version in CCC ’01.

Digital Library

[5]

Paul Beame and Toniann Pitassi. 1996. Simplified and Improved Resolution Lower Bounds. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’96). 274–282.

Digital Library

[6]

Eli Ben-Sasson and Avi Wigderson. 2001. Short Proofs are Narrow—Resolution Made Simple. J. ACM 48, 2 (March 2001), 149–169. Preliminary version in STOC ’99.

Digital Library

[7]

Olaf Beyersdorff, Nicola Galesi, and Massimo Lauria. 2013. Parameterized Complexity of DPLL Search Procedures. ACM Transactions on Computational Logic 14, 3, Article 20 (Aug. 2013), 21 pages. Preliminary version in SAT ’11.

Digital Library

[8]

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, and Alexander A. Razborov. 2012. Parameterized Bounded-Depth Frege Is not Optimal. ACM Transactions on Computation Theory 4, 3 (Sept. 2012), 7:1–7:16. Preliminary version in ICALP ’11.

Digital Library

[9]

Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, and Ge Xia. 2004. Linear FPT reductions and computational lower bounds. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC ’04). 212–221.

Digital Library

[10]

Stephen A. Cook and Robert Reckhow. 1979. The relative efficiency of propositional proof systems. Journal of Symbolic Logic 44, 1 (March 1979), 36–50.

[11]

Stefan S. Dantchev, Barnaby Martin, and Stefan Szeider. 2011.

[12]

Parameterized Proof Complexity. Computational Complexity 20 (March 2011), 51–85. Issue 1. Preliminary version in FOCS ’07.

[13]

Rodney Downey and Michael R. Fellows. 1995.

[14]

Fixed-Parameter Tractability and Completeness II: Completeness for W{1}. Theoretical Computer Science A 141 (1995), 109–131. Preliminary versions of some of the results of this paper were presented at the 21st Manitoba Conference on Numerical Mathematics and Computation, 1991.

Digital Library

[15]

Armin Haken. 1985.

[16]

The Intractability of Resolution. Theoretical Computer Science 39, 2-3 (Aug. 1985), 297–308.

[17]

Johan Håstad. 1999. Clique is Hard to Approximate within n 1 − ϵ. Acta Mathematica 182 (1999), 105–142. Preliminary version in FOCS ’96.

[18]

Russell Impagliazzo and Ramamohan Paturi. 2001. On the Complexity of k-SAT. J. Comput. System Sci. 62, 2 (March 2001), 367–375. Preliminary version in CCC ’99.

Digital Library

[19]

Richard M. Karp. 1972. Reducibility among Combinatorial Problems. In Complexity of Computer Computations. Springer, 85–103.

[20]

Richard M. Karp. 1976. The probabilistic analysis of some combinatorial search algorithms. In Algorithms and Complexity: New Directions and Recent Results. Academic Press, New York, 1–19.

[21]

Donald E. Knuth. 1994. The sandwich theorem. The Electronic Journal of Combinatorics 1, A1 (1994), 1–48. STOC’18, June 25–29, 2018, Los Angeles, CA, USA A. Atserias, I. Bonacina, S. de Rezende, M. Lauria, J. Nordström, and A. Razborov

[22]

Jan Krajíček. 1997. Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic. Journal of Symbolic Logic 62, 2 (June 1997), 457–486.

[23]

Jan Krajíček. 1995.

[24]

Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press, New York.

Digital Library

[25]

Luděk Kučera. 1995. Expected complexity of graph partitioning problems. Discrete Applied Mathematics 57, 2 (1995), 193–212.

Digital Library

[26]

Massimo Lauria, Pavel Pudlák, Vojtěch Rödl, and Neil Thapen. 2017. The Complexity of Proving That a Graph is Ramsey. Combinatorica 37, 2 (April 2017), 253–268. Preliminary version in ICALP ’13.

Digital Library

[27]

László Lovász. 1979. On the Shannon capacity of a graph. IEEE Transactions on Information theory 25, 1 (Jan. 1979), 1–7.

Digital Library

[28]

João P. Marques-Silva and Karem A. Sakallah. 1999. GRASP: A Search Algorithm for Propositional Satisfiability. IEEE Trans. Comput. 48, 5 (May 1999), 506–521. Preliminary version in ICCAD ’96.

Digital Library

[29]

Ciaran McCreesh. 2017.

[30]

Solving Hard Subgraph Problems in Parallel. Ph.D. Dissertation. University of Glasgow.

[31]

Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhang, and Sharad Malik. 2001.

[32]

Chaff: Engineering an Efficient SAT Solver. In Proceedings of the 38th Design Automation Conference (DAC ’01). 530–535.

Digital Library

[33]

Jaroslav Nešetřil and Svatopluk Poljak. 1985. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae 026, 2 (1985), 415–419.

[34]

Patrick Prosser. 2012. Exact Algorithms for Maximum Clique: A Computational Study. Algorithms 5, 4 (2012), 545–587.

[35]

Pavel Pudlák. 1997. Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations. Journal of Symbolic Logic 62, 3 (Sept. 1997), 981–998.

[36]

Alexander Razborov, Avi Wigderson, and Andrew Yao. 2002. Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus. Combinatorica 22, 4 (2002), 555–574.

Digital Library

[37]

Benjamin Rossman. 2008.

[38]

On the Constant-Depth Complexity of k-Clique. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC ’08). 721–730.

Digital Library

[39]

Benjamin Rossman. 2010.

[40]

Average-Case Complexity of Detecting Cliques. Ph.D. Dissertation. Masschussets Institute of Technology.

[41]

Benjamin Rossman. 2014. The Monotone Complexity of k-Clique on Random Graphs. SIAM J. Comput. 43, 1 (2014), 256–279. Preliminary version in FOCS ’10.

[42]

Virginia Vassilevska. 2009.

[43]

Efficient Algorithms for Clique Problems. Inform. Process. Lett. 109, 4 (Jan. 2009), 254–257.

Digital Library

[44]

David Zuckerman. 2007. Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number. Theory of Computing 3, 6 (Aug. 2007), 103–128. Preliminary version in STOC ’06. Abstract 1 Introduction 2 Preliminaries 3 Easy Graphs for Regular Resolution 4 Random Graphs Are Hard 5 Clique-Denseness Implies Hardness 6 Random Graphs Are Clique-Dense 7 Concluding Remarks References

Cited By

Sokolov DMohar BShinkar IO'Donnell R(2024)Random (log 𝑛)-CNF Are Hard for Cutting Planes (Again)Proceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649636(2008-2015)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649636
Abram DBeimel AIshai YKushilevitz ENarayanan V(2023)Cryptography from Planted Graphs: Security with Logarithmic-Size MessagesTheory of Cryptography10.1007/978-3-031-48615-9_11(286-315)Online publication date: 27-Nov-2023
https://doi.org/10.1007/978-3-031-48615-9_11
Sofronova ASokolov D(2021)Branching programs with bounded repetitions and flow formulasProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.17Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.17
Show More Cited By

Index Terms

Clique is hard on average for regular resolution
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Random graphs
2. Theory of computation
  1. Computational complexity and cryptography
    1. Proof complexity

Recommendations

Clique Is Hard on Average for Regular Resolution
We prove that for k ≪ 4√n regular resolution requires length n^Ω(k) to establish that an Erdős–Rényi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent and ...
Large Clique is Hard on Average for Resolution
Computer Science – Theory and Applications
Abstract
We prove an $exp (Ω (k^{(1 - ϵ)}))$ resolution size lower bound for the k-Clique problem on random graphs, for (roughly speaking) $k < n^{1 / 3}$ . Towards an optimal resolution lower bound of the problem (i.e. of type $n^{Ω (k)}$ ), we also extend the $n^{Ω (k)}$ bound in [2] ... $^{}$
Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
Abstract
This paper is motivated by seeking the exact complexity of resolution refutation of Tseitin formulas. We prove that the size of any regular resolution refutation of a Tseitin formula $T (G, c)$ based on a connected graph $G = (V, E)$ is at least $2^{Ω (tw (G) / log | ...}$ $^{}$
$^{}$ $^{}$
$^{}$ $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

June 2018

1332 pages

ISBN:9781450355599

DOI:10.1145/3188745

General Chairs:
Ilias Diakonikolas
University of Southern California, USA
,
David Kempe
University of Southern California, USA
,
Program Chair:
Monika Henzinger
University of Vienna, Austria

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '18

Sponsor:

SIGACT

STOC '18: Symposium on Theory of Computing

June 25 - 29, 2018

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
210
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sokolov DMohar BShinkar IO'Donnell R(2024)Random (log 𝑛)-CNF Are Hard for Cutting Planes (Again)Proceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649636(2008-2015)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649636
Abram DBeimel AIshai YKushilevitz ENarayanan V(2023)Cryptography from Planted Graphs: Security with Logarithmic-Size MessagesTheory of Cryptography10.1007/978-3-031-48615-9_11(286-315)Online publication date: 27-Nov-2023
https://doi.org/10.1007/978-3-031-48615-9_11
Sofronova ASokolov D(2021)Branching programs with bounded repetitions and flow formulasProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.17Online publication date: 20-Jul-2021
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2021.17
Atserias ABonacina IDe Rezende SLauria MNordström JRazborov A(2021)Clique Is Hard on Average for Regular ResolutionJournal of the ACM10.1145/344935268:4(1-26)Online publication date: 30-Jun-2021
https://dl.acm.org/doi/10.1145/3449352
Sigley SBeyersdorff O(2021)Proof Complexity of Modal ResolutionJournal of Automated Reasoning10.1007/s10817-021-09609-9Online publication date: 13-Oct-2021
https://doi.org/10.1007/s10817-021-09609-9
de Colnet AMengel S(2021)Characterizing Tseitin-Formulas with Short Regular Resolution RefutationsTheory and Applications of Satisfiability Testing – SAT 202110.1007/978-3-030-80223-3_9(116-133)Online publication date: 2-Jul-2021
https://doi.org/10.1007/978-3-030-80223-3_9
Pang S(2021)Large Clique is Hard on Average for ResolutionComputer Science – Theory and Applications10.1007/978-3-030-79416-3_22(361-380)Online publication date: 17-Jun-2021
https://doi.org/10.1007/978-3-030-79416-3_22
de Rezende SNordström JRisse KSokolov DAceto L(2020)Exponential resolution lower bounds for weak pigeonhole principle and perfect matching formulas over sparse graphsProceedings of the 35th Computational Complexity Conference10.4230/LIPIcs.CCC.2020.28(1-24)Online publication date: 28-Jul-2020
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2020.28
Gocht SMcBride RMcCreesh CNordström JProsser PTrimble J(2020)Certifying Solvers for Clique and Maximum Common (Connected) Subgraph ProblemsPrinciples and Practice of Constraint Programming10.1007/978-3-030-58475-7_20(338-357)Online publication date: 2-Sep-2020
https://doi.org/10.1007/978-3-030-58475-7_20
Dantchev SGalesi NMartin BAceto L(2019)Resolution and the binary encoding of combinatorial principlesProceedings of the 34th Computational Complexity Conference10.4230/LIPIcs.CCC.2019.6(1-25)Online publication date: 17-Jul-2019
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2019.6
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents