31 Search Results for "Cohen, David"


Document
Inductive Continuity via Brouwer Trees

Authors: Liron Cohen, Bruno da Rocha Paiva, Vincent Rahli, and Ayberk Tosun

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)


Abstract
Continuity is a key principle of intuitionistic logic that is generally accepted by constructivists but is inconsistent with classical logic. Most commonly, continuity states that a function from the Baire space to numbers, only needs approximations of the points in the Baire space to compute. More recently, another formulation of the continuity principle was put forward. It states that for any function F from the Baire space to numbers, there exists a (dialogue) tree that contains the values of F at its leaves and such that the modulus of F at each point of the Baire space is given by the length of the corresponding branch in the tree. In this paper we provide the first internalization of this "inductive" continuity principle within a computational setting. Concretely, we present a class of intuitionistic theories that validate this formulation of continuity thanks to computations that construct such dialogue trees internally to the theories using effectful computations. We further demonstrate that this inductive continuity principle implies other forms of continuity principles.

Cite as

Liron Cohen, Bruno da Rocha Paiva, Vincent Rahli, and Ayberk Tosun. Inductive Continuity via Brouwer Trees. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.MFCS.2023.37,
  author =	{Cohen, Liron and da Rocha Paiva, Bruno and Rahli, Vincent and Tosun, Ayberk},
  title =	{{Inductive Continuity via Brouwer Trees}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.37},
  URN =		{urn:nbn:de:0030-drops-185718},
  doi =		{10.4230/LIPIcs.MFCS.2023.37},
  annote =	{Keywords: Continuity, Dialogue trees, Stateful computations, Intuitionistic Logic, Extensional Type Theory, Constructive Type Theory, Realizability, Theorem proving, Agda}
}
Document
Making Self-Stabilizing Algorithms for Any Locally Greedy Problem

Authors: Johanne Cohen, Laurence Pilard, Mikaël Rabie, and Jonas Sénizergues

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)


Abstract
Self-stabilizing algorithms are a way to deal with network dynamicity, as it will update itself after a network change (addition or removal of nodes or edges), as long as changes are not frequent. We propose an automatic transformation of synchronous distributed algorithms that solve locally greedy and mendable problems into self-stabilizing algorithms in anonymous networks. Mendable problems are a generalization of greedy problems where any partial solution may be transformed -instead of completed- into a global solution: every time we extend the partial solution, we are allowed to change the previous partial solution up to a given distance. Locally here means that to extend a solution for a node, we need to look at a constant distance from it. In order to do this, we propose the first explicit self-stabilizing algorithm computing a (k,k-1)-ruling set (i.e. a "maximal independent set at distance k"). By combining this technique multiple times, we compute a distance-K coloring of the graph. With this coloring we can finally simulate Local model algorithms running in a constant number of rounds, using the colors as unique identifiers. Our algorithms work under the Gouda daemon, similar to the probabilistic daemon: if an event should eventually happen, it will occur.

Cite as

Johanne Cohen, Laurence Pilard, Mikaël Rabie, and Jonas Sénizergues. Making Self-Stabilizing Algorithms for Any Locally Greedy Problem. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.SAND.2023.11,
  author =	{Cohen, Johanne and Pilard, Laurence and Rabie, Mika\"{e}l and S\'{e}nizergues, Jonas},
  title =	{{Making Self-Stabilizing Algorithms for Any Locally Greedy Problem}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.11},
  URN =		{urn:nbn:de:0030-drops-179475},
  doi =		{10.4230/LIPIcs.SAND.2023.11},
  annote =	{Keywords: Greedy Problem, Ruling Set, Distance-K Coloring, Self-Stabilizing Algorithm}
}
Document
Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs

Authors: David Auger, Pierre Coucheney, and Loric Duhazé

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
A rotor walk in a directed graph can be thought of as a deterministic version of a Markov Chain, where a pebble moves from vertex to vertex following a simple rule until a terminal vertex, or sink, has been reached. The ARRIVAL problem, as defined by Dohrau et al. [Dohrau et al., 2017], consists in determining which sink will be reached. While the walk itself can take an exponential number of steps, this problem belongs to the complexity class NP ∩ co-NP without being known to be in P. In this work, we define a class of directed graphs, namely tree-like multigraphs, which are multigraphs having the global shape of an undirected tree. We prove that in this class, ARRIVAL can be solved in almost linear time, while the number of steps of a rotor walk can still be exponential. Then, we give an application of this result to solve some deterministic analogs of stochastic models (e.g., Markovian decision processes, Stochastic Games).

