Search Results

Documents authored by Davies, Ewan

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.35
A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs

Authors: Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph - in the language of approximate counting, we give an FPRAS for #BIS on the class of dense, regular bipartite graphs. Efficient counting algorithms typically apply to "high-temperature" problems on bounded-degree graphs, and our contribution is a notable exception as it applies to dense graphs in a low-temperature setting. Our methods give a counting-focused complement to the long line of work in combinatorial optimization showing that CSPs such as Max-Cut and Unique Games are easy on dense graphs via spectral arguments. Our contributions include a novel extension of the method of graph containers that differs considerably from other recent low-temperature algorithms. The additional key insights come from spectral graph theory and have previously been successful in approximation algorithms. As a result, we can overcome some limitations that seem inherent to the aforementioned class of algorithms. In particular, we exploit the fact that dense, regular graphs exhibit a kind of small-set expansion (i.e., bounded threshold rank), which, via subspace enumeration, lets us enumerate small cuts efficiently.
Cite as

Charlie Carlson, Ewan Davies, Alexandra Kolla, and Aditya Potukuchi. A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{carlson_et_al:LIPIcs.ICALP.2024.35,
  author =	{Carlson, Charlie and Davies, Ewan and Kolla, Alexandra and Potukuchi, Aditya},
  title =	{{A Spectral Approach to Approximately Counting Independent Sets in Dense Bipartite Graphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{35:1--35:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.35},
  URN =		{urn:nbn:de:0030-drops-201782},
  doi =		{10.4230/LIPIcs.ICALP.2024.35},
  annote =	{Keywords: approximate counting, independent sets, bipartite graphs, graph containers}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.62
Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs

Authors: Ewan Davies and Will Perkins

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We determine the computational complexity of approximately counting and sampling independent sets of a given size in bounded-degree graphs. That is, we identify a critical density α_c(Δ) and provide (i) for α < α_c(Δ) randomized polynomial-time algorithms for approximately sampling and counting independent sets of given size at most α n in n-vertex graphs of maximum degree Δ; and (ii) a proof that unless NP=RP, no such algorithms exist for α > α_c(Δ). The critical density is the occupancy fraction of hard core model on the clique K_{Δ+1} at the uniqueness threshold on the infinite Δ-regular tree, giving α_c(Δ) ~ e/(1+e)1/(Δ) as Δ → ∞.
Cite as

Ewan Davies and Will Perkins. Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 62:1-62:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{davies_et_al:LIPIcs.ICALP.2021.62,
  author =	{Davies, Ewan and Perkins, Will},
  title =	{{Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{62:1--62:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.62},
  URN =		{urn:nbn:de:0030-drops-141310},
  doi =		{10.4230/LIPIcs.ICALP.2021.62},
  annote =	{Keywords: approximate counting, independent sets, Markov chains}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.13
Statistical Physics Approaches to Unique Games

Authors: Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Games Conjecture. The variant, which we call Count Unique Games, is a promise problem in which the "yes" case guarantees a certain number of highly satisfiable assignments to the Unique Games instance. In the standard Unique Games problem, the "yes" case only guarantees at least one such assignment. We exhibit efficient algorithms for Count Unique Games based on approximating a suitable partition function for the Unique Games instance via (i) a zero-free region and polynomial interpolation, and (ii) the cluster expansion. We also show that a modest improvement to the parameters for which we give results would be strong negative evidence for the truth of the Unique Games Conjecture.
Cite as

Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts. Statistical Physics Approaches to Unique Games. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 13:1-13:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{coulson_et_al:LIPIcs.CCC.2020.13,
  author =	{Coulson, Matthew and Davies, Ewan and Kolla, Alexandra and Patel, Viresh and Regts, Guus},
  title =	{{Statistical Physics Approaches to Unique Games}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{13:1--13:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.13},
  URN =		{urn:nbn:de:0030-drops-125650},
  doi =		{10.4230/LIPIcs.CCC.2020.13},
  annote =	{Keywords: Unique Games Conjecture, approximation algorithm, Potts model, cluster expansion, polynomial interpolation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact