41 Search Results for "Agrawal, Manindra"

Document
DOI: 10.4230/LIPIcs.FUN.2026.39
Price of Locality in Permutation Mastermind: Are TikTok Influencers Chaotic Enough?

Authors: Bernardo Subercaseaux

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
In the permutation Mastermind game, the goal is to uncover a secret permutation σ^⋆ : [n] → [n] by making a series of guesses π₁, …, π_T which must also be permutations of [n], and receiving as feedback after guess π_t the number of positions i for which σ^⋆(i) = π_t(i). While the existing literature on permutation Mastermind suggests strategies in which π_t and π_{t+1} might be widely different permutations, a resurgence in popularity of this game as a TikTok trend shows that humans (or at least TikTok influencers) use strategies in which consecutive guesses are very similar. For example, it is common to see players attempt one transposition at a time and slowly see their score increase. Motivated by these observations, we study the theoretical impact of two forms of locality in permutation Mastermind strategies: 𝓁_k-local strategies, in which any two consecutive guesses differ in at most k positions, and the even more restrictive class of w_k-local strategies, in which consecutive guesses differ in a window of length at most k. We show that, in broad terms, the optimal number of guesses for local strategies is quadratic, and thus much worse than the O(n lg n) guesses that suffice for non-local strategies. We also show NP-hardness of the satisfiability version for 𝓁₃-local strategies, whereas in the 𝓁₂-local variant the problem admits a randomized polynomial-time algorithm.
Cite as

Bernardo Subercaseaux. Price of Locality in Permutation Mastermind: Are TikTok Influencers Chaotic Enough?. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 39:1-39:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{subercaseaux:LIPIcs.FUN.2026.39,
  author =	{Subercaseaux, Bernardo},
  title =	{{Price of Locality in Permutation Mastermind: Are TikTok Influencers Chaotic Enough?}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{39:1--39:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.39},
  URN =		{urn:nbn:de:0030-drops-257585},
  doi =		{10.4230/LIPIcs.FUN.2026.39},
  annote =	{Keywords: Permutation Mastermind, Locality, NP-hard}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.30
Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions

Authors: Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Given Boolean functions f, g : 𝔽₂ⁿ → {-1,+1}, we say they are linearly isomorphic if there exists A ∈ GL_n(𝔽₂) such that f(x) = g(Ax) for all x. We study this problem in the tolerant property testing framework under the known-unknown model, where g is given explicitly and f is accessible only via oracle queries, meaning the algorithm may adaptively request the value of f(x) for inputs x ∈ 𝔽₂ⁿ of its choice. Given parameters ε ≥ 0 and ω > 0, the goal is to distinguish whether there exists A ∈ GL_n(𝔽₂) such that the normalized Hamming distance between f and g(Ax) is at most ε, or whether for every A ∈ GL_n(𝔽₂) the distance is at least ε+ω. Our main result is a tolerant tester making Õ ((m/ω) ⁴) queries to f, where m is an upper bound on the spectral norm of g, improving the previous Õ ((m/ω) ^{24}) bound of Wimmer and Yoshida. We complement this with a nearly matching lower bound of Ω(m²) for constant ω (for example, ω = 1/4), improving the prior Ω(log m) lower bound of Grigorescu, Wimmer and Xie. A key technical ingredient on the algorithmic side is a query-efficient local list corrector. For the lower bound, we give a reduction from communication complexity using a novel subclass of Maiorana-McFarland functions from symmetric-key cryptography.
Cite as

Swarnalipa Datta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy. Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.STACS.2026.30,
  author =	{Datta, Swarnalipa and Ghosh, Arijit and Kayal, Chandrima and Paraashar, Manaswi and Roy, Manmatha},
  title =	{{Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{30:1--30:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.30},
  URN =		{urn:nbn:de:0030-drops-255194},
  doi =		{10.4230/LIPIcs.STACS.2026.30},
  annote =	{Keywords: Boolean Function, Isomorphism of Boolean Function, Fourier Analysis, Sublinear Algorithm, Property Testing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.19
A Linear Kernel for Independent Set Reconfiguration in Planar Graphs

Authors: Nicolas Bousquet and Daniel W. Cranston

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Fix a positive integer r, and a graph G that is K_{3,r}-minor-free. Let I_s and I_t be two independent sets in G, each of size k. We begin with a "token" on each vertex of I_s and seek to move all tokens to I_t, by repeated "token jumping", removing a single token from one vertex and placing it on another vertex. We require that each intermediate arrangement of tokens again specifies an independent set of size k. Given G, I_s, and I_t, we ask whether there exists a sequence of token jumps that transforms I_s into I_t. When k is part of the input, this problem is known to be PSPACE-complete. But it was shown by Ito, Kamiński, and Ono [Ito et al., 2014] to be fixed-parameter tractable. That is, the problem can be solved in time f(k)⋅ P(n), for some function f and polynomial P, where n denotes the order of G. Here we strengthen the upper bound on the running time in terms of k by showing that the problem has a kernel of size linear in k. More precisely, we transform an arbitrary input problem on a K_{3,r}-minor-free graph (for some fixed positive integer r) into an equivalent problem on a (K_{3,r}-minor-free) graph with order O(k). This answers positively a question of Bousquet, Mouawad, Nishimura, and Siebertz [Nicolas Bousquet et al., 2022] and improves the recent quadratic kernel of Cranston, Mühlenthaler, and Peyrille [Daniel W. Cranston et al., 2024]. For planar graphs, we further strengthen this upper bound to get a kernel of size at most 42k.
Cite as

Nicolas Bousquet and Daniel W. Cranston. A Linear Kernel for Independent Set Reconfiguration in Planar Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2026.19,
  author =	{Bousquet, Nicolas and Cranston, Daniel W.},
  title =	{{A Linear Kernel for Independent Set Reconfiguration in Planar Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.19},
  URN =		{urn:nbn:de:0030-drops-255081},
  doi =		{10.4230/LIPIcs.STACS.2026.19},
  annote =	{Keywords: Reconfiguration, Independent Set, Kernel, Planar graphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.95
Identity Testing for Circuits with Exponentiation Gates

Authors: Jiatu Li and Mengdi Wu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Motivated by practical applications in the design of optimization compilers for neural networks, we initiated the study of identity testing problems for arithmetic circuits augmented with exponentiation gates that compute the real function x↦ e^x. These circuits compute real functions of form P(→x)/P'(→x), where both P(→x) and P'(→x) are exponential polynomials ∑_{i = 1}^k f_i(→x)⋅ exp((g_i(→x))/(h_i(→x))), for polynomials f_i(→x),g_i(→x), and h_i(→x). We formalize a black-box query model over finite fields for this class of circuits, which is mathematical simple and reflects constraints faced by real-world neural network compilers. We proved that a simple and efficient randomized identity testing algorithm achieves perfect completeness and non-trivial soundness. Concurrent with our work, the algorithm has been implemented in the optimization compiler Mirage by Wu et al. (OSDI 2025), demonstrating promising empirical performance in both efficiency and soundness error. Finally, we propose a number-theoretic conjecture under which our algorithm is sound with high probability.
Cite as

Jiatu Li and Mengdi Wu. Identity Testing for Circuits with Exponentiation Gates. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 95:1-95:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ITCS.2026.95,
  author =	{Li, Jiatu and Wu, Mengdi},
  title =	{{Identity Testing for Circuits with Exponentiation Gates}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{95:1--95:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.95},
  URN =		{urn:nbn:de:0030-drops-253821},
  doi =		{10.4230/LIPIcs.ITCS.2026.95},
  annote =	{Keywords: Polynomial Identity Testing, Exponential Polynomials}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.60
Total Search Problems in ZPP

Authors: Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, and Weiqiang Yuan

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We initiate a systematic study of TFZPP, the class of total NP search problems solvable by polynomial time randomized algorithms. TFZPP contains a variety of important search problems such as Bertrand-Chebyshev (finding a prime between N and 2N), refuter problems for many circuit lower bounds, and Lossy-Code. The Lossy-Code problem has found prominence due to its fundamental connections to derandomization, catalytic computing, and the metamathematics of complexity theory, among other areas. While TFZPP collapses to FP under standard derandomization assumptions in the white-box setting, we are able to separate TFZPP from the major TFNP subclasses in the black-box setting. In fact, we are able to separate it from every uniform TFNP class assuming that NP is not in quasi-polynomial time. To do so, we extend the connection between proof complexity and black-box TFNP to randomized proof systems and randomized reductions. Next, we turn to developing a taxonomy of TFZPP problems. We highlight a problem called Nephew, originating from an infinity axiom in set theory. We show that Nephew is in PWPP∩ TFZPP and conjecture that it is not reducible to Lossy-Code. Intriguingly, except for some artificial examples, most other black-box TFZPP problems that we are aware of reduce to Lossy-Code: - We define a problem called Empty-Child capturing finding a leaf in a rooted (binary) tree, and show that this problem is equivalent to Lossy-Code. We also show that a variant of Empty-Child with "heights" is complete for the intersection of SOPL and Lossy-Code. - We strengthen Lossy-Code with several combinatorial inequalities such as the AM-GM inequality. Somewhat surprisingly, we show the resulting new problems are still reducible to Lossy-Code. A technical highlight of this result is that they are proved by formalizations in bounded arithmetic, specifically in Jeřábek’s theory APC₁ (JSL 2007). - Finally, we show that the Dense-Linear-Ordering problem reduces to Lossy-Code.
Cite as

Noah Fleming, Stefan Grosser, Siddhartha Jain, Jiawei Li, Hanlin Ren, Morgan Shirley, and Weiqiang Yuan. Total Search Problems in ZPP. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 60:1-60:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fleming_et_al:LIPIcs.ITCS.2026.60,
  author =	{Fleming, Noah and Grosser, Stefan and Jain, Siddhartha and Li, Jiawei and Ren, Hanlin and Shirley, Morgan and Yuan, Weiqiang},
  title =	{{Total Search Problems in ZPP}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{60:1--60:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.60},
  URN =		{urn:nbn:de:0030-drops-253473},
  doi =		{10.4230/LIPIcs.ITCS.2026.60},
  annote =	{Keywords: TFNP, lossy code, randomized proof systems, query complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.3
Linear Matroid Intersection Is in Catalytic Logspace

Authors: Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Linear matroid intersection is an important problem in combinatorial optimization. Given two linear matroids over the same ground set, the linear matroid intersection problem asks you to find a common independent set of maximum size. The deep interest in linear matroid intersection is due to the fact that it generalises many classical problems in theoretical computer science, such as bipartite matching, edge disjoint spanning trees, rainbow spanning tree, and many more. We study this problem in the model of catalytic computation: space-bounded machines are granted access to catalytic space, which is additional working memory that is full with arbitrary data that must be preserved at the end of its computation. Although linear matroid intersection has had a polynomial time algorithm for over 50 years, it remains an important open problem to show that linear matroid intersection belongs to any well studied subclass of {P}. We address this problem for the class catalytic logspace (CL) with a polynomial time bound (CLP). Recently, Agarwala and Mertz (2025) showed that bipartite maximum matching can be computed in the class CLP ⊆ {P}. This was the first subclass of {P} shown to contain bipartite matching, and additionally the first problem outside TC¹ shown to be contained in CL. We significantly improve the result of Agarwala and Mertz by showing that linear matroid intersection can be computed in CLP.
Cite as

Aryan Agarwala, Yaroslav Alekseev, and Antoine Vinciguerra. Linear Matroid Intersection Is in Catalytic Logspace. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwala_et_al:LIPIcs.ITCS.2026.3,
  author =	{Agarwala, Aryan and Alekseev, Yaroslav and Vinciguerra, Antoine},
  title =	{{Linear Matroid Intersection Is in Catalytic Logspace}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{3:1--3:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.3},
  URN =		{urn:nbn:de:0030-drops-252908},
  doi =		{10.4230/LIPIcs.ITCS.2026.3},
  annote =	{Keywords: Catalytic Computing, Computational Complexity, Matroid Theory, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.9
On Closure Properties of Read-Once Oblivious Algebraic Branching Programs

Authors: Robert Andrews, Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure under factoring: There is a sequence of explicit polynomials (f_n(x₁,…, x_n))_n that have poly(n)-sized roABPs such that some irreducible factor of f_n requires roABPs of superpolynomial size in any order. - Non-closure under powering: There is a sequence of polynomials (f_n(x₁,…, x_n))_n with poly(n)-sized roABPs such that any super-constant power of f_n does not have roABPs of polynomial size in any order (and f_nⁿ requires exponential size in any order). - Non-closure under symmetric operations: There are symmetric polynomials (f_n(e₁,…, e_n))_n that have roABPs of polynomial size such that f_n(x₁,…, x_n) do not have roABPs of subexponential size. (Here, e₁,…, e_n denote the elementary symmetric polynomials in n variables.) These results should be viewed in light of known results on models such as algebraic circuits, (general) algebraic branching programs, formulas and constant-depth circuits, all of which are known to be closed under these operations. To prove non-closure under factoring, we construct hard polynomials based on expander graphs using gadgets that lift their hardness from sparse polynomials to roABPs. For symmetric compositions, we show that the circulant polynomial requires roABPs of exponential size in every variable order.
Cite as

Robert Andrews, Jules Armand, Prateek Dwivedi, Magnus Rahbek Dalgaard Hansen, Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. On Closure Properties of Read-Once Oblivious Algebraic Branching Programs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{andrews_et_al:LIPIcs.ITCS.2026.9,
  author =	{Andrews, Robert and Armand, Jules and Dwivedi, Prateek and Hansen, Magnus Rahbek Dalgaard and Limaye, Nutan and Srinivasan, Srikanth and Tavenas, S\'{e}bastien},
  title =	{{On Closure Properties of Read-Once Oblivious Algebraic Branching Programs}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.9},
  URN =		{urn:nbn:de:0030-drops-252964},
  doi =		{10.4230/LIPIcs.ITCS.2026.9},
  annote =	{Keywords: Factoring, Closure Properties, Sparsity Bounds, Symmetric Polynomials, roABP, Expander Graphs}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.51
Randomized Black-Box PIT for Small Depth +-Regular Non-Commutative Circuits

Authors: G. V. Sumukha Bharadwaj and S. Raja

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

Abstract
In this paper, we address the black-box polynomial identity testing (PIT) problem for non-commutative polynomials computed by +-regular circuits, a class of homogeneous circuits introduced by Arvind, Joglekar, Mukhopadhyay, and Raja (STOC 2017, Theory of Computing 2019). These circuits can compute polynomials with a number of monomials that are doubly exponential in the circuit size. They gave an efficient randomized PIT algorithm for +-regular circuits of depth 3 and posed the problem of developing an efficient black-box PIT for higher depths as an open problem. Our work makes progress on this open problem by resolving it for constant-depth +-regular circuits. We present a randomized black-box polynomial-time algorithm for +-regular circuits of any constant depth. Specifically, our algorithm runs in s^{O(d²)} time, where s and d represent the size and the depth of the +-regular circuit, respectively. Our approach combines several key techniques in a novel way. We employ a nondeterministic substitution automaton that transforms the polynomial into a structured form and utilizes polynomial sparsification along with commutative transformations to maintain non-zeroness. Additionally, we introduce matrix composition, coefficient modification via the automaton, and multi-entry outputs - methods that have not previously been applied in the context of black-box PIT. Together, these techniques enable us to effectively handle exponential degrees and doubly exponential sparsity in non-commutative settings, enabling polynomial identity testing for higher-depth circuits. In particular, we show that if f is a non-zero non-commutative polynomial in n variables over the field 𝔽, computed by a depth-d +-regular circuit of size s, then f cannot be a polynomial identity for the matrix algebra 𝕄_{N}(𝔽), where N = s^{O(d²)} and the size of the field 𝔽 depends on the degree of f. Interestingly, the size of the matrices does not depend on the degree of f. Our result can be interpreted as an Amitsur-Levitzki-type result [Amitsur and Levitzki, 1950] for polynomials computed by small-depth +-regular circuits.
Cite as

G. V. Sumukha Bharadwaj and S. Raja. Randomized Black-Box PIT for Small Depth +-Regular Non-Commutative Circuits. 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. 51:1-51:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sumukhabharadwaj_et_al:LIPIcs.FSTTCS.2025.51,
  author =	{Sumukha Bharadwaj, G. V. and Raja, S.},
  title =	{{Randomized Black-Box PIT for Small Depth +-Regular Non-Commutative Circuits}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{51:1--51:16},
  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.51},
  URN =		{urn:nbn:de:0030-drops-250949},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.51},
  annote =	{Keywords: Polynomial Identity Testing, Non-commutative Circuits, Algebraic Circuits, +-Regular Circuits, Black-Box}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.21
On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers

Authors: Parinya Chalermsook, Ly Orgo, and Minoo Zarsav

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
This paper considers the Zarankiewicz problem in bipartite graphs with low-dimensional geometric representation (i.e., low Ferrers dimension). Let Z(n;k) be the maximum number of edges in a bipartite graph with n nodes and is free of a k-by-k biclique. Note that Z(n;k) ∈ Ω(nk) for all "natural" graph classes. Our first result reveals a separation between bipartite graphs of Ferrers dimension three and four: while we show that Z(n;k) ≤ 9n(k-1) for graphs of Ferrers dimension three, Z(n;k) ∈ Ω(n k ⋅ (log n)/(log log n)) for Ferrers dimension four graphs (Chan & Har-Peled, 2023) (Chazelle, 1990). To complement this, we derive a tight upper bound of 2n(k-1) for chordal bipartite graphs and 54n(k-1) for grid intersection graphs (GIG), a prominent graph class residing in four Ferrers dimensions and capturing planar bipartite graphs as well as bipartite intersection graphs of rectangles. Previously, the best-known bound for GIG was Z(n;k) ∈ O(2^{O(k)} n), implied by the results of Fox & Pach (2006) and Mustafa & Pach (2016). Our results advance and offer new insights into the interplay between Ferrers dimensions and extremal combinatorics.
Cite as

Parinya Chalermsook, Ly Orgo, and Minoo Zarsav. On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 21:1-21:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.GD.2025.21,
  author =	{Chalermsook, Parinya and Orgo, Ly and Zarsav, Minoo},
  title =	{{On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{21:1--21:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.21},
  URN =		{urn:nbn:de:0030-drops-250074},
  doi =		{10.4230/LIPIcs.GD.2025.21},
  annote =	{Keywords: Bipartite graph classes, extremal graph theory, geometric intersection graphs, Zarankiewicz problem, bicliques}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.56
Efficient Polynomial Identity Testing over Nonassociative Algebras

Authors: Partha Mukhopadhyay, C. Ramya, and Pratik Shastri

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

Abstract
We design the first efficient polynomial identity testing algorithms over the nonassociative polynomial algebra. In particular, multiplication among the formal variables is commutative but it is not associative. This complements the strong lower bound results obtained over this algebra by Hrubeš, Yehudayoff, and Wigderson [Pavel Hrubes et al., 2010] and Fijalkow, Lagarde, Ohlmann, and Serre [Fijalkow et al., 2021] from the identity testing perspective. Our main results are the following: - We construct nonassociative algebras (both commutative and noncommutative) which have no low degree identities. As a result, we obtain the first Amitsur-Levitzki type theorems [A. S. Amitsur and J. Levitzki, 1950] over nonassociative polynomial algebras. As a direct consequence, we obtain randomized polynomial-time black-box PIT algorithms for nonassociative polynomials which allow evaluation over such algebras. - On the derandomization side, we give a deterministic polynomial-time identity testing algorithm for nonassociative polynomials given by arithmetic circuits in the white-box setting. Previously, such an algorithm was known with the additional restriction of noncommutativity [Vikraman Arvind et al., 2017]. - In the black-box setting, we construct a hitting set of quasipolynomial-size for nonassociative polynomials computed by arithmetic circuits of small depth. Understanding the black-box complexity of identity testing, even in the randomized setting, was open prior to our work.
Cite as

Partha Mukhopadhyay, C. Ramya, and Pratik Shastri. Efficient Polynomial Identity Testing over Nonassociative Algebras. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 56:1-56:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mukhopadhyay_et_al:LIPIcs.APPROX/RANDOM.2025.56,
  author =	{Mukhopadhyay, Partha and C. Ramya and Shastri, Pratik},
  title =	{{Efficient Polynomial Identity Testing over Nonassociative Algebras}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{56:1--56:22},
  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.56},
  URN =		{urn:nbn:de:0030-drops-244224},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.56},
  annote =	{Keywords: Polynomial identity testing, nonassociative algebra, arithmetic circuits, black-box algorithms, white-box algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.51
Word Structures and Their Automatic Presentations

Authors: Xiaoyang Gong, Bakh Khoussainov, and Yuyang Zhuge

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

Abstract
We study automatic presentations of the structures (ℕ; S), (ℕ; E_S), (ℕ; ≤), and their expansions by a unary predicate U. Here S is the successor function, E_S is the undirected version of S, and ≤ is the natural order. We call these structures word structures. Our goal is three-fold. First, we study the isomorphism problem for automatic word structures by focusing on the following three problems. The first problem asks to design an algorithm that, given an automatic structure A, decides if A is isomorphic to (ℕ; S). The second asks to design an algorithm that, given two automatic presentations of (ℕ; S, U₁) and (ℕ; S, U₂), where U₁ and U₂ are unary predicates, decides if these structures are isomorphic. The third problem investigates if there is an algorithm that, given two automatic presentations of (ℕ; ≤, U₁) and (ℕ; ≤, U₂), decides whether U₁ ∩ U₂ ≠ ∅. We show that these problems are undecidable. Next, we study intrinsic regularity of the function S in the structure Path_ω = (ℕ; E_S). We build an automatic presentation of Path_ω in which S is not regular. This implies that S is not intrinsically regular in Path_ω. For U ⊆ ℕ, let d_U be the function that computes the distances between the consecutive elements of U. We build automatic presentations of (ℕ; ≤, U) where d_U can realise logarithmic, radical, intermediate, and exponential functions.
Cite as

Xiaoyang Gong, Bakh Khoussainov, and Yuyang Zhuge. Word Structures and Their Automatic Presentations. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gong_et_al:LIPIcs.MFCS.2025.51,
  author =	{Gong, Xiaoyang and Khoussainov, Bakh and Zhuge, Yuyang},
  title =	{{Word Structures and Their Automatic Presentations}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{51:1--51:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.51},
  URN =		{urn:nbn:de:0030-drops-241581},
  doi =		{10.4230/LIPIcs.MFCS.2025.51},
  annote =	{Keywords: Automatic structures, the isomorphism problem, decidability, undecidability, regular relations}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.19
Monotone Bounded-Depth Complexity of Homomorphism Polynomials

Authors: C.S. Bhargav, Shiteng Chen, Radu Curticapean, and Prateek Dwivedi

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

Abstract
For every fixed graph H, it is known that homomorphism counts from H and colorful H-subgraph counts can be determined in O(n^{t+1}) time on n-vertex input graphs G, where t is the treewidth of H. On the other hand, a running time of n^{o(t / log t)} would refute the exponential-time hypothesis. Komarath, Pandey, and Rahul (Algorithmica, 2023) studied algebraic variants of these counting problems, i.e., homomorphism and subgraph polynomials for fixed graphs H. These polynomials are weighted sums over the objects counted above, where each object is weighted by the product of variables corresponding to edges contained in the object. As shown by Komarath et al., the monotone circuit complexity of the homomorphism polynomial for H is Θ(n^{tw(H)+1}). In this paper, we characterize the power of monotone bounded-depth circuits for homomorphism and colorful subgraph polynomials. This leads us to discover a natural hierarchy of graph parameters tw_Δ(H), for fixed Δ ∈ ℕ, which capture the width of tree-decompositions for H when the underlying tree is required to have depth at most Δ. We prove that monotone circuits of product-depth Δ computing the homomorphism polynomial for H require size Θ(n^{tw_Δ(H^{†})+1}), where H^{†} is the graph obtained from H by removing all degree-1 vertices. This allows us to derive an optimal depth hierarchy theorem for monotone bounded-depth circuits through graph-theoretic arguments.
Cite as

C.S. Bhargav, Shiteng Chen, Radu Curticapean, and Prateek Dwivedi. Monotone Bounded-Depth Complexity of Homomorphism Polynomials. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhargav_et_al:LIPIcs.MFCS.2025.19,
  author =	{Bhargav, C.S. and Chen, Shiteng and Curticapean, Radu and Dwivedi, Prateek},
  title =	{{Monotone Bounded-Depth Complexity of Homomorphism Polynomials}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.19},
  URN =		{urn:nbn:de:0030-drops-241269},
  doi =		{10.4230/LIPIcs.MFCS.2025.19},
  annote =	{Keywords: algebraic complexity, homomorphisms, monotone circuit complexity, bounded-depth circuits, treewidth, pathwidth}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.79
Deciding Robust Instances of an Escape Problem for Dynamical Systems in Euclidean Space

Authors: Eike Neumann

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

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

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

Copy BibTex To Clipboard

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

Authors: S. Akshay, Ouldouz Neysari, and Ðorđe Žikelić

Published in: LIPIcs, Volume 348, 36th International Conference on Concurrency Theory (CONCUR 2025)

Abstract
A classical approach to studying Markov decision processes (MDPs) is to view them as state transformers. However, MDPs can also be viewed as distribution transformers, where an MDP under a strategy generates a sequence of probability distributions over MDP states. This view arises in several applications, even as the probabilistic model checking problem becomes much harder compared to the classical state transformer counterpart. It is known that even distributional reachability and safety problems become computationally intractable (Skolem- and positivity-hard). To address this challenge, recent works focused on sound but possibly incomplete methods for verification and control of MDPs under the distributional view. However, existing automated methods are applicable only to distributional reachability, safety and reach-avoidance specifications. In this work, we present the first automated method for verification and control of MDPs with respect to distributional omega-regular specifications. To achieve this, we propose a novel notion of distributional certificates, which are sound and complete proof rules for proving that an MDP under a distributionally memoryless strategy satisfies some distributional omega-regular specification. We then use our distributional certificates to design the first fully automated algorithms for verification and control of MDPs with respect to distributional omega-regular specifications. Our algorithms follow a template-based synthesis approach and provide soundness and relative completeness guarantees, while running in PSPACE. Our prototype implementation demonstrates practical applicability of our algorithms to challenging examples collected from the literature.
Cite as

S. Akshay, Ouldouz Neysari, and Ðorđe Žikelić. Omega-Regular Verification and Control for Distributional Specifications in MDPs. In 36th International Conference on Concurrency Theory (CONCUR 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 348, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{akshay_et_al:LIPIcs.CONCUR.2025.6,
  author =	{Akshay, S. and Neysari, Ouldouz and \v{Z}ikeli\'{c}, Ðor{\d}e},
  title =	{{Omega-Regular Verification and Control for Distributional Specifications in MDPs}},
  booktitle =	{36th International Conference on Concurrency Theory (CONCUR 2025)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-389-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{348},
  editor =	{Bouyer, Patricia and van de Pol, Jaco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2025.6},
  URN =		{urn:nbn:de:0030-drops-239562},
  doi =		{10.4230/LIPIcs.CONCUR.2025.6},
  annote =	{Keywords: MDPs, Distributional objectives, \omega-regularity, Certificates}
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.22
Enumerating All Boolean Matches

Authors: Alexander Nadel and Yogev Shalmon

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
Boolean matching, a fundamental problem in circuit design, determines whether two Boolean circuits are equivalent under input/output permutations and negations. While most works focus on finding a single match or proving its absence, the problem of enumerating all matches remains largely unexplored, with BooM being a notable exception. Motivated by timing challenges in Intel’s library mapping flow, we introduce EBat - an open-source tool for enumerating all matches between single-output circuits. Built from scratch, EBat reuses BooM’s SAT encoding and introduces novel high-level algorithms and performance-critical subroutines to efficiently identify and block multiple mismatches and matches simultaneously. Experiments demonstrate that EBat substantially outperforms BooM’s baseline algorithm, solving 3 to 4 times more benchmarks within a given time limit. EBat has been productized as part of Intel’s library mapping flow, effectively addressing the timing challenges.
Cite as

Alexander Nadel and Yogev Shalmon. Enumerating All Boolean Matches. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 22:1-22:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{nadel_et_al:LIPIcs.SAT.2025.22,
  author =	{Nadel, Alexander and Shalmon, Yogev},
  title =	{{Enumerating All Boolean Matches}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{22:1--22:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.22},
  URN =		{urn:nbn:de:0030-drops-237568},
  doi =		{10.4230/LIPIcs.SAT.2025.22},
  annote =	{Keywords: Boolean Matching, All-Boolean-Matching, Enumeration, SAT, Generalization}
}
  • Refine by Type
  • 41 Document/PDF
  • 19 Document/HTML

  • Refine by Publication Year
  • 7 2026
  • 12 2025
  • 1 2021
  • 1 2019
  • 1 2018
  • Show More...

  • Refine by Author
  • 8 Agrawal, Manindra
  • 8 Thierauf, Thomas
  • 5 Buhrman, Harry
  • 5 Fortnow, Lance
  • 4 Umans, Christopher
  • Show More...

  • Refine by Series/Journal
  • 24 LIPIcs
  • 2 DagRep
  • 15 DagSemProc

  • Refine by Classification
  • 9 Theory of computation → Algebraic complexity theory
  • 3 Theory of computation → Circuit complexity
  • 3 Theory of computation → Complexity classes
  • 2 Mathematics of computing → Graph theory
  • 1 Computing methodologies → Symbolic and algebraic manipulation
  • Show More...

  • Refine by Keyword
  • 5 Computational Complexity
  • 3 Polynomial Identity Testing
  • 3 derandomization
  • 3 lower bounds
  • 2 (de-) randomization
  • 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