11 Search Results for "Parthasarathy, Srinivasan"

Document
Research
DOI: 10.4230/TGDK.3.3.4
Mining Inter-Document Argument Structures in Scientific Papers for an Argument Web

Authors: Florian Ruosch, Cristina Sarasua, and Abraham Bernstein

Published in: TGDK, Volume 3, Issue 3 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 3

Abstract
In Argument Mining, predicting argumentative relations between texts (or spans) remains one of the most challenging aspects, even more so in the cross-document setting. This paper makes three key contributions to advance research in this domain. We first extend an existing dataset, the Sci-Arg corpus, by annotating it with explicit inter-document argumentative relations, thereby allowing arguments to be distributed over several documents forming an Argument Web; these new annotations are published using Semantic Web technologies (RDF, OWL). Second, we explore and evaluate three automated approaches for predicting these inter-document argumentative relations, establishing critical baselines on the new dataset. We find that a simple classifier based on discourse indicators with access to context outperforms neural methods. Third, we conduct a comparative analysis of these approaches for both intra- and inter-document settings, identifying statistically significant differences in results that indicate the necessity of distinguishing between these two scenarios. Our findings highlight significant challenges in this complex domain and open crucial avenues for future research on the Argument Web of Science, particularly for those interested in leveraging Semantic Web technologies and knowledge graphs to understand scholarly discourse. With this, we provide the first stepping stones in the form of a benchmark dataset, three baseline methods, and an initial analysis for a systematic exploration of this field relevant to the Web of Data and Science.
Cite as

Florian Ruosch, Cristina Sarasua, and Abraham Bernstein. Mining Inter-Document Argument Structures in Scientific Papers for an Argument Web. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 3, pp. 4:1-4:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{ruosch_et_al:TGDK.3.3.4,
  author =	{Ruosch, Florian and Sarasua, Cristina and Bernstein, Abraham},
  title =	{{Mining Inter-Document Argument Structures in Scientific Papers for an Argument Web}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{4:1--4:33},
  ISSN =	{2942-7517},
  year =	{2025},
  volume =	{3},
  number =	{3},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.3.4},
  URN =		{urn:nbn:de:0030-drops-252159},
  doi =		{10.4230/TGDK.3.3.4},
  annote =	{Keywords: Argument Mining, Large Language Models, Knowledge Graphs, Link Prediction}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2025.2
Unboundedness Problems for Formal Languages (Invited Talk)

Authors: Georg Zetzsche

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
Informally, unboundedness problems are decision problems that ask about the existence of infinitely many words (satisfying certain properties) in a formal language. For example: Is a given language infinite? Or: Does a given language have super-polynomial growth? These came into focus in recent years because of their connections to downward closure computation and separability problems. Although unboundedness problems may seem difficult at first, it turns out that there are techniques that are at the same time conceptually very simple, but also apply to a surprisingly wide variety of language classes. The talk will survey recent results (and techniques) concerning unboundedness problems.
Cite as

Georg Zetzsche. Unboundedness Problems for Formal Languages (Invited Talk). In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zetzsche:LIPIcs.FSTTCS.2025.2,
  author =	{Zetzsche, Georg},
  title =	{{Unboundedness Problems for Formal Languages}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{2:1--2:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.2},
  URN =		{urn:nbn:de:0030-drops-250810},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.2},
  annote =	{Keywords: Decidability, formal languages, unifying frameworks, downward closure, separability}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.26
Non-Adaptive Evaluation of k-of- n Functions: Tight Gap and a Unit-Cost PTAS

Authors: Mads Anker Nielsen, Lars Rohwedder, and Kevin Schewior

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

Abstract
We consider the Stochastic Boolean Function Evaluation (SBFE) problem in the well-studied case of k-of-n functions: There are independent Boolean random variables x_1,… ,x_n where each variable i has a known probability p_i of taking value 1, and a known cost c_i that can be paid to find out its value. The value of the function is 1 iff there are at least k 1s among the variables. The goal is to efficiently compute a strategy that, at minimum expected cost, tests the variables until the function value is determined. While an elegant polynomial-time exact algorithm is known when tests can be made adaptively, we focus on the non-adaptive variant, for which much less is known. First, we show a clean and tight lower bound of 2 on the adaptivity gap, i.e., the worst-case multiplicative loss in the objective function caused by disallowing adaptivity, of the problem. This improves the tight lower bound of 3/2 for the unit-cost variant. Second, we give a PTAS for computing the best non-adaptive strategy in the unit-cost case, the first PTAS for an SBFE problem. At the core, our scheme establishes a novel notion of two-sided dominance (w.r.t. the optimal solution) by guessing so-called milestone tests for a set of carefully chosen buckets of tests. To turn this technique into a polynomial-time algorithm, we use a decomposition approach paired with a random-shift argument.
Cite as

Mads Anker Nielsen, Lars Rohwedder, and Kevin Schewior. Non-Adaptive Evaluation of k-of- n Functions: Tight Gap and a Unit-Cost PTAS. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nielsen_et_al:LIPIcs.APPROX/RANDOM.2025.26,
  author =	{Nielsen, Mads Anker and Rohwedder, Lars and Schewior, Kevin},
  title =	{{Non-Adaptive Evaluation of k-of- n Functions: Tight Gap and a Unit-Cost PTAS}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.26},
  URN =		{urn:nbn:de:0030-drops-243920},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.26},
  annote =	{Keywords: Approximation scheme, Boolean functions, stochastic combinatorial optimization, stochastic function evaluation, sequential testing, adaptivity}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.45
Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences

