Search Results

Documents authored by Kozik, Jakub

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.48
Local Computation Algorithms for Hypergraph Coloring - Following Beck’s Approach

Authors: Andrzej Dorobisz and Jakub Kozik

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We investigate local computation algorithms (LCA) for two-coloring of k-uniform hypergraphs. We focus on hypergraph instances that satisfy strengthened assumption of the Lovász Local Lemma of the form 2^(1-αk) (Δ+1) e < 1, where Δ is the bound on the maximum edge degree. The main question which arises here is for how large α there exists an LCA that is able to properly color such hypergraphs in polylogarithmic time per query. We describe briefly how upgrading the classical sequential procedure of Beck from 1991 with Moser and Tardos' Resample yields polylogarithmic LCA that works for α up to 1/4. Then, we present an improved procedure that solves wider range of instances by allowing α up to 1/3.
Cite as

Andrzej Dorobisz and Jakub Kozik. Local Computation Algorithms for Hypergraph Coloring - Following Beck’s Approach. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 48:1-48:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dorobisz_et_al:LIPIcs.ICALP.2023.48,
  author =	{Dorobisz, Andrzej and Kozik, Jakub},
  title =	{{Local Computation Algorithms for Hypergraph Coloring - Following Beck’s Approach}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{48:1--48:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel 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.2023.48},
  URN =		{urn:nbn:de:0030-drops-181002},
  doi =		{10.4230/LIPIcs.ICALP.2023.48},
  annote =	{Keywords: Local Computation Algorithms, Hypergraph Coloring, Property B}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.89
Improving Gebauer’s Construction of 3-Chromatic Hypergraphs with Few Edges

Authors: Jakub Kozik

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

Abstract
In 1964 Erdős proved, by randomized construction, that the minimum number of edges in a k-graph that is not two colorable is O(k² 2^k). To this day, it is not known whether there exist such k-graphs with smaller number of edges. Known deterministic constructions use much larger number of edges. The most recent one by Gebauer requires 2^{k+Θ(k^{2/3})} edges. Applying a derandomization technique we reduce that number to 2^{k+Θ̃(k^{1/2})}.
Cite as

Jakub Kozik. Improving Gebauer’s Construction of 3-Chromatic Hypergraphs with Few Edges. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 89:1-89:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kozik:LIPIcs.ICALP.2021.89,
  author =	{Kozik, Jakub},
  title =	{{Improving Gebauer’s Construction of 3-Chromatic Hypergraphs with Few Edges}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{89:1--89:9},
  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.89},
  URN =		{urn:nbn:de:0030-drops-141587},
  doi =		{10.4230/LIPIcs.ICALP.2021.89},
  annote =	{Keywords: Property B, Hypergraph Coloring, Deterministic Constructions}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.46
A Note on Two-Colorability of Nonuniform Hypergraphs

Authors: Lech Duraj, Grzegorz Gutowski, and Jakub Kozik

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
For a hypergraph H, let q(H) denote the expected number of monochromatic edges when the color of each vertex in H is sampled uniformly at random from the set of size 2. Let s_{min}(H) denote the minimum size of an edge in H. Erdös asked in 1963 whether there exists an unbounded function g(k) such that any hypergraph H with s_{min}(H) >=slant k and q(H) <=slant g(k) is two colorable. Beck in 1978 answered this question in the affirmative for a function g(k) = Theta(log^* k). We improve this result by showing that, for an absolute constant delta>0, a version of random greedy coloring procedure is likely to find a proper two coloring for any hypergraph H with s_{min}(H) >=slant k and q(H) <=slant delta * log k.
Cite as

Lech Duraj, Grzegorz Gutowski, and Jakub Kozik. A Note on Two-Colorability of Nonuniform Hypergraphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{duraj_et_al:LIPIcs.ICALP.2018.46,
  author =	{Duraj, Lech and Gutowski, Grzegorz and Kozik, Jakub},
  title =	{{A Note on Two-Colorability of Nonuniform Hypergraphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.46},
  URN =		{urn:nbn:de:0030-drops-90505},
  doi =		{10.4230/LIPIcs.ICALP.2018.46},
  annote =	{Keywords: Property B, Nonuniform Hypergraphs, Hypergraph Coloring, Random Greedy Coloring}
}
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 About DROPS Imprint Privacy Contact