3 Search Results for "Gluch, Grzegorz"

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.91

A Sublinear Time Tester for Max-Cut on Clusterable Graphs

Authors: Agastya Vibhuti Jha and Akash Kumar

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

Abstract

One natural question in the area of sublinear time algorithms asks whether we can distinguish between graphs with max-cut value at least 1-ε from graphs with max-cut value at most 1/2+ε in the adjacency list model where we can make degree queries and neighbor queries. Chiplunkar, Kapralov, Khanna, Mousavifar, and Peres (FOCS' 18) showed that in graphs of bounded degree, one cannot hope for a factor 1/2+ε approximation to the max-cut value in time n^{1/2+o(ε)}. Recently, Peng and Yoshida (SODA '23) obtained o(n) time algorithms which can distinguish expanders with max-cut value at least 1-ε from expanders with small max-cut value (their running time is n^{1/2+O(ε)}). In this paper, going beyond the results of Peng-Yoshida, we develop sublinear time algorithms for this problem on clusterable graphs (which is a graph class with a good community structure). Our algorithms run in ≈ n^{0.5001+ O(ε)} time. A natural extension of Peng-Yoshida approach does not seem to work for clusterable graphs. Indeed, their random walk based technique tracks the 𝓁₂ length of random walk vectors and they exploit the difference in the length of these vectors to tell apart expanders with large cut value from expanders with small cut-value. Such approaches fail to be reliable when graph has loosely connected clusters. Taking inspiration from [Ashish Chiplunkar et al., 2018], we exploit the more refined geometry of spectra of clusterable graphs which leads to our sublinear time implementation. We prove a novel spectral lemma which shows that in a spectral expander 2 - λ_{n-1} ≥ Ω(λ₂). This lemma is leveraged to show that there is a suitable difference between spectra of clusterable graphs with large cut value and spectra of clusterable graphs with small cut value. We use this gap to obtain our sublinear time implementation. To do this, we obtain a nuanced understanding of the eigenvector structure of clusterable graphs and in particular, we show that the eigenvectors of the normalized Laplacian of a clusterable graph, corresponding to eigenvalues which are close to 2 have a small infinity norm.

Cite as

Agastya Vibhuti Jha and Akash Kumar. A Sublinear Time Tester for Max-Cut on Clusterable Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 91:1-91:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jha_et_al:LIPIcs.ICALP.2024.91,
  author =	{Jha, Agastya Vibhuti and Kumar, Akash},
  title =	{{A Sublinear Time Tester for Max-Cut on Clusterable Graphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{91:1--91:17},
  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.91},
  URN =		{urn:nbn:de:0030-drops-202344},
  doi =		{10.4230/LIPIcs.ICALP.2024.91},
  annote =	{Keywords: Sublinear Algorithms, Graph Algorithms, Clusterable Graphs, Property Testung}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.ICDT.2020.2

What Makes a Variant of Query Determinacy (Un)Decidable? (Invited Talk)

Authors: Jerzy Marcinkowski

Published in: LIPIcs, Volume 155, 23rd International Conference on Database Theory (ICDT 2020)

Abstract

This paper was written as the companion paper of the ICDT 2020 invited tutorial. Query determinacy is a broad topic, with literally hundreds of papers published since late 1980s. This paper is not going to be a "survey" but rather a personal perspective of a person somehow involved in the recent developments in the area. First I explain how, in the last 30+ years, the question of determinacy was formalized. There are many parameters here: obviously one needs to choose the query language of the available views and the query language of the query itself. But - surprisingly - there is also some choice regarding what the word "to compute" actually means in this context. Then I concentrate on certain variants of the decision problem of determinacy (for each choice of parameters there is one such problem) and explain how I understand the mechanisms rendering such variants of determinacy decidable or undecidable. This is on a rather informal level. No really new theorems are presented, but I show some improvements of existing theorems and also simplified proofs of some of the earlier results.

Cite as

Jerzy Marcinkowski. What Makes a Variant of Query Determinacy (Un)Decidable? (Invited Talk). In 23rd International Conference on Database Theory (ICDT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 155, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{marcinkowski:LIPIcs.ICDT.2020.2,
  author =	{Marcinkowski, Jerzy},
  title =	{{What Makes a Variant of Query Determinacy (Un)Decidable?}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Lutz, Carsten and Jung, Jean Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2020.2},
  URN =		{urn:nbn:de:0030-drops-119265},
  doi =		{10.4230/LIPIcs.ICDT.2020.2},
  annote =	{Keywords: database theory, query, view, determinacy}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2019.15

The First Order Truth Behind Undecidability of Regular Path Queries Determinacy

Authors: Grzegorz Głuch, Jerzy Marcinkowski, and Piotr Ostropolski-Nalewaja

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract

In our paper [Głuch, Marcinkowski, Ostropolski-Nalewaja, LICS ACM, 2018] we have solved an old problem stated in [Calvanese, De Giacomo, Lenzerini, Vardi, SPDS ACM, 2000] showing that query determinacy is undecidable for Regular Path Queries. Here a strong generalisation of this result is shown, and - we think - a very unexpected one. We prove that no regularity is needed: determinacy remains undecidable even for finite unions of conjunctive path queries.

Cite as

Grzegorz Głuch, Jerzy Marcinkowski, and Piotr Ostropolski-Nalewaja. The First Order Truth Behind Undecidability of Regular Path Queries Determinacy. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gluch_et_al:LIPIcs.ICDT.2019.15,
  author =	{G{\l}uch, Grzegorz and Marcinkowski, Jerzy and Ostropolski-Nalewaja, Piotr},
  title =	{{The First Order Truth Behind Undecidability of Regular Path Queries Determinacy}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.15},
  URN =		{urn:nbn:de:0030-drops-103175},
  doi =		{10.4230/LIPIcs.ICDT.2019.15},
  annote =	{Keywords: database theory, query, view, determinacy, recursive path queries}
}

Refine by Author
2 Marcinkowski, Jerzy
1 Głuch, Grzegorz
1 Jha, Agastya Vibhuti
1 Kumar, Akash
1 Ostropolski-Nalewaja, Piotr

Refine by Classification
1 Information systems → Graph-based database models
1 Mathematics of computing → Spectra of graphs
1 Theory of computation → Database theory
1 Theory of computation → Streaming, sublinear and near linear time algorithms

Refine by Keyword
2 database theory
2 determinacy
2 query
2 view
1 Clusterable Graphs
Show More...

Refine by Type
3 document

Refine by Publication Year
1 2019
1 2020
1 2024