71 Search Results for "Simon, Sunil"

Volume

LIPIcs, Volume 182

40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

FSTTCS 2020, December 14-18, 2020, BITS Pilani, K K Birla Goa Campus, Goa, India (Virtual Conference)

Editors: Nitin Saxena and Sunil Simon

Document
DOI: 10.4230/LIPIcs.ITP.2025.14
Canonical for Automated Theorem Proving in Lean

Authors: Chase Norman and Jeremy Avigad

Published in: LIPIcs, Volume 352, 16th International Conference on Interactive Theorem Proving (ITP 2025)

Abstract
Canonical is a solver for type inhabitation in dependent type theory, that is, the problem of producing a term of a given type. We present a Lean tactic which invokes Canonical to generate proof terms and synthesize programs. The tactic supports higher-order and dependently-typed goals, structural recursion over indexed inductive types, and definitional equality. Canonical finds proofs for 84% of Natural Number Game problems in 51 seconds total.
Cite as

Chase Norman and Jeremy Avigad. Canonical for Automated Theorem Proving in Lean. In 16th International Conference on Interactive Theorem Proving (ITP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 352, pp. 14:1-14:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{norman_et_al:LIPIcs.ITP.2025.14,
  author =	{Norman, Chase and Avigad, Jeremy},
  title =	{{Canonical for Automated Theorem Proving in Lean}},
  booktitle =	{16th International Conference on Interactive Theorem Proving (ITP 2025)},
  pages =	{14:1--14:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-396-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{352},
  editor =	{Forster, Yannick and Keller, Chantal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2025.14},
  URN =		{urn:nbn:de:0030-drops-246128},
  doi =		{10.4230/LIPIcs.ITP.2025.14},
  annote =	{Keywords: Automated Reasoning, Interactive Theorem Proving, Dependent Type Theory, Inhabitation, Unification, Program Synthesis, Formal Methods}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.13
Solving Partial Dominating Set and Related Problems Using Twin-Width

Authors: Jakub Balabán, Daniel Mock, and Peter Rossmanith

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are W[1]-hard on general graphs, they have been shown to be fixed-parameter tractable on many sparse graph classes, including nowhere-dense classes. In this paper, we demonstrate that these problems are also fixed-parameter tractable with respect to the twin-width of a graph. Indeed, we establish a more general result: every graph property that can be expressed by a logical formula of the form ϕ≡∃ x₁⋯ ∃ x_k ∑_{α ∈ I} #y ψ_α(x₁,…,x_k,y) ≥ t, where ψ_α is a quantifier-free formula for each α ∈ I, t is an arbitrary number, and #y is a counting quantifier, can be evaluated in time f(d,k)n, where n is the number of vertices and d is the width of a contraction sequence that is part of the input. In addition to the aforementioned problems, this includes also connected partial dominating set and independent partial dominating set.
Cite as

Jakub Balabán, Daniel Mock, and Peter Rossmanith. Solving Partial Dominating Set and Related Problems Using Twin-Width. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.MFCS.2025.13,
  author =	{Balab\'{a}n, Jakub and Mock, Daniel and Rossmanith, Peter},
  title =	{{Solving Partial Dominating Set and Related Problems Using Twin-Width}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.13},
  URN =		{urn:nbn:de:0030-drops-241203},
  doi =		{10.4230/LIPIcs.MFCS.2025.13},
  annote =	{Keywords: Partial Dominating Set, Partial Vertex Cover, meta-algorithm, counting logic, twin-width}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.79
Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space

Authors: Eike Neumann

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the problem of deciding whether a point escapes a closed subset of ℝ^d under the iteration of a continuous map f : ℝ^d → ℝ^d in the bit-model of real computation. We give a sound partial decision method for this problem which is complete in the sense that its halting set contains the halting set of all sound partial decision methods for the problem. Equivalently, our decision method terminates on all problem instances whose answer is robust under all sufficiently small perturbations of the function. We further show that the halting set of our algorithm is dense in the set of all problem instances. While our algorithm applies to general continuous functions, we demonstrate that it also yields complete decision methods for much more rigid function families: affine linear systems and quadratic complex polynomials. In the latter case, completeness is subject to the density of hyperbolicity conjecture in complex dynamics. This in particular yields an alternative proof of Hertling’s (2004) conditional answer to a question raised by Penrose (1989) regarding the computability of the Mandelbrot set.
Cite as

Eike Neumann. Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 79:1-79:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{neumann:LIPIcs.MFCS.2025.79,
  author =	{Neumann, Eike},
  title =	{{Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{79:1--79:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.79},
  URN =		{urn:nbn:de:0030-drops-241866},
  doi =		{10.4230/LIPIcs.MFCS.2025.79},
  annote =	{Keywords: Dynamical Systems, Computability in Analysis, Non-Linear Functions}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.21
On the Performance of Mildly Greedy Players in k-Coloring Games

Authors: Vittorio Bilò, Andrea D'Ascenzo, Mattia D'Emidio, and Giuseppe F. Italiano

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the performance of mildly greedy players in k-coloring games, a relevant subclass of anti-coordination games. A mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than ε, for some given ε ≥ 0. In presence of mildly greedy players, stability is captured by the concept of (1+ε)-approximate Nash equilibrium. In this paper, we first show that, for any k-coloring game, the (1+ε)-approximate price of anarchy, i.e., the price of anarchy of (1+ε)-approximate pure Nash equilibria, is at least (k-1)/((k-1)ε +k), and that this bound is tight for any ε ≥ 0. Then, we evaluate the approximation ratio of the solutions achieved after a (1 + ϵ)-approximate one-round walk starting from any initial strategy profile, where a (1 + ϵ)-approximate one-round walk is a sequence of (1 + ε)-approximate best-responses, one for each player. We provide a lower bound of min{(k-2)/k, (k-1)/((k-1)ε+k)} on this ratio, for any ε ≥ 0 and k ≥ 5; for the cases of k = 3 and k = 4, we give finer bounds depending on ε. Our work generalizes the results known for cut games, the special case of k-coloring games restricted to k = 2.
Cite as

Vittorio Bilò, Andrea D'Ascenzo, Mattia D'Emidio, and Giuseppe F. Italiano. On the Performance of Mildly Greedy Players in k-Coloring Games. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bilo_et_al:LIPIcs.MFCS.2025.21,
  author =	{Bil\`{o}, Vittorio and D'Ascenzo, Andrea and D'Emidio, Mattia and Italiano, Giuseppe F.},
  title =	{{On the Performance of Mildly Greedy Players in k-Coloring Games}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.21},
  URN =		{urn:nbn:de:0030-drops-241287},
  doi =		{10.4230/LIPIcs.MFCS.2025.21},
  annote =	{Keywords: Coloring games, (Approximate) Nash Equilibria, Price of Anarchy}
}
Document
DOI: 10.4230/LIPIcs.WABI.2025.11
Mutational Signature Refitting on Sparse Pan-Cancer Data

Authors: Gal Gilad, Teresa M. Przytycka, and Roded Sharan

Published in: LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025)

Abstract
Mutational processes shape cancer genomes, leaving characteristic marks that are termed signatures. The level of activity of each such process, or its signature exposure, provides important information on the disease, improving patient stratification and the prediction of drug response. Thus, there is growing interest in developing refitting methods that decipher those exposures. Previous work in this domain was unsupervised in nature, employing algebraic decomposition and probabilistic inference methods. Here we provide a supervised approach to the problem of signature refitting and show its superiority over current methods. Our method, SuRe, leverages a neural network model to capture correlations between signature exposures in real data. We show that SuRe outperforms previous methods on sparse mutation data from tumor type specific data sets, as well as pan-cancer data sets, with an increasing advantage as the data become sparser. We further demonstrate its utility in clinical settings.
Cite as

Gal Gilad, Teresa M. Przytycka, and Roded Sharan. Mutational Signature Refitting on Sparse Pan-Cancer Data. In 25th International Conference on Algorithms for Bioinformatics (WABI 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 344, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gilad_et_al:LIPIcs.WABI.2025.11,
  author =	{Gilad, Gal and Przytycka, Teresa M. and Sharan, Roded},
  title =	{{Mutational Signature Refitting on Sparse Pan-Cancer Data}},
  booktitle =	{25th International Conference on Algorithms for Bioinformatics (WABI 2025)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-386-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{344},
  editor =	{Brejov\'{a}, Bro\v{n}a and Patro, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.11},
  URN =		{urn:nbn:de:0030-drops-239374},
  doi =		{10.4230/LIPIcs.WABI.2025.11},
  annote =	{Keywords: mutational signatures, signature refitting, cancer genomics, genomic data analysis, somatic mutations}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.106
Streaming Maximal Matching with Bounded Deletions

Authors: Sanjeev Khanna, Christian Konrad, and Jacques Dark

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

Abstract
We initiate the study of the Maximal Matching problem in bounded-deletion graph streams. In this setting, a graph G is revealed as an arbitrary sequence of edge insertions and deletions, where the number of insertions is unrestricted but the number of deletions is guaranteed to be at most K, for some given parameter K. The single-pass streaming space complexity of this problem is known to be Θ(n²) when K is unrestricted, where n is the number of vertices of the input graph. In this work, we present new randomized and deterministic algorithms and matching lower bound results that together give a tight understanding (up to poly-log factors) of how the space complexity of Maximal Matching evolves as a function of the parameter K: The randomized space complexity of this problem is Θ̃(n ⋅ √K), while the deterministic space complexity is Θ̃(n ⋅ K). We further show that if we relax the maximal matching requirement to an α-approximation to Maximum Matching, for any constant α > 2, then the space complexity for both, deterministic and randomized algorithms, strikingly changes to Θ̃(n + K). A key conceptual contribution of our work that underlies all our algorithmic results is the introduction of the hierarchical maximal matching data structure, which computes a hierarchy of L maximal matchings on the substream of edge insertions, for an integer L. This deterministic data structure allows recovering a Maximal Matching even in the presence of up to L-1 edge deletions, which immediately yields an optimal deterministic algorithm with space Õ(n ⋅ K). To reduce the space to Õ(n ⋅ √K), we compute only √K levels of our hierarchical matching data structure and utilize a randomized linear sketch, i.e., our matching repair data structure, to repair any damage due to edge deletions. Using our repair data structure, we show that the level that is least affected by deletions can be repaired back to be globally maximal. The repair data structure is computed independently of the hierarchical maximal matching data structure and stores information for vertices at different scales with a gradually smaller set of vertices storing more and more information about their incident edges. The repair process then makes progress either by rematching a vertex to a previously unmatched vertex, or by strategically matching it to another matched vertex whose current mate is in a better position to find a new mate in that we have stored more information about its incident edges. Our lower bound result for randomized algorithms is obtained by establishing a lower bound for a generalization of the well-known Augmented-Index problem in the one-way two-party communication setting that we refer to as Embedded-Augmented-Index, and then showing that an instance of Embedded-Augmented-Index reduces to computing a maximal matching in bounded-deletion streams. To obtain our lower bound for deterministic algorithms, we utilize a compression argument to show that a deterministic algorithm with space o(n ⋅ K) would yield a scheme to compress a suitable class of graphs below the information-theoretic threshold.
Cite as

Sanjeev Khanna, Christian Konrad, and Jacques Dark. Streaming Maximal Matching with Bounded Deletions. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 106:1-106:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.ICALP.2025.106,
  author =	{Khanna, Sanjeev and Konrad, Christian and Dark, Jacques},
  title =	{{Streaming Maximal Matching with Bounded Deletions}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{106:1--106: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.106},
  URN =		{urn:nbn:de:0030-drops-234834},
  doi =		{10.4230/LIPIcs.ICALP.2025.106},
  annote =	{Keywords: Streaming Algorithms, Maximal Matching, Maximum Matching, Bounded-Deletion Streams}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.100
Robust-Sorting and Applications to Ulam-Median

Authors: Ragesh Jaiswal, Amit Kumar, and Jatin Yadav

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

Abstract
Sorting is one of the most basic primitives in many algorithms and data analysis tasks. Comparison-based sorting algorithms, like quick-sort and merge-sort, are known to be optimal when the outcome of each comparison is error-free. However, many real-world sorting applications operate in scenarios where the outcome of each comparison can be noisy. In this work, we explore settings where a bounded number of comparisons are potentially corrupted by erroneous agents, resulting in arbitrary, adversarial outcomes. We model the sorting problem as a query-limited tournament graph where edges involving erroneous nodes may yield arbitrary results. Our primary contribution is a randomized algorithm inspired by quick-sort that, in expectation, produces an ordering close to the true total order while only querying Õ(n) edges. We achieve a distance from the target order π within (3 + ε)|B|, where B is the set of erroneous nodes, balancing the competing objectives of minimizing both query complexity and misalignment with π. Our algorithm needs to carefully balance two aspects - identify a pivot that partitions the vertex set evenly and ensure that this partition is "truthful" and yet query as few "triangles" in the graph G as possible. Since the nodes in B can potentially hide in an intricate manner, our algorithm requires several technical steps that ensure that progress is made in each recursive step. Additionally, we demonstrate significant implications for the Ulam-k-Median problem. This is a classical clustering problem where the metric is defined on the set of permutations on a set of d elements. Chakraborty, Das, and Krauthgamer gave a (2-ε) FPT approximation algorithm for this problem, where the running time is super-linear in both n and d. We give the first (2-ε) FPT linear time approximation algorithm for this problem. Our main technical result gives a strengthening of the results in Chakraborty et al. by showing that a good 1-median solution can be obtained from a constant-size random sample of the input. We use our robust sorting framework to find a good solution from such a random sample. We feel that the notion of robust sorting should have applications in several such settings.
Cite as

Ragesh Jaiswal, Amit Kumar, and Jatin Yadav. Robust-Sorting and Applications to Ulam-Median. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 100:1-100:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jaiswal_et_al:LIPIcs.ICALP.2025.100,
  author =	{Jaiswal, Ragesh and Kumar, Amit and Yadav, Jatin},
  title =	{{Robust-Sorting and Applications to Ulam-Median}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{100:1--100:19},
  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.100},
  URN =		{urn:nbn:de:0030-drops-234774},
  doi =		{10.4230/LIPIcs.ICALP.2025.100},
  annote =	{Keywords: Sorting, clustering, query complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.27
Computing Oriented Spanners and Their Dilation

Authors: Kevin Buchin, Antonia Kalb, Anil Maheshwari, Saeed Odak, Carolin Rehs, Michiel Smid, and Sampson Wong

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Given a point set P in a metric space and a real number t ≥ 1, an oriented t-spanner is an oriented graph G = (P, E), where for every pair of distinct points p and q in P, the shortest oriented closed walk in G that contains p and q is at most a factor t longer than the perimeter of the smallest triangle in P containing p and q. The oriented dilation of a graph G is the minimum t for which G is an oriented t-spanner. For arbitrary point sets of size n in ℝ^d, where d ≥ 2 is a constant, the only known oriented spanner construction is an oriented 2-spanner with binom(n,2) edges. Moreover, there exists a set P of four points in the plane, for which the oriented dilation is larger than 1.46, for any oriented graph on P. We present the first algorithm that computes, in Euclidean space, a sparse oriented spanner whose oriented dilation is bounded by a constant. More specifically, for any set of n points in ℝ^d, where d is a constant, we construct an oriented (2+ε)-spanner with 𝒪(n) edges in 𝒪(n log n) time and 𝒪(n) space. Our construction uses the well-separated pair decomposition and an algorithm that computes a (1+ε)-approximation of the minimum-perimeter triangle in P containing two given query points in 𝒪(log n) time. While our algorithm is based on first computing a suitable undirected graph and then orienting it, we show that, in general, computing the orientation of an undirected graph that minimises its oriented dilation is NP-hard, even for point sets in the Euclidean plane. We further prove that even if the oriented graph is already given, computing its oriented dilation is APSP-hard for points in a general metric space. We complement this result with an algorithm that approximates the oriented dilation of a given graph in subcubic time for point sets in ℝ^d, where d is a constant.
Cite as

Kevin Buchin, Antonia Kalb, Anil Maheshwari, Saeed Odak, Carolin Rehs, Michiel Smid, and Sampson Wong. Computing Oriented Spanners and Their Dilation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2025.27,
  author =	{Buchin, Kevin and Kalb, Antonia and Maheshwari, Anil and Odak, Saeed and Rehs, Carolin and Smid, Michiel and Wong, Sampson},
  title =	{{Computing Oriented Spanners and Their Dilation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.27},
  URN =		{urn:nbn:de:0030-drops-231792},
  doi =		{10.4230/LIPIcs.SoCG.2025.27},
  annote =	{Keywords: spanner, oriented graph, dilation, orientation, well-separated pair decomposition, minimum-perimeter triangle}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.66
Graph Reconstruction via MIS Queries

Authors: Christian Konrad, Conor O'Sullivan, and Victor Traistaru

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In the Graph Reconstruction (GR) problem, a player initially only knows the vertex set V of an input graph G = (V, E) and is required to learn its set of edges E. To this end, the player submits queries to an oracle and must deduce E from the oracle’s answers. Angluin and Chen [Journal of Computer and System Sciences, 2008] resolved the number of Independent Set (IS) queries necessary and sufficient for GR on m-edge graphs. In this setting, each query consists of a subset of vertices U ⊆ V, and the oracle responds with a boolean, indicating whether U is an independent set in G. They gave algorithms that use O(m ⋅ log n) IS queries, which is best possible. In this paper, we initiate the study of GR via Maximal Independent Set (MIS) queries, a more powerful variant of IS queries. Given a query U ⊆ V, the oracle responds with any, potentially adversarially chosen, maximal independent set I ⊆ U in the induced subgraph G[U]. We show that, for GR, MIS queries are strictly more powerful than IS queries when parametrized by the maximum degree Δ of the input graph. We give tight (up to poly-logarithmic factors) upper and lower bounds for this problem: 1) We observe that the simple strategy of taking uniform independent random samples of V and submitting those to the oracle yields a non-adaptive randomized algorithm that executes O(Δ² ⋅ log n) queries and succeeds with high probability. This should be contrasted with the fact that Ω(Δ ⋅ n ⋅ log(n/Δ)) IS queries are required for such graphs, which shows that MIS queries are strictly more powerful than IS queries. Interestingly, combining the strategy of taking uniform random samples of V with the probabilistic method, we show the existence of a deterministic non-adaptive algorithm that executes O(Δ³ ⋅ log(n/Δ)) queries. 2) Regarding lower bounds, we prove that the additional Δ factor when going from randomized non-adaptive algorithms to deterministic non-adaptive algorithms is necessary. We show that every non-adaptive deterministic algorithm requires Ω(Δ³ / log² Δ) queries. For arbitrary randomized adaptive algorithms, we show that Ω(Δ²) queries are necessary in graphs of maximum degree Δ, and that Ω(log n) queries are necessary, even when the input graph is an n-vertex cycle.
Cite as

Christian Konrad, Conor O'Sullivan, and Victor Traistaru. Graph Reconstruction via MIS Queries. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 66:1-66:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{konrad_et_al:LIPIcs.ITCS.2025.66,
  author =	{Konrad, Christian and O'Sullivan, Conor and Traistaru, Victor},
  title =	{{Graph Reconstruction via MIS Queries}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{66:1--66:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.66},
  URN =		{urn:nbn:de:0030-drops-226945},
  doi =		{10.4230/LIPIcs.ITCS.2025.66},
  annote =	{Keywords: Query Complexity, Graph Reconstruction, Maximal Independent Set Queries}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.FSTTCS.2020
LIPIcs, Volume 182, FSTTCS 2020, Complete Volume

Authors: Nitin Saxena and Sunil Simon

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
LIPIcs, Volume 182, FSTTCS 2020, Complete Volume
Cite as

40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 1-912, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{saxena_et_al:LIPIcs.FSTTCS.2020,
  title =	{{LIPIcs, Volume 182, FSTTCS 2020, Complete Volume}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{1--912},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020},
  URN =		{urn:nbn:de:0030-drops-132401},
  doi =		{10.4230/LIPIcs.FSTTCS.2020},
  annote =	{Keywords: LIPIcs, Volume 182, FSTTCS 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.FSTTCS.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Nitin Saxena and Sunil Simon

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{saxena_et_al:LIPIcs.FSTTCS.2020.0,
  author =	{Saxena, Nitin and Simon, Sunil},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.0},
  URN =		{urn:nbn:de:0030-drops-132413},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2020.1
The Quest for Mathematical Understanding of Deep Learning (Invited Talk)

Authors: Sanjeev Arora

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
Deep learning has transformed Machine Learning and Artificial Intelligence in the past decade. It raises fundamental questions for mathematics and theory of computer science, since it relies upon solving large-scale nonconvex problems via gradient descent and its variants. This talk will be an introduction to mathematical questions raised by deep learning, and some partial understanding obtained in recent years.
Cite as

Sanjeev Arora. The Quest for Mathematical Understanding of Deep Learning (Invited Talk). In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arora:LIPIcs.FSTTCS.2020.1,
  author =	{Arora, Sanjeev},
  title =	{{The Quest for Mathematical Understanding of Deep Learning}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.1},
  URN =		{urn:nbn:de:0030-drops-132427},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.1},
  annote =	{Keywords: machine learning, artificial intelligence, deep learning, gradient descent, optimization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2020.2
Proofs of Soundness and Proof Search (Invited Talk)

Authors: Albert Atserias

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
Let P be a sound proof system for propositional logic. For each CNF formula F, let SAT(F) be a CNF formula whose satisfying assignments are in 1-to-1 correspondence with those of F (e.g., F itself). For each integer s, let REF(F,s) be a CNF formula whose satisfying assignments are in 1-to-1 correspondence with the P-refutations of F of length s. Since P is sound, it is obvious that the conjunction formula SAT(F) & REF(F,s) is unsatisfiable for any choice of F and s. It has been long known that, for many natural proof systems P and for the most natural formalizations of the formulas SAT and REF, the unsatisfiability of SAT(F) & REF(F,s) can be established by a short refutation. In addition, for many P, these short refutations live in the proof system P itself. This is the case for all Frege proof systems. In contrast it was known since the early 2000’s that Resolution proofs of Resolution’s soundness statements must have superpolynomial length. In this talk I will explain how the soundness formulas for a proof system P relate to the computational complexity of the proof search problem for P. In particular, I will explain how such formulas are used in the recent proof that the problem of approximating the minimum proof-length for Resolution is NP-hard (Atserias-Müller 2019). Besides playing a key role in this hardness of approximation result, the renewed interest in the soundness formulas led to a complete answer to the question whether Resolution has subexponential-length proofs of its own soundness statements (Garlík 2019).
Cite as

Albert Atserias. Proofs of Soundness and Proof Search (Invited Talk). In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{atserias:LIPIcs.FSTTCS.2020.2,
  author =	{Atserias, Albert},
  title =	{{Proofs of Soundness and Proof Search}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.2},
  URN =		{urn:nbn:de:0030-drops-132439},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.2},
  annote =	{Keywords: Proof complexity, automatability, Resolution, proof search, consistency statements, lower bounds, reflection principle, satisfiability}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2020.3
Convex Optimization and Dynamic Data Structure (Invited Talk)

Authors: Yin Tat Lee

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
In the last three years, there are many breakthroughs in optimization such as nearly quadratic time algorithms for bipartite matching, linear programming algorithms that are as fast as Ax = b. All of these algorithms are based on a careful combination of optimization techniques and dynamic data structures. In this talk, we will explain the framework underlying all the recent breakthroughs. Joint work with Jan van den Brand, Michael B. Cohen, Sally Dong, Haotian Jiang, Tarun Kathuria, Danupon Nanongkai, Swati Padmanabhan, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang, Sam Chiu-wai Wong, Guanghao Ye, Qiuyi Zhang.
Cite as

Yin Tat Lee. Convex Optimization and Dynamic Data Structure (Invited Talk). In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lee:LIPIcs.FSTTCS.2020.3,
  author =	{Lee, Yin Tat},
  title =	{{Convex Optimization and Dynamic Data Structure}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.3},
  URN =		{urn:nbn:de:0030-drops-132440},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.3},
  annote =	{Keywords: Convex Optimization, Dynamic Data Structure}
}
  • Refine by Type
  • 70 Document/PDF
  • 9 Document/HTML
  • 1 Volume

  • Refine by Publication Year
  • 9 2025
  • 61 2020
  • 1 2009

  • Refine by Author
  • 3 Konrad, Christian
  • 3 Kumar, Amit
  • 3 Saurabh, Saket
  • 3 Simon, Sunil
  • 3 Wolf, Petra
  • Show More...

  • Refine by Series/Journal
  • 70 LIPIcs

  • Refine by Classification
  • 7 Theory of computation → Logic and verification
  • 6 Theory of computation
  • 6 Theory of computation → Formal languages and automata theory
  • 5 Theory of computation → Design and analysis of algorithms
  • 4 Theory of computation → Automata over infinite objects
  • Show More...

  • Refine by Keyword
  • 2 Complexity
  • 2 Computational complexity
  • 2 Markov chains
  • 2 Price of Anarchy
  • 2 Static analysis
  • 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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact