82 Search Results for "Srinivasan, Srikanth"

Volume

LIPIcs, Volume 284

43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

FSTTCS 2023, December 18-20, 2023, IIIT Hyderabad, Telangana, India

Editors: Patricia Bouyer and Srikanth Srinivasan

Document
Complete Volume
DOI: 10.4230/LIPIcs.FSTTCS.2023
LIPIcs, Volume 284, FSTTCS 2023, Complete Volume

Authors: Patricia Bouyer and Srikanth Srinivasan

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
LIPIcs, Volume 284, FSTTCS 2023, Complete Volume
Cite as

43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 1-784, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{bouyer_et_al:LIPIcs.FSTTCS.2023,
  title =	{{LIPIcs, Volume 284, FSTTCS 2023, Complete Volume}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{1--784},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023},
  URN =		{urn:nbn:de:0030-drops-193724},
  doi =		{10.4230/LIPIcs.FSTTCS.2023},
  annote =	{Keywords: LIPIcs, Volume 284, FSTTCS 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.FSTTCS.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Patricia Bouyer and Srikanth Srinivasan

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

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

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

Copy BibTex To Clipboard

@InProceedings{bouyer_et_al:LIPIcs.FSTTCS.2023.0,
  author =	{Bouyer, Patricia and Srinivasan, Srikanth},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.0},
  URN =		{urn:nbn:de:0030-drops-193737},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2023.1
Reachability Games and Friends: A Journey Through the Lens of Memory and Complexity (Invited Talk)

Authors: Thomas Brihaye, Aline Goeminne, James C. A. Main, and Mickael Randour

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
Reachability objectives are arguably the most basic ones in the theory of games on graphs (and beyond). But far from being bland, they constitute the cornerstone of this field. Reachability is everywhere, as are the tools we use to reason about it. In this invited contribution, we take the reader on a journey through a zoo of models that have reachability objectives at their core. Our goal is to illustrate how model complexity impacts the complexity of strategies needed to play optimally in the corresponding games and computational complexity.
Cite as

Thomas Brihaye, Aline Goeminne, James C. A. Main, and Mickael Randour. Reachability Games and Friends: A Journey Through the Lens of Memory and Complexity (Invited Talk). In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 1:1-1:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{brihaye_et_al:LIPIcs.FSTTCS.2023.1,
  author =	{Brihaye, Thomas and Goeminne, Aline and Main, James C. A. and Randour, Mickael},
  title =	{{Reachability Games and Friends: A Journey Through the Lens of Memory and Complexity}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{1:1--1:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.1},
  URN =		{urn:nbn:de:0030-drops-193747},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.1},
  annote =	{Keywords: Games on graphs, reachability, finite-memory strategies, complexity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2023.2
On Measuring Average Case Complexity via Sum-Of-Squares Degree (Invited Talk)

Authors: Prasad Raghavendra

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
Sum-of-squares semidefinite programming hierarchy is a sequence of increasingly complex semidefinite programs to reason about systems of polynomial inequalities. The k-th-level of the sum-of-squares SDP hierarchy is a semidefinite program that can be solved in time n^O(k). Sum-of-squares SDP hierarchies subsume fundamental algorithmic techniques such as linear programming and spectral methods. Many state-of-the-art algorithms for approximating NP-hard optimization problems are captured in the first few levels of the hierarchy. More recently, sum-of-squares SDPs have been applied extensively towards designing algorithms for average case problems. These include planted problems, random constraint satisfaction problems, and computational problems arising in statistics. From the standpoint of complexity theory, sum-of-squares SDPs can be applied towards measuring the average-case hardness of a problem. Most natural optimization problems can often be shown to be solvable by degree n sum-of-squares SDP, which corresponds to an exponential time algorithm. The smallest degree of the sum-of-squares relaxation needed to solve a problem can be used as a measure of the computational complexity of the problem. This approach seems especially useful for understanding average-case complexity under natural distributions. For example, the sum-of-squares degree has been used to nearly characterize the computational complexity of refuting random CSPs as a function of the number of constraints. Using the sum-of-squares degree as a proxy measure for average case complexity opens the door to formalizing certain computational phase transitions that have been conjectured for average case problems such as recovery in stochastic block models. In this talk, we discuss applications of this approach to average-case complexity and present some open problems.
Cite as

Prasad Raghavendra. On Measuring Average Case Complexity via Sum-Of-Squares Degree (Invited Talk). In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{raghavendra:LIPIcs.FSTTCS.2023.2,
  author =	{Raghavendra, Prasad},
  title =	{{On Measuring Average Case Complexity via Sum-Of-Squares Degree}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.2},
  URN =		{urn:nbn:de:0030-drops-193750},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.2},
  annote =	{Keywords: semidefinite programming, sum-of-squares SDP, average case complexity, random SAT, stochastic block models}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2023.3
Computational and Information-Theoretic Questions from Causal Inference (Invited Talk)

Authors: Leonard J. Schulman

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
Data, for the most part, is used in order to inform potential interventions: whether by individuals (decisions about education or employment), government (public health, environmental regulation, infrastructure investment) or business. The most common data analysis tools are those which identify correlations among variables - think of regression or of clustering. However, some famous paradoxes illustrate the futility of relying on correlations alone without a model for the causal relationships between variables. Historically, causality has been teased apart from correlation through controlled experiments. But for a variety of reasons - cost, ethical constraints, or uniqueness of the system - we must often make do with passive observation alone. A theory based upon directed graphical models has been developed over the past three decades, which in some situations, enables statistically defensible causal inference even in the absence of controlled experiments. Yet "some situations" is rather fewer than one would like. This limitation spurs a range of research questions. In this talk I will describe a couple of causality paradoxes along with how they are captured within the graphical model framework; this will lead naturally toward some of the computational and information-theoretic questions which arise in the theory.
Cite as

Leonard J. Schulman. Computational and Information-Theoretic Questions from Causal Inference (Invited Talk). In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{schulman:LIPIcs.FSTTCS.2023.3,
  author =	{Schulman, Leonard J.},
  title =	{{Computational and Information-Theoretic Questions from Causal Inference}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.3},
  URN =		{urn:nbn:de:0030-drops-193769},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.3},
  annote =	{Keywords: Causal Inference, Bayesian Networks}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2023.4
From Concept Learning to SAT-Based Invariant Inference (Invited Talk)

Authors: Sharon Shoham

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
In recent years SAT-based invariant inference algorithms such as interpolation-based model checking and PDR/IC3 have proven to be extremely successful in practice. However, the essence of their practical success and their performance guarantees are far less understood. This talk surveys results that establish formal connections and distinctions between SAT-based invariant inference and exact concept learning with queries, showing that learning techniques and algorithms can clarify foundational questions, illuminate existing algorithms, and suggest new directions for efficient invariant inference.
Cite as

Sharon Shoham. From Concept Learning to SAT-Based Invariant Inference (Invited Talk). In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{shoham:LIPIcs.FSTTCS.2023.4,
  author =	{Shoham, Sharon},
  title =	{{From Concept Learning to SAT-Based Invariant Inference}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.4},
  URN =		{urn:nbn:de:0030-drops-193771},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.4},
  annote =	{Keywords: invariant inference, complexity, exact learning, interpolation, IC3}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2023.5
Algorithms in the Presence of Biased Inputs (Invited Talk)

Authors: Nisheeth K. Vishnoi

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
Algorithms for optimization problems such as selection, ranking, and classification typically assume that the inputs are what they are promised to be. However, in several real-world applications of these problems, the input may contain systematic biases along socially salient attributes associated with inputs such as race, gender, or political opinion. Such biases can not only lead the outputs of the current algorithms to output sub-optimal solutions with respect to true inputs but may also adversely affect opportunities for individuals in disadvantaged socially salient groups. This talk will consider the question of using optimization to solve the aforementioned problems in the presence of biased inputs. It will start with models of biases in inputs and discuss alternate ways to design algorithms for the underlying problem that can mitigate the effects of biases by taking into account knowledge about biases. This talk is based on several joint works with a number of co-authors.
Cite as

Nisheeth K. Vishnoi. Algorithms in the Presence of Biased Inputs (Invited Talk). In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 5:1-5:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vishnoi:LIPIcs.FSTTCS.2023.5,
  author =	{Vishnoi, Nisheeth K.},
  title =	{{Algorithms in the Presence of Biased Inputs}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{5:1--5:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.5},
  URN =		{urn:nbn:de:0030-drops-193788},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.5},
  annote =	{Keywords: Algorithmic Bias}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.6
Online Facility Location with Weights and Congestion

Authors: Arghya Chakraborty and Rahul Vaze

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
The classic online facility location problem deals with finding the optimal set of facilities in an online fashion when demand requests arrive one at a time and facilities need to be opened to service these requests. In this work, we study two variants of the online facility location problem; (1) weighted requests and (2) congestion. Both of these variants are motivated by their applications to real life scenarios and the previously known results on online facility location cannot be directly adapted to analyse them. - Weighted requests: In this variant, each demand request is a pair (x,w) where x is the standard location of the demand while w is the corresponding weight of the request. The cost of servicing request (x,w) at facility F is w⋅ d(x,F). For this variant, given n requests, we present an online algorithm attaining a competitive ratio of 𝒪(log n) in the secretarial model for the weighted requests and show that it is optimal. -Congestion: The congestion variant considers the case when there is a congestion cost that grows with the number of requests served by each facility. For this variant, when the congestion cost is a monomial, we show that there exists an algorithm attaining a constant competitive ratio. This constant is a function of the exponent of the monomial and the facility opening cost but independent of the number of requests.
Cite as

Arghya Chakraborty and Rahul Vaze. Online Facility Location with Weights and Congestion. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2023.6,
  author =	{Chakraborty, Arghya and Vaze, Rahul},
  title =	{{Online Facility Location with Weights and Congestion}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.6},
  URN =		{urn:nbn:de:0030-drops-193797},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.6},
  annote =	{Keywords: online algorithms, online facility location, probabilistic method, weighted-requests, congestion}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.7
An Optimal Algorithm for Sorting in Trees

Authors: Jishnu Roychoudhury and Jatin Yadav

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
Sorting is a foundational problem in computer science that is typically employed on sequences or total orders. More recently, a more general form of sorting on partially ordered sets (or posets), where some pairs of elements are incomparable, has been studied. General poset sorting algorithms have a lower-bound query complexity of Ω(wn + n log n), where w is the width of the poset. We consider the problem of sorting in trees, a particular case of partial orders. This problem is equivalent to the problem of reconstructing a rooted directed tree from path queries. We parametrize the complexity with respect to d, the maximum degree of an element in the tree, as d is usually much smaller than w in trees. For example, in complete binary trees, d = Θ(1), w = Θ(n). The previous known upper bounds are O(dn log² n) [Wang and Honorio, 2019] and O(d² n log n) [Ramtin Afshar et al., 2020], and a recent paper proves a lower bound of Ω(dn log_d n) [Paul Bastide, 2023] for any Las Vegas randomized algorithm. In this paper, we settle the complexity of the problem by presenting a randomized algorithm with worst-case expected O(dnlog_d n) query and time complexity.
Cite as

Jishnu Roychoudhury and Jatin Yadav. An Optimal Algorithm for Sorting in Trees. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{roychoudhury_et_al:LIPIcs.FSTTCS.2023.7,
  author =	{Roychoudhury, Jishnu and Yadav, Jatin},
  title =	{{An Optimal Algorithm for Sorting in Trees}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.7},
  URN =		{urn:nbn:de:0030-drops-193807},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.7},
  annote =	{Keywords: Sorting, Trees}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.8
Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction

Authors: R. Krithika, V. K. Kutty Malu, Roohani Sharma, and Prafullkumar Tale

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
A bipartite graph is called a biclique if it is a complete bipartite graph and a biclique is called a balanced biclique if it has equal number of vertices in both parts of its bipartition. In this work, we initiate the complexity study of Biclique Contraction and Balanced Biclique Contraction. In these problems, given as input a graph G and an integer k, the objective is to determine whether one can contract at most k edges in G to obtain a biclique and a balanced biclique, respectively. We first prove that these problems are NP-complete even when the input graph is bipartite. Next, we study the parameterized complexity of these problems and show that they admit single exponential-time FPT algorithms when parameterized by the number k of edge contractions. Then, we show that Balanced Biclique Contraction admits a quadratic vertex kernel while Biclique Contraction does not admit any polynomial compression (or kernel) unless NP ⊆ coNP/poly.
Cite as

R. Krithika, V. K. Kutty Malu, Roohani Sharma, and Prafullkumar Tale. Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{krithika_et_al:LIPIcs.FSTTCS.2023.8,
  author =	{Krithika, R. and Malu, V. K. Kutty and Sharma, Roohani and Tale, Prafullkumar},
  title =	{{Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.8},
  URN =		{urn:nbn:de:0030-drops-193811},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.8},
  annote =	{Keywords: contraction, bicliques, balanced bicliques, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.9
Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae

Authors: Pranav Bisht, Nikhil Gupta, and Ilya Volkovich

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
An arithmetic formula is an arithmetic circuit where each gate has fan-out one. An arithmetic read-once formula (ROF in short) is an arithmetic formula where each input variable labels at most one leaf. In this paper we present several efficient blackbox polynomial identity testing (PIT) algorithms for some classes of polynomials related to read-once formulas. Namely, for polynomial of the form: - f = Φ_1 ⋅ … ⋅ Φ_m + Ψ₁ ⋅ … ⋅ Ψ_r, where Φ_i,Ψ_j are ROFs for every i ∈ [m], j ∈ [r]. - f = Φ_1^{e₁} + Φ₂^{e₂} + Φ₃^{e₃}, where each Φ_i is an ROF and e_i-s are arbitrary positive integers. Earlier, only a whitebox polynomial-time algorithm was known for the former class by Mahajan, Rao and Sreenivasaiah (Algorithmica 2016). In the same paper, they also posed an open problem to come up with an efficient PIT algorithm for the class of polynomials of the form f = Φ_1^{e₁} + Φ_2^{e₂} + … + Φ_k^{e_k}, where each Φ_i is an ROF and k is some constant. Our second result answers this partially by giving a polynomial-time algorithm when k = 3. More generally, when each Φ₁,Φ₂,Φ₃ is a multilinear bounded-read formulae, we also give a quasi-polynomial-time blackbox PIT algorithm. Our main technique relies on the hardness of representation approach introduced in Shpilka and Volkovich (Computational Complexity 2015). Specifically, we show hardness of representation for the resultant polynomial of two ROFs in our first result. For our second result, we lift hardness of representation for a sum of three ROFs to sum of their powers.
Cite as

Pranav Bisht, Nikhil Gupta, and Ilya Volkovich. Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bisht_et_al:LIPIcs.FSTTCS.2023.9,
  author =	{Bisht, Pranav and Gupta, Nikhil and Volkovich, Ilya},
  title =	{{Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.9},
  URN =		{urn:nbn:de:0030-drops-193829},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.9},
  annote =	{Keywords: Identity Testing, Derandomization, Bounded-Read Formulae, Arithmetic Formulas}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.10
Bandwidth of Timed Automata: 3 Classes

Authors: Eugene Asarin, Aldric Degorre, Cătălin Dima, and Bernardo Jacobo Inclán

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
Timed languages contain sequences of discrete events ("letters") separated by real-valued delays, they can be recognized by timed automata, and represent behaviors of various real-time systems. The notion of bandwidth of a timed language defined in [Jacobo Inclán et al., 2022] characterizes the amount of information per time unit, encoded in words of the language observed with some precision ε. In this paper, we identify three classes of timed automata according to the asymptotics of the bandwidth of their languages with respect to this precision ε: automata are either meager, with an O(1) bandwidth, normal, with a Θ(log(1/ε)) bandwidth, or obese, with Θ(1/ε) bandwidth. We define two structural criteria and prove that they partition timed automata into these 3 classes of bandwidth, implying that there are no intermediate asymptotic classes. The classification problem of a timed automaton is PSPACE-complete. Both criteria are formulated using morphisms from paths of the timed automaton to some finite monoids extending Puri’s orbit graphs; the proofs are based on Simon’s factorization forest theorem.
Cite as

Eugene Asarin, Aldric Degorre, Cătălin Dima, and Bernardo Jacobo Inclán. Bandwidth of Timed Automata: 3 Classes. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{asarin_et_al:LIPIcs.FSTTCS.2023.10,
  author =	{Asarin, Eugene and Degorre, Aldric and Dima, C\u{a}t\u{a}lin and Jacobo Incl\'{a}n, Bernardo},
  title =	{{Bandwidth of Timed Automata: 3 Classes}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.10},
  URN =		{urn:nbn:de:0030-drops-193838},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.10},
  annote =	{Keywords: timed automata, information theory, bandwidth, entropy, orbit graphs, factorization forests}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.11
Monotone Classes Beyond VNP

Authors: Prerona Chatterjee, Kshitij Gajjar, and Anamay Tengse

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
In this work, we study the natural monotone analogues of various equivalent definitions of VPSPACE: a well studied class (Poizat 2008, Koiran & Perifel 2009, Malod 2011, Mahajan & Rao 2013) that is believed to be larger than VNP. We observe that these monotone analogues are not equivalent unlike their non-monotone counterparts, and propose monotone VPSPACE (mVPSPACE) to be defined as the monotone analogue of Poizat’s definition. With this definition, mVPSPACE turns out to be exponentially stronger than mVNP and also satisfies several desirable closure properties that the other analogues may not. Our initial goal was to understand the monotone complexity of transparent polynomials, a concept that was recently introduced by Hrubeš & Yehudayoff (2021). In that context, we show that transparent polynomials of large sparsity are hard for the monotone analogues of all the known definitions of VPSPACE, except for the one due to Poizat.
Cite as

Prerona Chatterjee, Kshitij Gajjar, and Anamay Tengse. Monotone Classes Beyond VNP. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.FSTTCS.2023.11,
  author =	{Chatterjee, Prerona and Gajjar, Kshitij and Tengse, Anamay},
  title =	{{Monotone Classes Beyond VNP}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.11},
  URN =		{urn:nbn:de:0030-drops-193846},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.11},
  annote =	{Keywords: Algebraic Complexity, Monotone Computation, VPSPACE, Transparent Polynomials}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.12
Approximate Maximum Rank Aggregation: Beyond the Worst-Case

Authors: Yan Hong Yao Alvin and Diptarka Chakraborty

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
The fundamental task of rank aggregation is to combine multiple rankings on a group of candidates into a single ranking to mitigate biases inherent in individual input rankings. This task has a myriad of applications, such as in social choice theory, collaborative filtering, web search, statistics, databases, sports, and admission systems. One popular version of this task, maximum rank aggregation (or the center ranking problem), aims to find a ranking (not necessarily from the input set) that minimizes the maximum distance to the input rankings. However, even for four input rankings, this problem is NP-hard (Dwork et al., WWW'01, and Biedl et al., Discrete Math.'09), and only a (folklore) polynomial-time 2-approximation algorithm is known for finding an optimal aggregate ranking under the commonly used Kendall-tau distance metric. Achieving a better approximation factor in polynomial time, ideally, a polynomial time approximation scheme (PTAS), is one of the major challenges. This paper presents significant progress in solving this problem by considering the Mallows model, a classical probabilistic model. Our proposed algorithm outputs an (1+ε)-approximate aggregate ranking for any ε > 0, with high probability, as long as the input rankings come from a Mallows model, even in a streaming fashion. Furthermore, the same approximation guarantee is achieved even in the presence of outliers, presumably a more challenging task.
Cite as

Yan Hong Yao Alvin and Diptarka Chakraborty. Approximate Maximum Rank Aggregation: Beyond the Worst-Case. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{alvin_et_al:LIPIcs.FSTTCS.2023.12,
  author =	{Alvin, Yan Hong Yao and Chakraborty, Diptarka},
  title =	{{Approximate Maximum Rank Aggregation: Beyond the Worst-Case}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.12},
  URN =		{urn:nbn:de:0030-drops-193857},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.12},
  annote =	{Keywords: Rank Aggregation, Center Problem, Mallows Model, Approximation Algorithms, Clustering with Outliers}
}
  • Refine by Author
  • 29 Srinivasan, Srikanth
  • 9 Limaye, Nutan
  • 7 Harsha, Prahladh
  • 4 Santhanam, Rahul
  • 3 Chillara, Suryajith
  • Show More...

  • Refine by Classification
  • 12 Theory of computation → Algebraic complexity theory
  • 9 Theory of computation → Circuit complexity
  • 5 Theory of computation → Probabilistic computation
  • 5 Theory of computation → Pseudorandomness and derandomization
  • 4 Theory of computation → Computational complexity and cryptography
  • Show More...

  • Refine by Keyword
  • 7 Lower Bounds
  • 3 Algebraic Complexity
  • 3 Boolean functions
  • 3 complexity
  • 3 lower bounds
  • Show More...

  • Refine by Type
  • 81 document
  • 1 volume

  • Refine by Publication Year
  • 51 2023
  • 5 2018
  • 5 2019
  • 5 2020
  • 4 2022
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact