4 Search Results for "Urrutia, Florent"

Document
DOI: 10.4230/LIPIcs.STACS.2025.33
Metric Dimension and Geodetic Set Parameterized by Vertex Cover

Authors: Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
For a graph G, a subset S ⊆ V(G) is called a resolving set of G if, for any two vertices u,v ∈ V(G), there exists a vertex w ∈ S such that d(w,u) ≠ d(w,v). The Metric Dimension problem takes as input a graph G on n vertices and a positive integer k, and asks whether there exists a resolving set of size at most k. In another metric-based graph problem, Geodetic Set, the input is a graph G and an integer k, and the objective is to determine whether there exists a subset S ⊆ V(G) of size at most k such that, for any vertex u ∈ V(G), there are two vertices s₁, s₂ ∈ S such that u lies on a shortest path from s₁ to s₂. These two classical problems are known to be intractable with respect to the natural parameter, i.e., the solution size, as well as most structural parameters, including the feedback vertex set number and pathwidth. We observe that both problems admit an FPT algorithm running in 2^𝒪(vc²) ⋅ n^𝒪(1) time, and a kernelization algorithm that outputs a kernel with 2^𝒪(vc) vertices, where vc is the vertex cover number. We prove that unless the Exponential Time Hypothesis (ETH) fails, Metric Dimension and Geodetic Set, even on graphs of bounded diameter, do not admit - an FPT algorithm running in 2^o(vc²) ⋅ n^𝒪(1) time, nor - a kernelization algorithm that does not increase the solution size and outputs a kernel with 2^o(vc) vertices. We only know of one other problem in the literature that admits such a tight algorithmic lower bound with respect to vc. Similarly, the list of known problems with exponential lower bounds on the number of vertices in kernelized instances is very short.
Cite as

