4 Search Results for "Tawari, Anuj"

Document
DOI: 10.4230/LIPIcs.MFCS.2024.46
Query Maintenance Under Batch Changes with Small-Depth Circuits

Authors: Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, and Thomas Zeume

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Which dynamic queries can be maintained efficiently? For constant-size changes, it is known that constant-depth circuits or, equivalently, first-order updates suffice for maintaining many important queries, among them reachability, tree isomorphism, and the word problem for context-free languages. In other words, these queries are in the dynamic complexity class DynFO. We show that most of the existing results for constant-size changes can be recovered for batch changes of polylogarithmic size if one allows circuits of depth 𝒪(log log n) or, equivalently, first-order updates that are iterated 𝒪(log log n) times.
Cite as

Samir Datta, Asif Khan, Anish Mukherjee, Felix Tschirbs, Nils Vortmeier, and Thomas Zeume. Query Maintenance Under Batch Changes with Small-Depth Circuits. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.MFCS.2024.46,
  author =	{Datta, Samir and Khan, Asif and Mukherjee, Anish and Tschirbs, Felix and Vortmeier, Nils and Zeume, Thomas},
  title =	{{Query Maintenance Under Batch Changes with Small-Depth Circuits}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{46:1--46:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.46},
  URN =		{urn:nbn:de:0030-drops-206027},
  doi =		{10.4230/LIPIcs.MFCS.2024.46},
  annote =	{Keywords: Dynamic complexity theory, parallel computation, dynamic algorithms}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.122
Dynamic Complexity of Reachability: How Many Changes Can We Handle?

Authors: Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, and Thomas Zeume

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-order formulas after inserting or deleting single edges. Later, in 2018, this was extended for changes of size (log n)/(log log n), where n is the size of the graph. Changes of polylogarithmic size can be handled when also majority quantifiers may be used. In this paper we extend these results by showing that, for changes of polylogarithmic size, first-order update formulas suffice for maintaining (1) undirected reachability, and (2) directed reachability under insertions. For classes of directed graphs for which efficient parallel algorithms can compute non-zero circulation weights, reachability can be maintained with update formulas that may use "modulo 2" quantifiers under changes of polylogarithmic size. Examples for these classes include the class of planar graphs and graphs with bounded treewidth. The latter is shown here. As the logics we consider cannot maintain reachability under changes of larger sizes, our results are optimal with respect to the size of the changes.
Cite as

Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, and Thomas Zeume. Dynamic Complexity of Reachability: How Many Changes Can We Handle?. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 122:1-122:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.ICALP.2020.122,
  author =	{Datta, Samir and Kumar, Pankaj and Mukherjee, Anish and Tawari, Anuj and Vortmeier, Nils and Zeume, Thomas},
  title =	{{Dynamic Complexity of Reachability: How Many Changes Can We Handle?}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{122:1--122:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.122},
  URN =		{urn:nbn:de:0030-drops-125291},
  doi =		{10.4230/LIPIcs.ICALP.2020.122},
  annote =	{Keywords: Dynamic complexity, reachability, complex changes}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.53
On the Symmetries of and Equivalence Test for Design Polynomials

Authors: Nikhil Gupta and Chandan Saha

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
In a Nisan-Wigderson design polynomial (in short, a design polynomial), every pair of monomials share a few common variables. A useful example of such a polynomial, introduced in [Neeraj Kayal et al., 2014], is the following: NW_{d,k}({x}) = sum_{h in F_d[z], deg(h) <= k}{ prod_{i=0}^{d-1}{x_{i, h(i)}}}, where d is a prime, F_d is the finite field with d elements, and k << d. The degree of the gcd of every pair of monomials in NW_{d,k} is at most k. For concreteness, we fix k = ceil[sqrt{d}]. The family of polynomials NW := {NW_{d,k} : d is a prime} and close variants of it have been used as hard explicit polynomial families in several recent arithmetic circuit lower bound proofs. But, unlike the permanent, very little is known about the various structural and algorithmic/complexity aspects of NW beyond the fact that NW in VNP. Is NW_{d,k} characterized by its symmetries? Is it circuit-testable, i.e., given a circuit C can we check efficiently if C computes NW_{d,k}? What is the complexity of equivalence test for NW, i.e., given black-box access to a f in F[{x}], can we check efficiently if there exists an invertible linear transformation A such that f = NW_{d,k}(A * {x})? Characterization of polynomials by their symmetries plays a central role in the geometric complexity theory program. Here, we answer the first two questions and partially answer the third. We show that NW_{d,k} is characterized by its group of symmetries over C, but not over R. We also show that NW_{d,k} is characterized by circuit identities which implies that NW_{d,k} is circuit-testable in randomized polynomial time. As another application of this characterization, we obtain the "flip theorem" for NW. We give an efficient equivalence test for NW in the case where the transformation A is a block-diagonal permutation-scaling matrix. The design of this algorithm is facilitated by an almost complete understanding of the group of symmetries of NW_{d,k}: We show that if A is in the group of symmetries of NW_{d,k} then A = D * P, where D and P are diagonal and permutation matrices respectively. This is proved by completely characterizing the Lie algebra of NW_{d,k}, and using an interplay between the Hessian of NW_{d,k} and the evaluation dimension.
Cite as

Nikhil Gupta and Chandan Saha. On the Symmetries of and Equivalence Test for Design Polynomials. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.MFCS.2019.53,
  author =	{Gupta, Nikhil and Saha, Chandan},
  title =	{{On the Symmetries of and Equivalence Test for Design Polynomials}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.53},
  URN =		{urn:nbn:de:0030-drops-109979},
  doi =		{10.4230/LIPIcs.MFCS.2019.53},
  annote =	{Keywords: Nisan-Wigderson design polynomial, characterization by symmetries, Lie algebra, group of symmetries, circuit testability, flip theorem, equivalence test}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.74
Computing the Maximum using (min, +) Formulas

Authors: Meena Mahajan, Prajakta Nimbhorkar, and Anuj Tawari

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
We study computation by formulas over (min,+). We consider the computation of max{x_1,...,x_n} over N as a difference of (min,+) formulas, and show that size n + n \log n is sufficient and necessary. Our proof also shows that any (min,+) formula computing the minimum of all sums of n-1 out of n variables must have n \log n leaves; this too is tight. Our proofs use a complexity measure for (min,+) functions based on minterm-like behaviour and on the entropy of an associated graph.
Cite as

Meena Mahajan, Prajakta Nimbhorkar, and Anuj Tawari. Computing the Maximum using (min, +) Formulas. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 74:1-74:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{mahajan_et_al:LIPIcs.MFCS.2017.74,
  author =	{Mahajan, Meena and Nimbhorkar, Prajakta and Tawari, Anuj},
  title =	{{Computing the Maximum using (min, +) Formulas}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{74:1--74:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.74},
  URN =		{urn:nbn:de:0030-drops-80706},
  doi =		{10.4230/LIPIcs.MFCS.2017.74},
  annote =	{Keywords: Formulas, Circuits, Lower bounds, Tropical semiring}
}
  • Refine by Author
  • 2 Datta, Samir
  • 2 Mukherjee, Anish
  • 2 Tawari, Anuj
  • 2 Vortmeier, Nils
  • 2 Zeume, Thomas
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Algebraic complexity theory
  • 1 Theory of computation → Logic and databases

  • Refine by Keyword
  • 1 Circuits
  • 1 Dynamic complexity
  • 1 Dynamic complexity theory
  • 1 Formulas
  • 1 Lie algebra
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2017
  • 1 2019
  • 1 2020
  • 1 2024

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