Authors: Tuyen Pham and Hubert Wagner

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
The contributions of the paper span theoretical and implementational results. First, we prove that Kd-trees can be extended to ℝ^d with the distance measured by an arbitrary Bregman divergence. Perhaps surprisingly, this shows that the triangle inequality is not necessary for correct pruning in Kd-trees. Second, we offer an efficient algorithm and C++ implementation for nearest neighbour search for decomposable Bregman divergences. The implementation supports the Kullback-Leibler divergence (relative entropy) which is a popular distance between probability vectors and is commonly used in statistics and machine learning. This is a step toward broadening the usage of computational geometry algorithms. Our benchmarks show that our implementation efficiently handles both exact and approximate nearest neighbour queries. Compared to a linear search, we achieve two orders of magnitude speedup for practical scenarios in dimension up to 100. Our solution is simpler and more efficient than competing methods.
Cite as

Tuyen Pham and Hubert Wagner. Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pham_et_al:LIPIcs.WADS.2025.45,
  author =	{Pham, Tuyen and Wagner, Hubert},
  title =	{{Fast Kd-Trees for the Kullback-Leibler Divergence and Other Decomposable Bregman Divergences}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.45},
  URN =		{urn:nbn:de:0030-drops-242766},
  doi =		{10.4230/LIPIcs.WADS.2025.45},
  annote =	{Keywords: Kd-tree, k-d tree, nearest neighbour search, Bregman divergence, decomposable Bregman divergence, KL divergence, relative entropy, cross entropy, Shannon’s entropy}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.8
Identifying Approximate Minimizers Under Stochastic Uncertainity

Authors: Hessa Al-Thani and Viswanath Nagarajan

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

Abstract
We study a fundamental stochastic selection problem involving n independent random variables, each of which can be queried at some cost. Given a tolerance level δ, the goal is to find a δ-approximately minimum (or maximum) value over all the random variables, at minimum expected cost. A solution to this problem is an adaptive sequence of queries, where the choice of the next query may depend on previously-observed values. Two variants arise, depending on whether the goal is to find a δ-minimum value or a δ-minimizer. When all query costs are uniform, we provide a 4-approximation algorithm for both variants. When query costs are non-uniform, we provide a 5.83-approximation algorithm for the δ-minimum value and a 7.47-approximation for the δ-minimizer. All our algorithms rely on non-adaptive policies (that perform a fixed sequence of queries), so we also upper bound the corresponding "adaptivity" gaps. Our analysis relates the stopping probabilities in the algorithm and optimal policies, where a key step is in proving and using certain stochastic dominance properties.
Cite as

