3 Search Results for "Cooley, Oliver"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.81
Worst-Case and Average-Case Hardness of Hypercycle and Database Problems

Authors: Cheng-Hao Fu, Andrea Lincoln, and Rene Reyes

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
In this paper we present tight lower-bounds and new upper-bounds for hypergraph and database problems. We give tight lower-bounds for finding minimum hypercycles. We give tight lower-bounds for a substantial regime of unweighted hypercycle. We also give a new faster algorithm for longer unweighted hypercycles. We give a worst-case to average-case reduction from detecting a subgraph of a hypergraph in the worst-case to counting subgraphs of hypergraphs in the average-case. We demonstrate two applications of this worst-case to average-case reduction, which result in average-case lower bounds for counting counting hypercycles in random hypergraphs and queries in average-case databases. Our tight upper and lower bounds for hypercycle detection in the worst-case have immediate implications for the average-case via our worst-case to average-case reductions.
Cite as

Cheng-Hao Fu, Andrea Lincoln, and Rene Reyes. Worst-Case and Average-Case Hardness of Hypercycle and Database Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 81:1-81:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fu_et_al:LIPIcs.ICALP.2025.81,
  author =	{Fu, Cheng-Hao and Lincoln, Andrea and Reyes, Rene},
  title =	{{Worst-Case and Average-Case Hardness of Hypercycle and Database Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{81:1--81:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.81},
  URN =		{urn:nbn:de:0030-drops-234581},
  doi =		{10.4230/LIPIcs.ICALP.2025.81},
  annote =	{Keywords: Hypergraphs, hypercycles, fine-grained complexity, average-case complexity, databases}
}
Document
Keynote Speakers
DOI: 10.4230/LIPIcs.AofA.2018.7
Vanishing of Cohomology Groups of Random Simplicial Complexes (Keynote Speakers)

Authors: Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
We consider k-dimensional random simplicial complexes that are generated from the binomial random (k+1)-uniform hypergraph by taking the downward-closure, where k >= 2. For each 1 <= j <= k-1, we determine when all cohomology groups with coefficients in F_2 from dimension one up to j vanish and the zero-th cohomology group is isomorphic to F_2. This property is not monotone, but nevertheless we show that it has a single sharp threshold. Moreover, we prove a hitting time result, relating the vanishing of these cohomology groups to the disappearance of the last minimal obstruction. Furthermore, we study the asymptotic distribution of the dimension of the j-th cohomology group inside the critical window. As a corollary, we deduce a hitting time result for a different model of random simplicial complexes introduced in [Linial and Meshulam, Combinatorica, 2006], a result which has only been known for dimension two [Kahle and Pittel, Random Structures Algorithms, 2016].
Cite as

Oliver Cooley, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel. Vanishing of Cohomology Groups of Random Simplicial Complexes (Keynote Speakers). In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cooley_et_al:LIPIcs.AofA.2018.7,
  author =	{Cooley, Oliver and Del Giudice, Nicola and Kang, Mihyun and Spr\"{u}ssel, Philipp},
  title =	{{Vanishing of Cohomology Groups of Random Simplicial Complexes}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.7},
  URN =		{urn:nbn:de:0030-drops-89006},
  doi =		{10.4230/LIPIcs.AofA.2018.7},
  annote =	{Keywords: Random hypergraphs, random simplicial complexes, sharp threshold, hitting time, connectedness}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.710
The Minimum Bisection in the Planted Bisection Model

Authors: Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
In the planted bisection model a random graph G(n,p_+,p_-) with n vertices is created by partitioning the vertices randomly into two classes of equal size (up to plus or minus 1). Any two vertices that belong to the same class are linked by an edge with probability p_+ and any two that belong to different classes with probability (p_-) <(p_+) independently. The planted bisection model has been used extensively to benchmark graph partitioning algorithms. If (p_+)=2(d_+)/n and (p_-)=2(d_-)/n for numbers 0 <= (d_-) <(d_+) that remain fixed as n tends to infinity, then with high probability the "planted" bisection (the one used to construct the graph) will not be a minimum bisection. In this paper we derive an asymptotic formula for the minimum bisection width under the assumption that (d_+)-(d_-) > c * sqrt((d_+)ln(d_+)) for a certain constant c>0.
Cite as

Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, and Kathrin Skubch. The Minimum Bisection in the Planted Bisection Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 710-725, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{cojaoghlan_et_al:LIPIcs.APPROX-RANDOM.2015.710,
  author =	{Coja-Oghlan, Amin and Cooley, Oliver and Kang, Mihyun and Skubch, Kathrin},
  title =	{{The Minimum Bisection in the Planted Bisection Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{710--725},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.710},
  URN =		{urn:nbn:de:0030-drops-53315},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.710},
  annote =	{Keywords: Random graphs, minimum bisection, planted bisection, belief propagation.}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2018
  • 1 2015

  • Refine by Author
  • 2 Cooley, Oliver
  • 2 Kang, Mihyun
  • 1 Coja-Oghlan, Amin
  • 1 Del Giudice, Nicola
  • 1 Fu, Cheng-Hao
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Hypergraphs
  • 1 Mathematics of computing → Random graphs
  • 1 Theory of computation → Database theory
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Hypergraphs
  • 1 Random graphs
  • 1 Random hypergraphs
  • 1 average-case complexity
  • 1 belief propagation.
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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