Cite as

David Auger, Pierre Coucheney, and Loric Duhazé. Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{auger_et_al:LIPIcs.MFCS.2022.12,
  author =	{Auger, David and Coucheney, Pierre and Duhaz\'{e}, Loric},
  title =	{{Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.12},
  URN =		{urn:nbn:de:0030-drops-168103},
  doi =		{10.4230/LIPIcs.MFCS.2022.12},
  annote =	{Keywords: Rotor-routing, Rotor Walk, Reachability Problem, Game Theory, Tree-like Multigraph}
}
Document
Track A: Algorithms, Complexity and Games
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems

Authors: Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, and Pasin Manurangsi

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
We study several questions related to diversifying search results. We give improved approximation algorithms in each of the following problems, together with some lower bounds. 1) We give a polynomial-time approximation scheme (PTAS) for a diversified search ranking problem [Nikhil Bansal et al., 2010] whose objective is to minimizes the discounted cumulative gain. Our PTAS runs in time n^{2^O(log(1/ε)/ε)} ⋅ m^O(1) where n denotes the number of elements in the databases and m denotes the number of constraints. Complementing this result, we show that no PTAS can run in time f(ε) ⋅ (nm)^{2^o(1/ε)} assuming Gap-ETH and therefore our running time is nearly tight. Both our upper and lower bounds answer open questions from [Nikhil Bansal et al., 2010]. 2) We next consider the Max-Sum Dispersion problem, whose objective is to select k out of n elements from a database that maximizes the dispersion, which is defined as the sum of the pairwise distances under a given metric. We give a quasipolynomial-time approximation scheme (QPTAS) for the problem which runs in time n^{O_ε(log n)}. This improves upon previously known polynomial-time algorithms with approximate ratios 0.5 [Refael Hassin et al., 1997; Allan Borodin et al., 2017]. Furthermore, we observe that reductions from previous work rule out approximation schemes that run in n^õ_ε(log n) time assuming ETH. 3) Finally, we consider a generalization of Max-Sum Dispersion called Max-Sum Diversification. In addition to the sum of pairwise distance, the objective also includes another function f. For monotone submodular function f, we give a quasipolynomial-time algorithm with approximation ratio arbitrarily close to (1-1/e). This improves upon the best polynomial-time algorithm which has approximation ratio 0.5 [Allan Borodin et al., 2017]. Furthermore, the (1-1/e) factor is also tight as achieving better-than-(1-1/e) approximation is NP-hard [Uriel Feige, 1998].

Cite as