Hessa Al-Thani and Viswanath Nagarajan. Identifying Approximate Minimizers Under Stochastic Uncertainity. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{althani_et_al:LIPIcs.ICALP.2025.8,
  author =	{Al-Thani, Hessa and Nagarajan, Viswanath},
  title =	{{Identifying Approximate Minimizers Under Stochastic Uncertainity}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{8:1--8:18},
  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.8},
  URN =		{urn:nbn:de:0030-drops-233854},
  doi =		{10.4230/LIPIcs.ICALP.2025.8},
  annote =	{Keywords: Approximation algorithms, stochastic optimization, selection problem}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.127
Cost Preserving Dependent Rounding for Allocation Problems

Authors: Lars Rohwedder, Arman Rouhani, and Leo Wennmann

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

Abstract
We present a dependent randomized rounding scheme, which rounds fractional solutions to integral solutions satisfying certain hard constraints on the output while preserving Chernoff-like concentration properties. In contrast to previous dependent rounding schemes, our algorithm guarantees that the cost of the rounded integral solution does not exceed that of the fractional solution. Our algorithm works for a class of assignment problems with restrictions similar to those of prior works. In a non-trivial combination of our general result with a classical approach from Shmoys and Tardos [Math. Programm.'93] and more recent linear programming techniques developed for the restricted assignment variant by Bansal, Sviridenko [STOC'06] and Davies, Rothvoss, Zhang [SODA'20], we derive a O(log n)-approximation algorithm for the Budgeted Santa Claus Problem. In this new variant, the goal is to allocate resources with different values to players, maximizing the minimum value a player receives, and satisfying a budget constraint on player-resource allocation costs.
Cite as

Lars Rohwedder, Arman Rouhani, and Leo Wennmann. Cost Preserving Dependent Rounding for Allocation Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 127:1-127:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rohwedder_et_al:LIPIcs.ICALP.2025.127,
  author =	{Rohwedder, Lars and Rouhani, Arman and Wennmann, Leo},
  title =	{{Cost Preserving Dependent Rounding for Allocation Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{127:1--127: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.127},
  URN =		{urn:nbn:de:0030-drops-235049},
  doi =		{10.4230/LIPIcs.ICALP.2025.127},
  annote =	{Keywords: Matching, Randomized Rounding, Santa Claus, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.10
Steinhaus Filtration and Stable Paths in the Mapper

Authors: Dustin L. Arendt, Matthew Broussard, Bala Krishnamoorthy, Nathaniel Saul, and Amber Thrall

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

Abstract
We define a new filtration called the Steinhaus filtration built from a single cover based on a generalized Steinhaus distance, a generalization of Jaccard distance. The homology persistence module of a Steinhaus filtration with infinitely many cover elements may not be q-tame, even when the covers are in a totally bounded space. While this may pose a challenge to derive stability results, we show that the Steinhaus filtration is stable when the cover is finite. We show that while the Čech and Steinhaus filtrations are not isomorphic in general, they are isomorphic for a finite point set in dimension one. Furthermore, the VR filtration completely determines the 1-skeleton of the Steinhaus filtration in arbitrary dimension. We then develop a language and theory for stable paths within the Steinhaus filtration. We demonstrate how the framework can be applied to several applications where a standard metric may not be defined but a cover is readily available. We introduce a new perspective for modeling recommendation system datasets. As an example, we look at a movies dataset and we find the stable paths identified in our framework represent a sequence of movies constituting a gentle transition and ordering from one genre to another. For explainable machine learning, we apply the Mapper algorithm for model induction by building a filtration from a single Mapper complex, and provide explanations in the form of stable paths between subpopulations. For illustration, we build a Mapper complex from a supervised machine learning model trained on the FashionMNIST dataset. Stable paths in the Steinhaus filtration provide improved explanations of relationships between subpopulations of images.
Cite as

Dustin L. Arendt, Matthew Broussard, Bala Krishnamoorthy, Nathaniel Saul, and Amber Thrall. Steinhaus Filtration and Stable Paths in the Mapper. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{arendt_et_al:LIPIcs.SoCG.2025.10,
  author =	{Arendt, Dustin L. and Broussard, Matthew and Krishnamoorthy, Bala and Saul, Nathaniel and Thrall, Amber},
  title =	{{Steinhaus Filtration and Stable Paths in the Mapper}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{10:1--10:21},
  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.10},
  URN =		{urn:nbn:de:0030-drops-231625},
  doi =		{10.4230/LIPIcs.SoCG.2025.10},
  annote =	{Keywords: Cover and nerve, Jaccard distance, persistence stability, Mapper, recommender systems, explainable machine learning}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2025.4
Learning Aggregate Queries Defined by First-Order Logic with Counting

Authors: Steffen van Bergerem and Nicole Schweikardt

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
In the logical framework introduced by Grohe and Turán (TOCS 2004) for Boolean classification problems, the instances to classify are tuples from a logical structure, and Boolean classifiers are described by parametric models based on logical formulas. This is a specific scenario for supervised passive learning, where classifiers should be learned based on labelled examples. Existing results in this scenario focus on Boolean classification. This paper presents learnability results beyond Boolean classification. We focus on multiclass classification problems where the task is to assign input tuples to arbitrary integers. To represent such integer-valued classifiers, we use aggregate queries specified by an extension of first-order logic with counting terms called FOC₁. Our main result shows the following: given a database of polylogarithmic degree, within quasi-linear time, we can build an index structure that makes it possible to learn FOC₁-definable integer-valued classifiers in time polylogarithmic in the size of the database and polynomial in the number of training examples.
Cite as

Steffen van Bergerem and Nicole Schweikardt. Learning Aggregate Queries Defined by First-Order Logic with Counting. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanbergerem_et_al:LIPIcs.ICDT.2025.4,
  author =	{van Bergerem, Steffen and Schweikardt, Nicole},
  title =	{{Learning Aggregate Queries Defined by First-Order Logic with Counting}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.4},
  URN =		{urn:nbn:de:0030-drops-229457},
  doi =		{10.4230/LIPIcs.ICDT.2025.4},
  annote =	{Keywords: Supervised learning, multiclass classification problems, counting logic}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.47
Concentration of Submodular Functions and Read-k Families Under Negative Dependence

Authors: Sharmila Duppala, George Z. Li, Juan Luque, Aravind Srinivasan, and Renata Valieva

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

Abstract
We study the question of whether submodular functions of random variables satisfying various notions of negative dependence satisfy Chernoff-like concentration inequalities. We prove such a concentration inequality for the lower tail when the random variables satisfy negative association or negative regression, partially resolving an open problem raised in ([Frederick Qiu and Sahil Singla, 2022]). Previous work showed such concentration results for random variables that come from specific dependent-rounding algorithms ([Chandra Chekuri et al., 2010; Nicholas J. A. Harvey and Neil Olver, 2014]). We discuss some applications of our results to combinatorial optimization and beyond. We also show applications to the concentration of read-k families [Dmitry Gavinsky et al., 2015] under certain forms of negative dependence; we further show a simplified proof of the entropy-method approach of [Dmitry Gavinsky et al., 2015].
Cite as

Sharmila Duppala, George Z. Li, Juan Luque, Aravind Srinivasan, and Renata Valieva. Concentration of Submodular Functions and Read-k Families Under Negative Dependence. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{duppala_et_al:LIPIcs.ITCS.2025.47,
  author =	{Duppala, Sharmila and Li, George Z. and Luque, Juan and Srinivasan, Aravind and Valieva, Renata},
  title =	{{Concentration of Submodular Functions and Read-k Families Under Negative Dependence}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{47:1--47:16},
  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.47},
  URN =		{urn:nbn:de:0030-drops-226751},
  doi =		{10.4230/LIPIcs.ITCS.2025.47},
  annote =	{Keywords: Chernoff bounds, Submodular Functions, Negative Correlation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.29
Local Cliques in ER-Perturbed Random Geometric Graphs

Authors: Matthew Kahle, Minghao Tian, and Yusu Wang

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We study a random graph model introduced in [Srinivasan Parthasarathy et al., 2017] where one adds Erdős - Rényi (ER) type perturbation to a random geometric graph. More precisely, assume G_X^* is a random geometric graph sampled from a nice measure on a metric space X = (X,d). An ER-perturbed random geometric graph G^(p,q) is generated by removing each existing edge from G_X^* with probability p, while inserting each non-existent edge to G_X^* with probability q. We consider a localized version of clique number for G^(p,q): Specifically, we study the edge clique number for each edge in a graph, defined as the size of the largest clique(s) in the graph containing that edge. We show that the edge clique number presents two fundamentally different types of behaviors in G^(p,q), depending on which "type" of randomness it is generated from. As an application of the above results, we show that by a simple filtering process based on the edge clique number, we can recover the shortest-path metric of the random geometric graph G_X^* within a multiplicative factor of 3 from an ER-perturbed observed graph G^(p,q), for a significantly wider range of insertion probability q than what is required in [Srinivasan Parthasarathy et al., 2017].
Cite as

Matthew Kahle, Minghao Tian, and Yusu Wang. Local Cliques in ER-Perturbed Random Geometric Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kahle_et_al:LIPIcs.ISAAC.2019.29,
  author =	{Kahle, Matthew and Tian, Minghao and Wang, Yusu},
  title =	{{Local Cliques in ER-Perturbed Random Geometric Graphs}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{29:1--29:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.29},
  URN =		{urn:nbn:de:0030-drops-115253},
  doi =		{10.4230/LIPIcs.ISAAC.2019.29},
  annote =	{Keywords: random graphs, random geometric graphs, edge clique number, the probabilistic method, metric recovery}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.53
A Quest to Unravel the Metric Structure Behind Perturbed Networks

Authors: Srinivasan Parthasarathy, David Sivakoff, Minghao Tian, and Yusu Wang

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Graphs and network data are ubiquitous across a wide spectrum of scientific and application domains. Often in practice, an input graph can be considered as an observed snapshot of a (potentially continuous) hidden domain or process. Subsequent analysis, processing, and inferences are then performed on this observed graph. In this paper we advocate the perspective that an observed graph is often a noisy version of some discretized 1-skeleton of a hidden domain, and specifically we will consider the following natural network model: We assume that there is a true graph G^* which is a certain proximity graph for points sampled from a hidden domain X; while the observed graph G is an Erdos-Renyi type perturbed version of G^*. Our network model is related to, and slightly generalizes, the much-celebrated small-world network model originally proposed by Watts and Strogatz. However, the main question we aim to answer is orthogonal to the usual studies of network models (which often focuses on characterizing / predicting behaviors and properties of real-world networks). Specifically, we aim to recover the metric structure of G^* (which reflects that of the hidden space X as we will show) from the observed graph G. Our main result is that a simple filtering process based on the Jaccard index can recover this metric within a multiplicative factor of 2 under our network model. Our work makes one step towards the general question of inferring structure of a hidden space from its observed noisy graph representation. In addition, our results also provide a theoretical understanding for Jaccard-Index-based denoising approaches.
Cite as

Srinivasan Parthasarathy, David Sivakoff, Minghao Tian, and Yusu Wang. A Quest to Unravel the Metric Structure Behind Perturbed Networks. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{parthasarathy_et_al:LIPIcs.SoCG.2017.53,
  author =	{Parthasarathy, Srinivasan and Sivakoff, David and Tian, Minghao and Wang, Yusu},
  title =	{{A Quest to Unravel the Metric Structure Behind Perturbed Networks}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.53},
  URN =		{urn:nbn:de:0030-drops-72112},
  doi =		{10.4230/LIPIcs.SoCG.2017.53},
  annote =	{Keywords: metric structure, Erd\"{o}s-R\'{e}nyi perturbation, graphs, doubling measure}
}
  • Refine by Type
  • 11 Document/PDF
  • 9 Document/HTML

  • Refine by Publication Year
  • 9 2025
  • 1 2019
  • 1 2017

  • Refine by Author
  • 2 Rohwedder, Lars
  • 2 Tian, Minghao
  • 2 Wang, Yusu
  • 1 Al-Thani, Hessa
  • 1 Arendt, Dustin L.
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Computing methodologies → Information extraction
  • 1 Computing methodologies → Language resources
  • 1 Computing methodologies → Logical and relational learning
  • 1 Computing methodologies → Semantic networks
  • Show More...

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Approximation algorithms
  • 1 Approximation scheme
  • 1 Argument Mining
  • 1 Boolean functions
  • 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