94 Search Results for "Guruswami, Venkatesan"

Volume

LIPIcs, Volume 250

42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

FSTTCS 2022, December 18-20, 2022, IIT Madras, Chennai, India

Editors: Anuj Dawar and Venkatesan Guruswami

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.50
A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble

Authors: Venkatesan Guruswami and Shilun Li

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

Abstract
We present an explicit construction of a sequence of rate 1/2 Wozencraft ensemble codes (over any fixed finite field 𝔽_q) that achieve minimum distance Ω(√k) where k is the message length. The coefficients of the Wozencraft ensemble codes are constructed using Sidon Sets and the cyclic structure of 𝔽_{q^k} where k+1 is prime with q a primitive root modulo k+1. Assuming Artin’s conjecture, there are infinitely many such k for any prime power q.
Cite as

Venkatesan Guruswami and Shilun Li. A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 50:1-50:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2023.50,
  author =	{Guruswami, Venkatesan and Li, Shilun},
  title =	{{A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{50:1--50:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.50},
  URN =		{urn:nbn:de:0030-drops-188751},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.50},
  annote =	{Keywords: Algebraic codes, Pseudorandomness, Explicit Construction, Wozencraft Ensemble, Sidon Sets}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.FSTTCS.2022
LIPIcs, Volume 250, FSTTCS 2022, Complete Volume

Authors: Anuj Dawar and Venkatesan Guruswami

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
LIPIcs, Volume 250, FSTTCS 2022, Complete Volume
Cite as

Anuj Dawar and Venkatesan Guruswami. LIPIcs, Volume 250, FSTTCS 2022, Complete Volume. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 1-792, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Proceedings{dawar_et_al:LIPIcs.FSTTCS.2022,
  title =	{{LIPIcs, Volume 250, FSTTCS 2022, Complete Volume}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{1--792},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022},
  URN =		{urn:nbn:de:0030-drops-173910},
  doi =		{10.4230/LIPIcs.FSTTCS.2022},
  annote =	{Keywords: LIPIcs, Volume 250, FSTTCS 2022, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.FSTTCS.2022.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Anuj Dawar and Venkatesan Guruswami

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

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

Anuj Dawar and Venkatesan Guruswami. Front Matter, Table of Contents, Preface, Conference Organization. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 0:i-0:xvi, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.FSTTCS.2022.0,
  author =	{Dawar, Anuj and Guruswami, Venkatesan},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.0},
  URN =		{urn:nbn:de:0030-drops-173928},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2022.1
Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk)

Authors: Anupam Gupta

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Analyzing the performance of algorithms in both the worst case and the average case are cornerstones of computer science: these are two different ways to understand how well algorithms perform. Over the past two decades, there has been a concerted effort to understand the performance of algorithms in models that go beyond these two extremes. In this talk I will discuss some of the proposed models and approaches, particularly for problems related to online algorithms, where decisions must be made sequentially without knowing future portions of the input.
Cite as

Anupam Gupta. Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gupta:LIPIcs.FSTTCS.2022.1,
  author =	{Gupta, Anupam},
  title =	{{Algorithms for Uncertain Environments: Going Beyond the Worst-Case}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.1},
  URN =		{urn:nbn:de:0030-drops-173933},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.1},
  annote =	{Keywords: Optimization under Uncertainty, Online Algorithms, Beyond Worst Case Analysis}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2022.2
Why MCSP Is a More Important Problem Than SAT (Invited Talk)

Authors: Rahul Santhanam

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
CNF Satisfiability (SAT) and its variants are generally considered the central problems in complexity theory, due to their applications in the theory of NP-completeness, logic, verification, probabilistically checkable proofs and parameterized complexity, among other areas. We challenge this conventional wisdom and argue that analysing the Minimum Circuit Size Problem (MCSP) and its relatives is more important from the perspective of fundamental problems in complexity theory, such as complexity lower bounds, minimal assumptions for cryptography, a robust theory of average-case complexity, and optimal results in hardness of approximation.
Cite as