Amir Abboud, Vincent Cohen-Addad, Euiwoong Lee, and Pasin Manurangsi. Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{abboud_et_al:LIPIcs.ICALP.2022.7,
  author =	{Abboud, Amir and Cohen-Addad, Vincent and Lee, Euiwoong and Manurangsi, Pasin},
  title =	{{Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.7},
  URN =		{urn:nbn:de:0030-drops-163481},
  doi =		{10.4230/LIPIcs.ICALP.2022.7},
  annote =	{Keywords: Approximation Algorithms, Complexity, Data Mining, Diversification}
}
Document
Track A: Algorithms, Complexity and Games
Low-Degree Polynomials Extract From Local Sources

Authors: Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, this model was introduced by De and Watson (TOCT 2012) and Viola (SICOMP 2014), and is closely related to sources generated by AC⁰ circuits and bounded-width branching programs. In particular, extractors for local sources also work for sources generated by these classical computational models. Despite being introduced a decade ago, little progress has been made on improving the entropy requirement for extracting from local sources. The current best explicit extractors require entropy n^{1/2}, and follow via a reduction to affine extractors. To start, we prove a barrier showing that one cannot hope to improve this entropy requirement via a black-box reduction of this form. In particular, new techniques are needed. In our main result, we seek to answer whether low-degree polynomials (over 𝔽₂) hold potential for breaking this barrier. We answer this question in the positive, and fully characterize the power of low-degree polynomials as extractors for local sources. More precisely, we show that a random degree r polynomial is a low-error extractor for n-bit local sources with min-entropy Ω(r(nlog n)^{1/r}), and we show that this is tight. Our result leverages several new ingredients, which may be of independent interest. Our existential result relies on a new reduction from local sources to a more structured family, known as local non-oblivious bit-fixing sources. To show its tightness, we prove a "local version" of a structural result by Cohen and Tal (RANDOM 2015), which relies on a new "low-weight" Chevalley-Warning theorem.

Cite as

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro. Low-Degree Polynomials Extract From Local Sources. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{alrabiah_et_al:LIPIcs.ICALP.2022.10,
  author =	{Alrabiah, Omar and Chattopadhyay, Eshan and Goodman, Jesse and Li, Xin and Ribeiro, Jo\~{a}o},
  title =	{{Low-Degree Polynomials Extract From Local Sources}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.10},
  URN =		{urn:nbn:de:0030-drops-163519},
  doi =		{10.4230/LIPIcs.ICALP.2022.10},
  annote =	{Keywords: Randomness extractors, local sources, samplable sources, AC⁰ circuits, branching programs, low-degree polynomials, Chevalley-Warning}
}
Document
Track A: Algorithms, Complexity and Games
Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances

Authors: Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
We construct data structures for extremal and pairwise distances in directed graphs in the presence of transient edge failures. Henzinger et al. [ITCS 2017] initiated the study of fault-tolerant (sensitivity) oracles for the diameter and vertex eccentricities. We extend this with a special focus on space efficiency. We present several new data structures, among them the first fault-tolerant eccentricity oracle for dual failures in subcubic space. We further prove lower bounds that show limits to approximation vs. space and diameter vs. space trade-offs for fault-tolerant oracles. They highlight key differences between data structures for undirected and directed graphs. Initially, our oracles are randomized leaning on a sampling technique frequently used in sensitivity analysis. Building on the work of Alon, Chechik, and Cohen [ICALP 2019] as well as Karthik and Parter [SODA 2021], we develop a hierarchical framework to derandomize fault-tolerant data structures. We first apply it to our own diameter and eccentricity oracles and then show its versatility by derandomizing algorithms from the literature: the distance sensitivity oracle of Ren [JCSS 2022] and the Single-Source Replacement Path algorithm of Chechik and Magen [ICALP 2020]. This way, we obtain the first deterministic distance sensitivity oracle with subcubic preprocessing time.

Cite as

Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.ICALP.2022.22,
  author =	{Bil\`{o}, Davide and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin},
  title =	{{Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{22:1--22:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.22},
  URN =		{urn:nbn:de:0030-drops-163633},
  doi =		{10.4230/LIPIcs.ICALP.2022.22},
  annote =	{Keywords: derandomization, diameter, eccentricity, fault-tolerant data structure, sensitivity oracle, space lower bound}
}
Document
Track A: Algorithms, Complexity and Games
Expander Random Walks: The General Case and Limitations

Authors: Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
Cohen, Peri and Ta-Shma [Gil Cohen et al., 2021] considered the following question: Assume the vertices of an expander graph are labelled by ± 1. What "test" functions f : {±1}^t → {±1} can or cannot distinguish t independent samples from those obtained by a random walk? [Gil Cohen et al., 2021] considered only balanced labellings, and proved that for all symmetric functions the distinguishability goes down to zero with the spectral gap λ of the expander G. In addition, [Gil Cohen et al., 2021] show that functions computable by AC⁰ circuits are fooled by expanders with vanishing spectral expansion. We continue the study of this question. We generalize the result to all labelling, not merely balanced ones. We also improve the upper bound on the error of symmetric functions. More importantly, we give a matching lower bound and show a symmetric function with distinguishability going down to zero with λ but not with t. Moreover, we prove a lower bound on the error of functions in AC⁰ in particular, we prove that a random walk on expanders with constant spectral gap does not fool AC⁰.

Cite as

Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma. Expander Random Walks: The General Case and Limitations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.43,
  author =	{Cohen, Gil and Minzer, Dor and Peleg, Shir and Potechin, Aaron and Ta-Shma, Amnon},
  title =	{{Expander Random Walks: The General Case and Limitations}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.43},
  URN =		{urn:nbn:de:0030-drops-163849},
  doi =		{10.4230/LIPIcs.ICALP.2022.43},
  annote =	{Keywords: Expander Graphs, Random Walks, Lower Bounds}
}
Document
Track A: Algorithms, Complexity and Games
LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation

Authors: Gil Cohen and Tal Yankovitz

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
The Alon-Edmonds-Luby distance amplification procedure (FOCS 1995) is an algorithm that transforms a code with vanishing distance to a code with constant distance. AEL was invoked by Kopparty, Meir, Ron-Zewi, and Saraf (J. ACM 2017) for obtaining their state-of-the-art LDC, LCC and LTC. Cohen and Yankovitz (CCC 2021) devised a procedure that can amplify inverse-polynomial distances, exponentially extending the regime of distances that can be amplified by AEL. However, the improved procedure only works for LDC and assuming rate 1-1/(poly log n). In this work we devise a distance amplification procedure for LCC with inverse-polynomial distances even for vanishing rate 1/(poly log log n). For LDC, we obtain a more modest improvement and require rate 1-1/(poly log log n). Thus, the tables have turned and it is now LCC that can be better amplified. Our key idea for accomplishing this, deviating from prior work, is to tailor the distance amplification procedure to the code at hand. Our second result concerns the relation between linear LDC and LCC. We prove the existence of linear LDC that are not LCC, qualitatively extending a separation by Kaufman and Viderman (RANDOM 2010).

Cite as

Gil Cohen and Tal Yankovitz. LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 44:1-44:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.44,
  author =	{Cohen, Gil and Yankovitz, Tal},
  title =	{{LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{44:1--44:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.44},
  URN =		{urn:nbn:de:0030-drops-163858},
  doi =		{10.4230/LIPIcs.ICALP.2022.44},
  annote =	{Keywords: Locally Correctable Codes, Locally Decodable Codes, Distance Amplifications}
}
Document
Track A: Algorithms, Complexity and Games
One-Pass Additive-Error Subset Selection for 𝓁_p Subspace Approximation

Authors: Amit Deshpande and Rameshwar Pratap

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
We consider the problem of subset selection for 𝓁_p subspace approximation, that is, to efficiently find a small subset of data points such that solving the problem optimally for this subset gives a good approximation to solving the problem optimally for the original input. Previously known subset selection algorithms based on volume sampling and adaptive sampling [Deshpande and Varadarajan, 2007], for the general case of p ∈ [1, ∞), require multiple passes over the data. In this paper, we give a one-pass subset selection with an additive approximation guarantee for 𝓁_p subspace approximation, for any p ∈ [1, ∞). Earlier subset selection algorithms that give a one-pass multiplicative (1+ε) approximation work under the special cases. Cohen et al. [Michael B. Cohen et al., 2017] gives a one-pass subset section that offers multiplicative (1+ε) approximation guarantee for the special case of 𝓁₂ subspace approximation. Mahabadi et al. [Sepideh Mahabadi et al., 2020] gives a one-pass noisy subset selection with (1+ε) approximation guarantee for 𝓁_p subspace approximation when p ∈ {1, 2}. Our subset selection algorithm gives a weaker, additive approximation guarantee, but it works for any p ∈ [1, ∞).

Cite as

Amit Deshpande and Rameshwar Pratap. One-Pass Additive-Error Subset Selection for 𝓁_p Subspace Approximation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{deshpande_et_al:LIPIcs.ICALP.2022.51,
  author =	{Deshpande, Amit and Pratap, Rameshwar},
  title =	{{One-Pass Additive-Error Subset Selection for 𝓁\underlinep Subspace Approximation}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{51:1--51:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.51},
  URN =		{urn:nbn:de:0030-drops-163924},
  doi =		{10.4230/LIPIcs.ICALP.2022.51},
  annote =	{Keywords: Subspace approximation, streaming algorithms, low-rank approximation, adaptive sampling, volume sampling, subset selection}
}
Document
Track A: Algorithms, Complexity and Games
Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions

Authors: Ming Ding, Rasmus Kyng, and Peng Zhang

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
We give a nearly-linear time reduction that encodes any linear program as a 2-commodity flow problem with only a small blow-up in size. Under mild assumptions similar to those employed by modern fast solvers for linear programs, our reduction causes only a polylogarithmic multiplicative increase in the size of the program, and runs in nearly-linear time. Our reduction applies to high-accuracy approximation algorithms and exact algorithms. Given an approximate solution to the 2-commodity flow problem, we can extract a solution to the linear program in linear time with only a polynomial factor increase in the error. This implies that any algorithm that solves the 2-commodity flow problem can solve linear programs in essentially the same time. Given a directed graph with edge capacities and two source-sink pairs, the goal of the 2-commodity flow problem is to maximize the sum of the flows routed between the two source-sink pairs subject to edge capacities and flow conservation. A 2-commodity flow problem can be formulated as a linear program, which can be solved to high accuracy in almost the current matrix multiplication time (Cohen-Lee-Song JACM'21). Our reduction shows that linear programs can be approximately solved, to high accuracy, using 2-commodity flow as well. Our proof follows the outline of Itai’s polynomial-time reduction of a linear program to a 2-commodity flow problem (JACM’78). Itai’s reduction shows that exactly solving 2-commodity flow and exactly solving linear programming are polynomial-time equivalent. We improve Itai’s reduction to nearly preserve the problem representation size in each step. In addition, we establish an error bound for approximately solving each intermediate problem in the reduction, and show that the accumulated error is polynomially bounded. We remark that our reduction does not run in strongly polynomial time and that it is open whether 2-commodity flow and linear programming are equivalent in strongly polynomial time.

Cite as

Ming Ding, Rasmus Kyng, and Peng Zhang. Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 54:1-54:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ding_et_al:LIPIcs.ICALP.2022.54,
  author =	{Ding, Ming and Kyng, Rasmus and Zhang, Peng},
  title =	{{Two-Commodity Flow Is Equivalent to Linear Programming Under Nearly-Linear Time Reductions}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{54:1--54:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.54},
  URN =		{urn:nbn:de:0030-drops-163950},
  doi =		{10.4230/LIPIcs.ICALP.2022.54},
  annote =	{Keywords: Two-Commodity Flow Problems, Linear Programming, Fine-Grained Complexity}
}
Document
RANDOM
Better Pseudodistributions and Derandomization for Space-Bounded Computation

Authors: William M. Hoza

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


Abstract
Three decades ago, Nisan constructed an explicit pseudorandom generator (PRG) that fools width-n length-n read-once branching programs (ROBPs) with error ε and seed length O(log² n + log n ⋅ log(1/ε)) [Nisan, 1992]. Nisan’s generator remains the best explicit PRG known for this important model of computation. However, a recent line of work starting with Braverman, Cohen, and Garg [Braverman et al., 2020; Chattopadhyay and Liao, 2020; Cohen et al., 2021; Pyne and Vadhan, 2021] has shown how to construct weighted pseudorandom generators (WPRGs, aka pseudorandom pseudodistribution generators) with better seed lengths than Nisan’s generator when the error parameter ε is small. In this work, we present an explicit WPRG for width-n length-n ROBPs with seed length O(log² n + log(1/ε)). Our seed length eliminates log log factors from prior constructions, and our generator completes this line of research in the sense that further improvements would require beating Nisan’s generator in the standard constant-error regime. Our technique is a variation of a recently-discovered reduction that converts moderate-error PRGs into low-error WPRGs [Cohen et al., 2021; Pyne and Vadhan, 2021]. Our version of the reduction uses averaging samplers. We also point out that as a consequence of the recent work on WPRGs, any randomized space-S decision algorithm can be simulated deterministically in space O (S^{3/2} / √{log S}). This is a slight improvement over Saks and Zhou’s celebrated O(S^{3/2}) bound [Saks and Zhou, 1999]. For this application, our improved WPRG is not necessary.

Cite as

William M. Hoza. Better Pseudodistributions and Derandomization for Space-Bounded Computation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 28:1-28:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{hoza:LIPIcs.APPROX/RANDOM.2021.28,
  author =	{Hoza, William M.},
  title =	{{Better Pseudodistributions and Derandomization for Space-Bounded Computation}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{28:1--28:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.28},
  URN =		{urn:nbn:de:0030-drops-147217},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.28},
  annote =	{Keywords: Weighted pseudorandom generator, pseudorandom pseudodistribution, read-once branching program, derandomization, space complexity}
}
Document
Budgeted Dominating Sets in Uncertain Graphs

Authors: Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy, David Peleg, and R. Vijayaragunathan

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)


Abstract
We study the Budgeted Dominating Set (BDS) problem on uncertain graphs, namely, graphs with a probability distribution p associated with the edges, such that an edge e exists in the graph with probability p(e). The input to the problem consists of a vertex-weighted uncertain graph 𝒢 = (V, E, p, ω) and an integer budget (or solution size) k, and the objective is to compute a vertex set S of size k that maximizes the expected total domination (or total weight) of vertices in the closed neighborhood of S. We refer to the problem as the Probabilistic Budgeted Dominating Set (PBDS) problem. In this article, we present the following results on the complexity of the PBDS problem. 1) We show that the PBDS problem is NP-complete even when restricted to uncertain trees of diameter at most four. This is in sharp contrast with the well-known fact that the BDS problem is solvable in polynomial time in trees. We further show that PBDS is 𝖶[1]-hard for the budget parameter k, and under the Exponential time hypothesis it cannot be solved in n^o(k) time. 2) We show that if one is willing to settle for (1-ε) approximation, then there exists a PTAS for PBDS on trees. Moreover, for the scenario of uniform edge-probabilities, the problem can be solved optimally in polynomial time. 3) We consider the parameterized complexity of the PBDS problem, and show that Uni-PBDS (where all edge probabilities are identical) is 𝖶[1]-hard for the parameter pathwidth. On the other hand, we show that it is FPT in the combined parameters of the budget k and the treewidth. 4) Finally, we extend some of our parameterized results to planar and apex-minor-free graphs. Our first hardness proof (Thm. 1) makes use of the new problem of k-Subset Σ-Π Maximization (k-SPM), which we believe is of independent interest. We prove its NP-hardness by a reduction from the well-known k-SUM problem, presenting a close relationship between the two problems.

Cite as

Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy, David Peleg, and R. Vijayaragunathan. Budgeted Dominating Sets in Uncertain Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.MFCS.2021.32,
  author =	{Choudhary, Keerti and Cohen, Avi and Narayanaswamy, N. S. and Peleg, David and Vijayaragunathan, R.},
  title =	{{Budgeted Dominating Sets in Uncertain Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{32:1--32:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.32},
  URN =		{urn:nbn:de:0030-drops-144723},
  doi =		{10.4230/LIPIcs.MFCS.2021.32},
  annote =	{Keywords: Uncertain graphs, Dominating set, NP-hard, PTAS, treewidth, planar graph}
}
Document
Value-Oriented Legal Argumentation in Isabelle/HOL

Authors: Christoph Benzmüller and David Fuenmayor

Published in: LIPIcs, Volume 193, 12th International Conference on Interactive Theorem Proving (ITP 2021)


Abstract
Literature in AI & Law contemplates argumentation in legal cases as an instance of theory construction. The task of a lawyer in a legal case is to construct a theory containing: (a) relevant generic facts about the world, (b) relevant legal rules such as precedents and statutes, and (c) contingent facts describing or interpreting the situation at hand. Lawyers then elaborate convincing arguments starting from these facts and rules, deriving into a positive decision in favour of their client, often employing sophisticated argumentation techniques involving such notions as burden of proof, stare decisis, legal balancing, etc. In this paper we exemplarily show how to harness Isabelle/HOL to model lawyer’s argumentation using value-oriented legal balancing, while drawing upon shallow embeddings of combinations of expressive modal logics in HOL. We highlight the essential role of model finders (Nitpick) and "hammers" (Sledgehammer) in assisting the task of legal theory construction and share some thoughts on the practicability of extending the catalogue of ITP applications towards legal informatics.

Cite as

Christoph Benzmüller and David Fuenmayor. Value-Oriented Legal Argumentation in Isabelle/HOL. In 12th International Conference on Interactive Theorem Proving (ITP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 193, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{benzmuller_et_al:LIPIcs.ITP.2021.7,
  author =	{Benzm\"{u}ller, Christoph and Fuenmayor, David},
  title =	{{Value-Oriented Legal Argumentation in Isabelle/HOL}},
  booktitle =	{12th International Conference on Interactive Theorem Proving (ITP 2021)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-188-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{193},
  editor =	{Cohen, Liron and Kaliszyk, Cezary},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2021.7},
  URN =		{urn:nbn:de:0030-drops-139028},
  doi =		{10.4230/LIPIcs.ITP.2021.7},
  annote =	{Keywords: Higher order logic, preference logic, shallow embedding, legal reasoning}
}
Document
Verified Progress Tracking for Timely Dataflow

Authors: Matthias Brun, Sára Decova, Andrea Lattuada, and Dmitriy Traytel

Published in: LIPIcs, Volume 193, 12th International Conference on Interactive Theorem Proving (ITP 2021)


Abstract
Large-scale stream processing systems often follow the dataflow paradigm, which enforces a program structure that exposes a high degree of parallelism. The Timely Dataflow distributed system supports expressive cyclic dataflows for which it offers low-latency data- and pipeline-parallel stream processing. To achieve high expressiveness and performance, Timely Dataflow uses an intricate distributed protocol for tracking the computation’s progress. We modeled the progress tracking protocol as a combination of two independent transition systems in the Isabelle/HOL proof assistant. We specified and verified the safety of the two components and of the combined protocol. To this end, we identified abstract assumptions on dataflow programs that are sufficient for safety and were not previously formalized.

Cite as

Matthias Brun, Sára Decova, Andrea Lattuada, and Dmitriy Traytel. Verified Progress Tracking for Timely Dataflow. In 12th International Conference on Interactive Theorem Proving (ITP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 193, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{brun_et_al:LIPIcs.ITP.2021.10,
  author =	{Brun, Matthias and Decova, S\'{a}ra and Lattuada, Andrea and Traytel, Dmitriy},
  title =	{{Verified Progress Tracking for Timely Dataflow}},
  booktitle =	{12th International Conference on Interactive Theorem Proving (ITP 2021)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-188-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{193},
  editor =	{Cohen, Liron and Kaliszyk, Cezary},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2021.10},
  URN =		{urn:nbn:de:0030-drops-139057},
  doi =		{10.4230/LIPIcs.ITP.2021.10},
  annote =	{Keywords: safety, distributed systems, timely dataflow, Isabelle/HOL}
}
Document
Specifying Message Formats with Contiguity Types

Authors: Konrad Slind

Published in: LIPIcs, Volume 193, 12th International Conference on Interactive Theorem Proving (ITP 2021)


Abstract
We introduce Contiguity Types, a formalism for network message formats, aimed especially at self-describing formats. Contiguity types provide an intermediate layer between programming language data structures and messages, offering a helpful setting from which to automatically generate decoders, filters, and message generators. The syntax and semantics of contiguity types are defined and used to prove the correctness of a matching algorithm which has the flavour of a parser generator. The matcher has been used to enforce semantic well-formedness conditions on complex message formats for an autonomous unmanned avionics system.

Cite as

Konrad Slind. Specifying Message Formats with Contiguity Types. In 12th International Conference on Interactive Theorem Proving (ITP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 193, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{slind:LIPIcs.ITP.2021.30,
  author =	{Slind, Konrad},
  title =	{{Specifying Message Formats with Contiguity Types}},
  booktitle =	{12th International Conference on Interactive Theorem Proving (ITP 2021)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-188-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{193},
  editor =	{Cohen, Liron and Kaliszyk, Cezary},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2021.30},
  URN =		{urn:nbn:de:0030-drops-139252},
  doi =		{10.4230/LIPIcs.ITP.2021.30},
  annote =	{Keywords: Logic, verification, formal language theory, message format languages}
}
  • Refine by Author
  • 3 Choudhary, Keerti
  • 3 Hoza, William M.
  • 2 Cohen, Albert
  • 2 Cohen, Avi
  • 2 Cohen, Gil
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Pseudorandomness and derandomization
  • 3 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Complexity classes
  • 1 Computing methodologies → Dimensionality reduction and manifold learning
  • 1 Computing methodologies → Distributed algorithms
  • Show More...

  • Refine by Keyword
  • 2 derandomization
  • 2 space complexity
  • 1 AC⁰ circuits
  • 1 Agda
  • 1 Approximation Algorithms
  • Show More...

  • Refine by Type
  • 31 document

  • Refine by Publication Year
  • 8 2022
  • 5 2021
  • 3 2008
  • 3 2018
  • 3 2019
  • Show More...

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