Florent Foucaud, Esther Galby, Liana Khazaliya, Shaohua Li, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale. Metric Dimension and Geodetic Set Parameterized by Vertex Cover. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{foucaud_et_al:LIPIcs.STACS.2025.33,
  author =	{Foucaud, Florent and Galby, Esther and Khazaliya, Liana and Li, Shaohua and Mc Inerney, Fionn and Sharma, Roohani and Tale, Prafullkumar},
  title =	{{Metric Dimension and Geodetic Set Parameterized by Vertex Cover}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{33:1--33:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.33},
  URN =		{urn:nbn:de:0030-drops-228593},
  doi =		{10.4230/LIPIcs.STACS.2025.33},
  annote =	{Keywords: Parameterized Complexity, ETH-based Lower Bounds, Kernelization, Vertex Cover, Metric Dimension, Geodetic Set}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.27
Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication

Authors: Michael Elkin and Ofer Neiman

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Consider an undirected weighted graph G = (V,E,w). We study the problem of computing (1+ε)-approximate shortest paths for S × V, for a subset S ⊆ V of |S| = n^r sources, for some 0 < r ≤ 1. We devise a significantly improved algorithm for this problem in the entire range of parameter r, in both the classical centralized and the parallel (PRAM) models of computation, and in a wide range of r in the distributed (Congested Clique) model. Specifically, our centralized algorithm for this problem requires time Õ(|E| ⋅ n^{o(1)} + n^{ω(r)}), where n^{ω(r)} is the time required to multiply an n^r × n matrix by an n × n one. Our PRAM algorithm has polylogarithmic time (log n)^{O(1/ρ)}, and its work complexity is Õ(|E| ⋅ n^ρ + n^{ω(r)}), for any arbitrarily small constant ρ > 0. In particular, for r ≤ 0.313…, our centralized algorithm computes S × V (1+ε)-approximate shortest paths in n^{2 + o(1)} time. Our PRAM polylogarithmic-time algorithm has work complexity O(|E| ⋅ n^ρ + n^{2+o(1)}), for any arbitrarily small constant ρ > 0. Previously existing solutions either require centralized time/parallel work of O(|E| ⋅ |S|) or provide much weaker approximation guarantees. In the Congested Clique model, our algorithm solves the problem in polylogarithmic time for |S| = n^r sources, for r ≤ 0.655, while previous state-of-the-art algorithms did so only for r ≤ 1/2. Moreover, it improves previous bounds for all r > 1/2. For unweighted graphs, the running time is improved further to poly(log log n) for r ≤ 0.655. Previously this running time was known for r ≤ 1/2.
Cite as

Michael Elkin and Ofer Neiman. Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 27:1-27:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{elkin_et_al:LIPIcs.STACS.2022.27,
  author =	{Elkin, Michael and Neiman, Ofer},
  title =	{{Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{27:1--27:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.27},
  URN =		{urn:nbn:de:0030-drops-158379},
  doi =		{10.4230/LIPIcs.STACS.2022.27},
  annote =	{Keywords: Shortest paths, matrix multiplication, hopsets}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.64
A New Approach to Multi-Party Peer-to-Peer Communication Complexity

Authors: Adi Rosén and Florent Urrutia

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
We introduce new models and new information theoretic measures for the study of communication complexity in the natural peer-to-peer, multi-party, number-in-hand setting. We prove a number of properties of our new models and measures, and then, in order to exemplify their effectiveness, we use them to prove two lower bounds. The more elaborate one is a tight lower bound of Omega(kn) on the multi-party peer-to-peer randomized communication complexity of the k-player, n-bit function Disjointness, Disj_k^n. The other one is a tight lower bound of Omega(kn) on the multi-party peer-to-peer randomized communication complexity of the k-player, n-bit bitwise parity function, Par_k^n. Both lower bounds hold when n=Omega(k). The lower bound for Disj_k^n improves over the lower bound that can be inferred from the result of Braverman et al. (FOCS 2013), which was proved in the coordinator model and can yield a lower bound of Omega(kn/log k) in the peer-to-peer model. To the best of our knowledge, our lower bounds are the first tight (non-trivial) lower bounds on communication complexity in the natural peer-to-peer multi-party setting. In addition to the above results for communication complexity, we also prove, using the same tools, an Omega(n) lower bound on the number of random bits necessary for the (information theoretic) private computation of the function Disj_k^n.
Cite as

Adi Rosén and Florent Urrutia. A New Approach to Multi-Party Peer-to-Peer Communication Complexity. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 64:1-64:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{rosen_et_al:LIPIcs.ITCS.2019.64,
  author =	{Ros\'{e}n, Adi and Urrutia, Florent},
  title =	{{A New Approach to Multi-Party Peer-to-Peer Communication Complexity}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{64:1--64:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.64},
  URN =		{urn:nbn:de:0030-drops-101576},
  doi =		{10.4230/LIPIcs.ITCS.2019.64},
  annote =	{Keywords: communication complexity, multi-party communication complexity, peer-to-peer communication complexity, information complexity, private computation}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.57
Multi-Party Protocols, Information Complexity and Privacy

Authors: Iordanis Kerenidis, Adi Rosén, and Florent Urrutia

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
We introduce the new measure of Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing peer-to-peer model and show a number of interesting properties and applications of our new notion: the Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; an explicit calculation of the zero-error Public Information Complexity of the k-party, n-bit Parity function, where a player outputs the bit-wise parity of the inputs. The latter result establishes that the amount of randomness needed for a private protocol that computes this function is Omega(n).
Cite as

Iordanis Kerenidis, Adi Rosén, and Florent Urrutia. Multi-Party Protocols, Information Complexity and Privacy. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kerenidis_et_al:LIPIcs.MFCS.2016.57,
  author =	{Kerenidis, Iordanis and Ros\'{e}n, Adi and Urrutia, Florent},
  title =	{{Multi-Party Protocols, Information Complexity and Privacy}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{57:1--57:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.57},
  URN =		{urn:nbn:de:0030-drops-64696},
  doi =		{10.4230/LIPIcs.MFCS.2016.57},
  annote =	{Keywords: multi-party protocols, information theory, communication complexity, multi-party private computation (MPC), randomness}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2022
  • 1 2019
  • 1 2016

  • Refine by Author
  • 2 Rosén, Adi
  • 2 Urrutia, Florent
  • 1 Elkin, Michael
  • 1 Foucaud, Florent
  • 1 Galby, Esther
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Information theory
  • 1 Theory of computation → Communication complexity
  • 1 Theory of computation → Cryptographic protocols
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 2 communication complexity
  • 1 ETH-based Lower Bounds
  • 1 Geodetic Set
  • 1 Kernelization
  • 1 Metric Dimension
  • 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