Rahul Santhanam. Why MCSP Is a More Important Problem Than SAT (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{santhanam:LIPIcs.FSTTCS.2022.2,
  author =	{Santhanam, Rahul},
  title =	{{Why MCSP Is a More Important Problem Than SAT}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.2},
  URN =		{urn:nbn:de:0030-drops-173943},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.2},
  annote =	{Keywords: Minimum Circuit Size Problem, Satisfiability, Cryptography, Learning, Approximation}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2022.3
The True Colors of Memory: A Tour of Chromatic-Memory Strategies in Zero-Sum Games on Graphs (Invited Talk)

Authors: Patricia Bouyer, Mickael Randour, and Pierre Vandenhove

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Two-player turn-based zero-sum games on (finite or infinite) graphs are a central framework in theoretical computer science - notably as a tool for controller synthesis, but also due to their connection with logic and automata theory. A crucial challenge in the field is to understand how complex strategies need to be to play optimally, given a type of game and a winning objective. In this invited contribution, we give a tour of recent advances aiming to characterize games where finite-memory strategies suffice (i.e., using a limited amount of information about the past). We mostly focus on so-called chromatic memory, which is limited to using colors - the basic building blocks of objectives - seen along a play to update itself. Chromatic memory has the advantage of being usable in different game graphs, and the corresponding class of strategies turns out to be of great interest to both the practical and the theoretical sides.
Cite as

Patricia Bouyer, Mickael Randour, and Pierre Vandenhove. The True Colors of Memory: A Tour of Chromatic-Memory Strategies in Zero-Sum Games on Graphs (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 3:1-3:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bouyer_et_al:LIPIcs.FSTTCS.2022.3,
  author =	{Bouyer, Patricia and Randour, Mickael and Vandenhove, Pierre},
  title =	{{The True Colors of Memory: A Tour of Chromatic-Memory Strategies in Zero-Sum Games on Graphs}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.3},
  URN =		{urn:nbn:de:0030-drops-173957},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.3},
  annote =	{Keywords: two-player games on graphs, finite-memory strategies, chromatic memory, parity automata, \omega-regularity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2022.4
Expanders in Higher Dimensions (Invited Talk)

Authors: Irit Dinur

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Expander graphs have been studied in many areas of mathematics and in computer science with versatile applications, including coding theory, networking, computational complexity and geometry. High-dimensional expanders are a generalization that has been studied in recent years and their promise is beginning to bear fruit. In the talk, I will survey some powerful local to global properties of high-dimensional expanders, and describe several interesting applications, ranging from convergence of random walks to construction of locally testable codes that prove the c³ conjecture (namely, codes with constant rate, constant distance, and constant locality).
Cite as

Irit Dinur. Expanders in Higher Dimensions (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, p. 4:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dinur:LIPIcs.FSTTCS.2022.4,
  author =	{Dinur, Irit},
  title =	{{Expanders in Higher Dimensions}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.4},
  URN =		{urn:nbn:de:0030-drops-173967},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.4},
  annote =	{Keywords: Expanders}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.5
Packing Arc-Disjoint 4-Cycles in Oriented Graphs

Authors: Jasine Babu, R. Krithika, and Deepak Rajendraprasad

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Given a directed graph G and a positive integer k, the Arc Disjoint r-Cycle Packing problem asks whether G has k arc-disjoint r-cycles. We show that, for each integer r ≥ 3, Arc Disjoint r-Cycle Packing is NP-complete on oriented graphs with girth r. When r is even, the same result holds even when the input class is further restricted to be bipartite. On the positive side, focusing on r = 4 in oriented graphs, we study the complexity of the problem with respect to two parameterizations: solution size and vertex cover size. For the former, we give a cubic kernel with quadratic number of vertices. This is smaller than the compression size guaranteed by a reduction to the well-known 4-Set Packing. For the latter, we show fixed-parameter tractability using an unapparent integer linear programming formulation of an equivalent problem.
Cite as

Jasine Babu, R. Krithika, and Deepak Rajendraprasad. Packing Arc-Disjoint 4-Cycles in Oriented Graphs. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 5:1-5:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{babu_et_al:LIPIcs.FSTTCS.2022.5,
  author =	{Babu, Jasine and Krithika, R. and Rajendraprasad, Deepak},
  title =	{{Packing Arc-Disjoint 4-Cycles in Oriented Graphs}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.5},
  URN =		{urn:nbn:de:0030-drops-173979},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.5},
  annote =	{Keywords: arc-disjoint cycles, bipartite digraphs, oriented graphs, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.6
Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions

Authors: Calvin Beideman, Karthekeyan Chandrasekaran, Chandra Chekuri, and Chao Xu

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Submodular functions are fundamental to combinatorial optimization. Many interesting problems can be formulated as special cases of problems involving submodular functions. In this work, we consider the problem of approximating symmetric submodular functions everywhere using hypergraph cut functions. Devanur, Dughmi, Schwartz, Sharma, and Singh [Devanur et al., 2013] showed that symmetric submodular functions over n-element ground sets cannot be approximated within (n/8)-factor using a graph cut function and raised the question of approximating them using hypergraph cut functions. Our main result is that there exist symmetric submodular functions over n-element ground sets that cannot be approximated within a o(n^{1/3}/log² n)-factor using a hypergraph cut function. On the positive side, we show that symmetrized concave linear functions and symmetrized rank functions of uniform matroids and partition matroids can be constant-approximated using hypergraph cut functions.
Cite as

Calvin Beideman, Karthekeyan Chandrasekaran, Chandra Chekuri, and Chao Xu. Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 6:1-6:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{beideman_et_al:LIPIcs.FSTTCS.2022.6,
  author =	{Beideman, Calvin and Chandrasekaran, Karthekeyan and Chekuri, Chandra and Xu, Chao},
  title =	{{Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.6},
  URN =		{urn:nbn:de:0030-drops-173986},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.6},
  annote =	{Keywords: Submodular Functions, Hypergraphs, Approximation, Representation}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.7
The DAG Visit Approach for Pebbling and I/O Lower Bounds

Authors: Gianfranco Bilardi and Lorenzo De Stefani

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
We introduce the notion of an r-visit of a Directed Acyclic Graph DAG G = (V,E), a sequence of the vertices of the DAG complying with a given rule r. A rule r specifies for each vertex v ∈ V a family of r-enabling sets of (immediate) predecessors: before visiting v, at least one of its enabling sets must have been visited. Special cases are the r^(top)-rule (or, topological rule), for which the only enabling set is the set of all predecessors and the r^(sin)-rule (or, singleton rule), for which the enabling sets are the singletons containing exactly one predecessor. The r-boundary complexity of a DAG G, b_r(G), is the minimum integer b such that there is an r-visit where, at each stage, for at most b of the vertices yet to be visited an enabling set has already been visited. By a reformulation of known results, it is shown that the boundary complexity of a DAG G is a lower bound to the pebbling number of the reverse DAG, G^R. Several known pebbling lower bounds can be cast in terms of the r^{(sin)}-boundary complexity. The main contributions of this paper are as follows: - An existentially tight 𝒪(√{d_{out} n}) upper bound to the r^(sin)-boundary complexity of any DAG of n vertices and out-degree d_{out}. - An existentially tight 𝒪(d_{out}/(log₂ d_{out}) log₂ n) upper bound to the r^(top)-boundary complexity of any DAG. (There are DAGs for which r^(top) provides a tight pebbling lower bound, whereas r^(sin) does not.) - A visit partition technique for I/O lower bounds, which generalizes the S-partition I/O technique introduced by Hong and Kung in their classic paper "I/O complexity: The Red-Blue pebble game". The visit partition approach yields tight I/O bounds for some DAGs for which the S-partition technique can only yield a trivial lower bound.
Cite as

Gianfranco Bilardi and Lorenzo De Stefani. The DAG Visit Approach for Pebbling and I/O Lower Bounds. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 7:1-7:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bilardi_et_al:LIPIcs.FSTTCS.2022.7,
  author =	{Bilardi, Gianfranco and De Stefani, Lorenzo},
  title =	{{The DAG Visit Approach for Pebbling and I/O Lower Bounds}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.7},
  URN =		{urn:nbn:de:0030-drops-173999},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.7},
  annote =	{Keywords: Pebbling, Directed Acyclic Graph, Pebbling number, I/O complexity}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.8
Counting and Sampling from Substructures Using Linear Algebraic Queries

Authors: Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
For an unknown n × n matrix A having non-negative entries, the inner product (IP) oracle takes as inputs a specified row (or a column) of A and a vector 𝐯 ∈ ℝⁿ with non-negative entries, and returns their inner product. Given two input vectors x and y in ℝⁿ with non-negative entries, and an unknown matrix A with non-negative entries with IP oracle access, we design almost optimal sublinear time algorithms for the following two fundamental matrix problems: - Find an estimate 𝒳 for the bilinear form x^T A y such that 𝒳 ≈ x^T A y. - Designing a sampler 𝒵 for the entries of the matrix A such that ℙ(𝒵 = (i,j)) ≈ x_i A_{ij} y_j /(x^T A y), where x_i and y_j are i-th and j-th coordinate of 𝐱 and 𝐲 respectively. As special cases of the above results, for any submatrix of an unknown matrix with non-negative entries and IP oracle access, we can efficiently estimate the sum of the entries of any submatrix, and also sample a random entry from the submatrix with probability proportional to its weight. We will show that the above results imply that if we are given IP oracle access to the adjacency matrix of a graph, with non-negative weights on the edges, then we can design sublinear time algorithms for the following two fundamental graph problems: - Estimating the sum of the weights of the edges of an induced subgraph, and - Sampling edges proportional to their weights from an induced subgraph. We show that compared to the classical local queries (degree, adjacency, and neighbor queries) on graphs, we can get a quadratic speedup if we use IP oracle access for the above two problems. Apart from the above, we study several matrix problems through the lens of IP oracle, like testing if the matrix is diagonal, symmetric, doubly stochastic, etc. Note that IP oracle is in the class of linear algebraic queries used lately in a series of works by Ben-Eliezer et al. [SODA'08], Nisan [SODA'21], Rashtchian et al. [RANDOM'20], Sun et al. [ICALP'19], and Shi and Woodruff [AAAI'19]. Recently, IP oracle was used by Bishnu et al. [RANDOM'21] to estimate dissimilarities between two matrices.
Cite as

Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar. Counting and Sampling from Substructures Using Linear Algebraic Queries. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 8:1-8:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bishnu_et_al:LIPIcs.FSTTCS.2022.8,
  author =	{Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath and Paraashar, Manaswi},
  title =	{{Counting and Sampling from Substructures Using Linear Algebraic Queries}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.8},
  URN =		{urn:nbn:de:0030-drops-174009},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.8},
  annote =	{Keywords: Query complexity, Bilinear form, Uniform sampling, Weighted graphs}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.9
Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials

Authors: Pranav Bisht and Nitin Saxena

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
More than three decades ago, after a series of results, Kaltofen and Trager (J. Symb. Comput. 1990) designed a randomized polynomial time algorithm for factorization of multivariate circuits. Derandomizing this algorithm, even for restricted circuit classes, is an important open problem. In particular, the case of s-sparse polynomials, having individual degree d = O(1), is very well-studied (Shpilka, Volkovich ICALP'10; Volkovich RANDOM'17; Bhargava, Saraf and Volkovich FOCS'18, JACM'20). We give a complete derandomization for this class assuming that the input is a symmetric polynomial over rationals. Generally, we prove an s^poly(d)-sparsity bound for the factors of symmetric polynomials over any field. This characterizes the known worst-case examples of sparsity blow-up for sparse polynomial factoring. To factor f, we use techniques from convex geometry and exploit symmetry (only) in the Newton polytope of f. We prove a crucial result about convex polytopes, by introducing the concept of "low min-entropy", which might also be of independent interest.
Cite as

Pranav Bisht and Nitin Saxena. Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 9:1-9:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bisht_et_al:LIPIcs.FSTTCS.2022.9,
  author =	{Bisht, Pranav and Saxena, Nitin},
  title =	{{Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{9:1--9:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.9},
  URN =		{urn:nbn:de:0030-drops-174012},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.9},
  annote =	{Keywords: Multivariate polynomial factorization, derandomization, sparse polynomials, symmetric polynomials, factor-sparsity, convex polytopes}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.10
On Solving Sparse Polynomial Factorization Related Problems

Authors: Pranav Bisht and Ilya Volkovich

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first factor sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most s terms and individual degree bounded by d can itself have at most s^O(d²log n) terms. It is conjectured, though, that the "true" sparsity bound should be polynomial (i.e. s^poly(d)). In this paper we provide supporting evidence for this conjecture by presenting polynomial-time algorithms for several problems that would be implied by a polynomial-size sparsity bound. In particular, we give efficient (deterministic) algorithms for identity testing of Σ^[2]ΠΣΠ^[ind-deg d] circuits and testing if a sparse polynomial is an exact power. Hence, our algorithms rely on different techniques.
Cite as

Pranav Bisht and Ilya Volkovich. On Solving Sparse Polynomial Factorization Related Problems. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 10:1-10:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bisht_et_al:LIPIcs.FSTTCS.2022.10,
  author =	{Bisht, Pranav and Volkovich, Ilya},
  title =	{{On Solving Sparse Polynomial Factorization Related Problems}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.10},
  URN =		{urn:nbn:de:0030-drops-174023},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.10},
  annote =	{Keywords: Sparse Polynomials, Identity Testing, Derandomization, Factor-Sparsity, Multivariate Polynomial Factorization}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.11
Complexity of Spatial Games

Authors: Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Ismaël Jecker, and Jakub Svoboda

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
Spatial games form a widely-studied class of games from biology and physics modeling the evolution of social behavior. Formally, such a game is defined by a square (d by d) payoff matrix M and an undirected graph G. Each vertex of G represents an individual, that initially follows some strategy i ∈ {1,2,…,d}. In each round of the game, every individual plays the matrix game with each of its neighbors: An individual following strategy i meeting a neighbor following strategy j receives a payoff equal to the entry (i,j) of M. Then, each individual updates its strategy to its neighbors' strategy with the highest sum of payoffs, and the next round starts. The basic computational problems consist of reachability between configurations and the average frequency of a strategy. For general spatial games and graphs, these problems are in PSPACE. In this paper, we examine restricted setting: the game is a prisoner’s dilemma; and G is a subgraph of grid. We prove that basic computational problems for spatial games with prisoner’s dilemma on a subgraph of a grid are PSPACE-hard.
Cite as

Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Ismaël Jecker, and Jakub Svoboda. Complexity of Spatial Games. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 11:1-11:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.FSTTCS.2022.11,
  author =	{Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Jecker, Isma\"{e}l and Svoboda, Jakub},
  title =	{{Complexity of Spatial Games}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.11},
  URN =		{urn:nbn:de:0030-drops-174038},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.11},
  annote =	{Keywords: spatial games, computational complexity, prisoner’s dilemma, dynamical systems}
}
  • Refine by Author
  • 46 Guruswami, Venkatesan
  • 5 Xing, Chaoping
  • 4 Lee, Euiwoong
  • 4 Sandeep, Sai
  • 4 Wootters, Mary
  • Show More...

  • Refine by Classification
  • 11 Theory of computation → Error-correcting codes
  • 7 Mathematics of computing → Coding theory
  • 7 Theory of computation
  • 7 Theory of computation → Algebraic complexity theory
  • 6 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 5 hardness of approximation
  • 4 Coding theory
  • 4 hypergraph coloring
  • 3 Pseudorandomness
  • 3 list-decoding
  • Show More...

  • Refine by Type
  • 93 document
  • 1 volume

  • Refine by Publication Year
  • 53 2022
  • 7 2019
  • 6 2015
  • 6 2017
  • 6 2020
  • 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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact