11 Search Results for "Derksen, Harm"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.32
Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem

Authors: Jin-Yi Cai and Ben Young

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

Abstract
Valiant’s Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets ℱ and 𝒢 of tensors (a.k.a. constraint functions or signatures) are related by a holographic transformation, then ℱ and 𝒢 are Holant-indistinguishable, i.e., every tensor network using tensors from ℱ, respectively from 𝒢, contracts to the same value. Xia (ICALP 2010) conjectured the converse of the Holant theorem, but a counterexample was found based on vanishing signatures, those which are Holant-indistinguishable from 0. We prove two near-converses of the Holant theorem using techniques from invariant theory. (I) Holant-indistinguishable ℱ and 𝒢 always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their GL_q-orbit closures intersect. (II) We show that vanishing signatures are the only true obstacle to a converse of the Holant theorem. As corollaries of the two theorems we obtain the first characterization of homomorphism-indistinguishability over graphs of bounded degree, a long standing open problem, and show that two graphs with invertible adjacency matrices are isomorphic if and only if they are homomorphism-indistinguishable over graphs with maximum degree at most three. We also show that Holant-indistinguishability is complete for a complexity class TOCI introduced by Lysikov and Walter [Vladimir Lysikov and Michael Walter, 2024], and hence hard for graph isomorphism.
Cite as

Jin-Yi Cai and Ben Young. Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.ITCS.2026.32,
  author =	{Cai, Jin-Yi and Young, Ben},
  title =	{{Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{32:1--32:20},
  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.32},
  URN =		{urn:nbn:de:0030-drops-253198},
  doi =		{10.4230/LIPIcs.ITCS.2026.32},
  annote =	{Keywords: Holant, Orbit Closure Intersection, Homomorphism Indistinguishability, Tensor Network}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.90
Slice Rank and Partition Rank of the Determinant

Authors: Amichai Lampert and Guy Moshkovitz

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

Abstract
The Laplace expansion expresses the n × n determinant det_n as a sum of n products. Do shorter expansions exist? In this paper we: - Fully determine the slice rank decompositions of det_n (where each product must contain a linear factor): In this case, we show that n summands are necessary, and moreover, the only such expansions with n summands are equivalent (in a precise sense) to the Laplace expansion. - Prove a logarithmic lower bound for the partition rank of det_n (where each product is of multilinear forms): In this case, we show that at least log₂(n)+1 summands are needed and we explain why existing techniques fail to yield any nontrivial lower bound. - Separate partition rank from slice rank for det_n: we find a quadratic expansion for det₄, over any field, with fewer summands than the Laplace expansion. This construction is related to a well-known example of Green-Tao and Lovett-Meshulam-Samorodnitsky disproving the naive version of the Gowers Inverse conjecture over small fields. An important motivation for these questions comes from the challenge of separating structure and randomness for tensors. On the one hand, we show that the random construction fails to separate: for a random tensor of partition rank r, the analytic rank is r-o(1) with high probability. On the other hand, our results imply that the determinant yields the first asymptotic separation between partition rank and analytic rank of d-tensors, with their ratio tending to infinity with d.
Cite as

Amichai Lampert and Guy Moshkovitz. Slice Rank and Partition Rank of the Determinant. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 90:1-90:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lampert_et_al:LIPIcs.ITCS.2026.90,
  author =	{Lampert, Amichai and Moshkovitz, Guy},
  title =	{{Slice Rank and Partition Rank of the Determinant}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{90:1--90:15},
  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.90},
  URN =		{urn:nbn:de:0030-drops-253779},
  doi =		{10.4230/LIPIcs.ITCS.2026.90},
  annote =	{Keywords: Slice rank, partition rank, determinant}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.1
List Decoding Quotient Reed-Muller Codes

Authors: Omri Gotlib, Tali Kaufman, and Shachar Lovett

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Reed-Muller codes consist of evaluations of n-variate polynomials over a finite field 𝔽 with degree at most d. Much like every linear code, Reed-Muller codes can be characterized by constraints, where a codeword is valid if and only if it satisfies all degree-d constraints. For a subset X̃ ⊆ 𝔽ⁿ, we introduce the notion of X̃-quotient Reed-Muller code. A function F:X̃ → 𝔽 is a valid codeword in the quotient code if it satisfies all the constraints of degree-d polynomials lying in X̃. This gives rise to a novel phenomenon: a quotient codeword may have many extensions to original codewords. This weakens the connection between original codewords and quotient codewords which introduces a richer range of behaviors along with substantial new challenges. Our goal is to answer the following question: what properties of X̃ will imply that the quotient code inherits its distance and list-decoding radius from the original code? We address this question using techniques developed by Bhowmick and Lovett [Abhishek Bhowmick and Shachar Lovett, 2014], identifying key properties of 𝔽ⁿ used in their proof and extending them to general subsets X̃ ⊆ 𝔽ⁿ. By introducing a new tool, we overcome the novel challenge in analyzing the quotient code that arises from the weak connection between original and quotient codewords. This enables us to apply known results from additive combinatorics and algebraic geometry [David Kazhdan and Tamar Ziegler, 2018; David Kazhdan and Tamar Ziegler, 2019; Amichai Lampert and Tamar Ziegler, 2021] to show that when X̃ is a high rank variety, X̃-quotient Reed-Muller codes inherit the distance and list-decoding parameters from the original Reed-Muller codes.
Cite as

Omri Gotlib, Tali Kaufman, and Shachar Lovett. List Decoding Quotient Reed-Muller Codes. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 1:1-1:44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gotlib_et_al:LIPIcs.CCC.2025.1,
  author =	{Gotlib, Omri and Kaufman, Tali and Lovett, Shachar},
  title =	{{List Decoding Quotient Reed-Muller Codes}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{1:1--1:44},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.1},
  URN =		{urn:nbn:de:0030-drops-236957},
  doi =		{10.4230/LIPIcs.CCC.2025.1},
  annote =	{Keywords: Reed-Muller Codes, Quotient Code, Quotient Reed-Muller Code, List Decoding, High Rank Variety, High-Order Fourier Analysis, Error-Correcting Codes}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.9
Pseudorandom Bits for Non-Commutative Programs

Authors: Chin Ho Lee and Emanuele Viola

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We obtain new explicit pseudorandom generators for several computational models involving groups. Our main results are as follows: 1) We consider read-once group-products over a finite group G, i.e., tests of the form ∏_{i=1}^n (g_i)^{x_i} where g_i ∈ G, a special case of read-once permutation branching programs. We give generators with optimal seed length c_G log(n/ε) over any p-group. The proof uses the small-bias plus noise paradigm, but derandomizes the noise to avoid the recursion in previous work. Our generator works when the bits are read in any order. Previously for any non-commutative group the best seed length was ≥ log n log(1/ε), even for a fixed order. 2) We give a reduction that "lifts" suitable generators for group products over G to a generator that fools width-w block products, i.e., tests of the form ∏ (g_i)^{f_i} where the f_i are arbitrary functions on disjoint blocks of w bits. Block products generalize several previously studied classes. The reduction applies to groups that are mixing in a representation-theoretic sense that we identify. 3) Combining (2) with (1) and other works we obtain new generators for block products over the quaternions or over any commutative group, with nearly optimal seed length. In particular, we obtain generators for read-once polynomials modulo any fixed m with nearly optimal seed length. Previously this was known only for m = 2. 4) We give a new generator for products over "mixing groups." The construction departs from previous work and uses representation theory. For constant error, we obtain optimal seed length, improving on previous work (which applied to any group). This paper identifies a challenge in the area that is reminiscent of a roadblock in circuit complexity - handling composite moduli - and points to several classes of groups to be attacked next.
Cite as

Chin Ho Lee and Emanuele Viola. Pseudorandom Bits for Non-Commutative Programs. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.CCC.2025.9,
  author =	{Lee, Chin Ho and Viola, Emanuele},
  title =	{{Pseudorandom Bits for Non-Commutative Programs}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.9},
  URN =		{urn:nbn:de:0030-drops-237039},
  doi =		{10.4230/LIPIcs.CCC.2025.9},
  annote =	{Keywords: Group programs, Space-bounded derandomization, Representation theory}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.28
Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition

Authors: Vishwas Bhargava and Devansh Shringi

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

Abstract
We present a deterministic 2^{k^{𝒪(1)}} poly(n,d) time algorithm for decomposing d-dimensional, width-n tensors of rank at most k over ℝ and ℂ. This improves upon the previous randomized algorithm of Peleg, Shpilka, and Volk (ITCS '24) that takes 2^{k^{k^{𝒪(k)}}} poly(n,d) time and the deterministic n^k^k time algorithms of Bhargava, Saraf, and Volkovich (STOC '21). Our work resolves an open question asked by Peleg, Shpilka, and Volk (ITCS '24) on whether a deterministic Fixed Parameter Tractable (FPT) algorithm exists for worst-case tensor decomposition. We also make substantial progress on the fundamental problem of how the tractability of tensor decomposition varies as the tensor rank increases. Our result implies that we can achieve deterministic polynomial-time decomposition as long as the rank of the tensor is at most (log n)^{1/C}, where C is some fixed constant independent of n and d. Further, we note that there cannot exist a polynomial-time algorithm for k = ω(log n) unless ETH fails. Our algorithm works for all fields; however, the time complexity worsens to 2^{k^{k^{𝒪(1)}}} and requires randomization for finite fields of large characteristics. Both conditions are provably necessary unless there are improvements in the state of the art for system solving over the corresponding fields. Our approach achieves this by designing a proper learning (reconstruction) algorithm for set-multilinear depth-3 arithmetic circuits. On a technical note, we design a "partial" clustering algorithm for set-multilinear depth-3 arithmetic circuits that lets us isolate a cluster from any set-multilinear depth-3 circuit while preserving the structure of the circuit.
Cite as

Vishwas Bhargava and Devansh Shringi. Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhargava_et_al:LIPIcs.ICALP.2025.28,
  author =	{Bhargava, Vishwas and Shringi, Devansh},
  title =	{{Faster \& Deterministic FPT Algorithm for Worst-Case Tensor Decomposition}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.28},
  URN =		{urn:nbn:de:0030-drops-234052},
  doi =		{10.4230/LIPIcs.ICALP.2025.28},
  annote =	{Keywords: Algebraic circuits, Deterministic algorithms, FPT algorithm, Learning circuits, Reconstruction, Tensor Decomposition, Tensor Rank}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.154
Submonoid Membership in n-Dimensional Lamplighter Groups and S-Unit Equations

Authors: Ruiwen Dong

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

Abstract
We show that Submonoid Membership is decidable in n-dimensional lamplighter groups (ℤ/pℤ) ≀ ℤⁿ for any prime p and integer n. More generally, we show decidability of Submonoid Membership in semidirect products of the form 𝒴 ⋊ ℤⁿ, where 𝒴 is any finitely presented module over the Laurent polynomial ring 𝔽_p[X₁^{±}, …, X_n^{±}]. Combined with a result of Shafrir (2024), this gives the first example of a group G and a finite index subgroup G̃ ≤ G, such that Submonoid Membership is decidable in G̃ but undecidable in G. To obtain our decidability result, we reduce Submonoid Membership in 𝒴 ⋊ ℤⁿ to solving S-unit equations over 𝔽_p[X₁^{±}, …, X_n^{±}]-modules. We show that the solution set of such equations is effectively p-automatic, extending a result of Adamczewski and Bell (2012). As an intermediate result, we also obtain that the solution set of the Knapsack Problem in 𝒴 ⋊ ℤⁿ is effectively p-automatic.
Cite as

Ruiwen Dong. Submonoid Membership in n-Dimensional Lamplighter Groups and S-Unit Equations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 154:1-154:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dong:LIPIcs.ICALP.2025.154,
  author =	{Dong, Ruiwen},
  title =	{{Submonoid Membership in n-Dimensional Lamplighter Groups and S-Unit Equations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{154:1--154:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.154},
  URN =		{urn:nbn:de:0030-drops-235316},
  doi =		{10.4230/LIPIcs.ICALP.2025.154},
  annote =	{Keywords: Submonoid Membership, lamplighter groups, S-unit equations, p-automatic sets, Knapsack in groups}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.99
Algorithmic Aspects of Semistability of Quiver Representations

Authors: Yuni Iwamasa, Taihei Oki, and Tasuku Soma

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

Abstract
We study the semistability of quiver representations from an algorithmic perspective. We present efficient algorithms for several fundamental computational problems on the semistability of quiver representations: deciding the semistability and σ-semistability, finding the maximizers of King’s criterion, and computing the Harder-Narasimhan filtration. We also investigate a class of polyhedral cones defined by the linear system in King’s criterion, which we refer to as King cones. For rank-one representations, we demonstrate that these King cones can be encoded by submodular flow polytopes, enabling us to decide the σ-semistability in strongly polynomial time. Our approach employs submodularity in quiver representations, which may be of independent interest.
Cite as

Yuni Iwamasa, Taihei Oki, and Tasuku Soma. Algorithmic Aspects of Semistability of Quiver Representations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 99:1-99:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{iwamasa_et_al:LIPIcs.ICALP.2025.99,
  author =	{Iwamasa, Yuni and Oki, Taihei and Soma, Tasuku},
  title =	{{Algorithmic Aspects of Semistability of Quiver Representations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{99:1--99:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.99},
  URN =		{urn:nbn:de:0030-drops-234762},
  doi =		{10.4230/LIPIcs.ICALP.2025.99},
  annote =	{Keywords: quivers, \sigma-semistability, King’s criterion, operator scaling, submodular flow}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.18
Pseudorandomness, Symmetry, Smoothing: I

Authors: Harm Derksen, Peter Ivanov, Chin Ho Lee, and Emanuele Viola

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
We prove several new results about bounded uniform and small-bias distributions. A main message is that, small-bias, even perturbed with noise, does not fool several classes of tests better than bounded uniformity. We prove this for threshold tests, small-space algorithms, and small-depth circuits. In particular, we obtain small-bias distributions that - achieve an optimal lower bound on their statistical distance to any bounded-uniform distribution. This closes a line of research initiated by Alon, Goldreich, and Mansour in 2003, and improves on a result by O'Donnell and Zhao. - have heavier tail mass than the uniform distribution. This answers a question posed by several researchers including Bun and Steinke. - rule out a popular paradigm for constructing pseudorandom generators, originating in a 1989 work by Ajtai and Wigderson. This again answers a question raised by several researchers. For branching programs, our result matches a bound by Forbes and Kelley. Our small-bias distributions above are symmetric. We show that the xor of any two symmetric small-bias distributions fools any bounded function. Hence our examples cannot be extended to the xor of two small-bias distributions, another popular paradigm whose power remains unknown. We also generalize and simplify the proof of a result of Bazzi.
Cite as

Harm Derksen, Peter Ivanov, Chin Ho Lee, and Emanuele Viola. Pseudorandomness, Symmetry, Smoothing: I. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 18:1-18:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{derksen_et_al:LIPIcs.CCC.2024.18,
  author =	{Derksen, Harm and Ivanov, Peter and Lee, Chin Ho and Viola, Emanuele},
  title =	{{Pseudorandomness, Symmetry, Smoothing: I}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{18:1--18:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.18},
  URN =		{urn:nbn:de:0030-drops-204144},
  doi =		{10.4230/LIPIcs.CCC.2024.18},
  annote =	{Keywords: pseudorandomness, k-wise uniform distributions, small-bias distributions, noise, symmetric tests, thresholds, Krawtchouk polynomials}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.6
On Identity Testing and Noncommutative Rank Computation over the Free Skew Field

Authors: V. Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, and C. Ramya

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
The identity testing of rational formulas (RIT) in the free skew field efficiently reduces to computing the rank of a matrix whose entries are linear polynomials in noncommuting variables [Hrubeš and Wigderson, 2015]. This rank computation problem has deterministic polynomial-time white-box algorithms [Ankit Garg et al., 2016; Ivanyos et al., 2018] and a randomized polynomial-time algorithm in the black-box setting [Harm Derksen and Visu Makam, 2017]. In this paper, we propose a new approach for efficient derandomization of black-box RIT. Additionally, we obtain results for matrix rank computation over the free skew field and construct efficient linear pencil representations for a new class of rational expressions. More precisely, we show: - Under the hardness assumption that the ABP (algebraic branching program) complexity of every polynomial identity for the k×k matrix algebra is 2^Ω(k) [Andrej Bogdanov and Hoeteck Wee, 2005], we obtain a subexponential-time black-box RIT algorithm for rational formulas of inversion height almost logarithmic in the size of the formula. This can be seen as the first "hardness implies derandomization" type theorem for rational formulas. - We show that the noncommutative rank of any matrix over the free skew field whose entries have small linear pencil representations can be computed in deterministic polynomial time. While an efficient rank computation was known for matrices with noncommutative formulas as entries [Ankit Garg et al., 2020], we obtain the first deterministic polynomial-time algorithms for rank computation of matrices whose entries are noncommutative ABPs or rational formulas. - Motivated by the definition given by Bergman [George M Bergman, 1976], we define a new class of rational functions where a rational function of inversion height at most h is defined as a composition of a noncommutative r-skewed circuit (equivalently an ABP) with inverses of rational functions of this class of inversion height at most h-1 which are also disjoint. We obtain a polynomial-size linear pencil representation for this class which gives a white-box deterministic polynomial-time identity testing algorithm for the class.
Cite as

V. Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, and C. Ramya. On Identity Testing and Noncommutative Rank Computation over the Free Skew Field. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.ITCS.2023.6,
  author =	{Arvind, V. and Chatterjee, Abhranil and Ghosal, Utsab and Mukhopadhyay, Partha and Ramya, C.},
  title =	{{On Identity Testing and Noncommutative Rank Computation over the Free Skew Field}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.6},
  URN =		{urn:nbn:de:0030-drops-175093},
  doi =		{10.4230/LIPIcs.ITCS.2023.6},
  annote =	{Keywords: Algebraic Complexity, Identity Testing, Non-commutative rank}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.9
Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors

Authors: Harm Derksen, Visu Makam, and Jeroen Zuiddam

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
Since the seminal works of Strassen and Valiant it has been a central theme in algebraic complexity theory to understand the relative complexity of algebraic problems, that is, to understand which algebraic problems (be it bilinear maps like matrix multiplication in Strassen’s work, or the determinant and permanent polynomials in Valiant’s) can be reduced to each other (under the appropriate notion of reduction). In this paper we work in the setting of bilinear maps and with the usual notion of reduction that allows applying linear maps to the inputs and output of a bilinear map in order to compute another bilinear map. As our main result we determine precisely how many independent scalar multiplications can be reduced to a given bilinear map (this number is called the subrank, and extends the concept of matrix diagonalization to tensors), for essentially all (i.e. generic) bilinear maps. Namely, we prove for a generic bilinear map T : V × V → V where dim(V) = n that θ(√n) independent scalar multiplications can be reduced to T. Our result significantly improves on the previous upper bound from the work of Strassen (1991) and Bürgisser (1990) which was n^{2/3 + o(1)}. Our result is very precise and tight up to an additive constant. Our full result is much more general and applies not only to bilinear maps and 3-tensors but also to k-tensors, for which we find that the generic subrank is θ(n^{1/(k-1)}). Moreover, as an application we prove that the subrank is not additive under the direct sum. The subrank plays a central role in several areas of complexity theory (matrix multiplication algorithms, barrier results) and combinatorics (e.g., the cap set problem and sunflower problem). As a consequence of our result we obtain several large separations between the subrank and tensor methods that have received much interest recently, notably the slice rank (Tao, 2016), analytic rank (Gowers-Wolf, 2011; Lovett, 2018; Bhrushundi-Harsha-Hatami-Kopparty-Kumar, 2020), geometric rank (Kopparty-Moshkovitz-Zuiddam, 2020), and G-stable rank (Derksen, 2020). Our proofs of the lower bounds rely on a new technical result about an optimal decomposition of tensor space into structured subspaces, which we think may be of independent interest.
Cite as

Harm Derksen, Visu Makam, and Jeroen Zuiddam. Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{derksen_et_al:LIPIcs.CCC.2022.9,
  author =	{Derksen, Harm and Makam, Visu and Zuiddam, Jeroen},
  title =	{{Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.9},
  URN =		{urn:nbn:de:0030-drops-165716},
  doi =		{10.4230/LIPIcs.CCC.2022.9},
  annote =	{Keywords: tensors, bilinear maps, complexity, subrank, diagonalization, generic tensors, random tensors, reduction, slice rank}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.57
Efficient Black-Box Identity Testing for Free Group Algebras

Authors: V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay

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

Abstract
Hrubeš and Wigderson [Pavel Hrubeš and Avi Wigderson, 2014] initiated the study of noncommutative arithmetic circuits with division computing a noncommutative rational function in the free skew field, and raised the question of rational identity testing. For noncommutative formulas with inverses the problem can be solved in deterministic polynomial time in the white-box model [Ankit Garg et al., 2016; Ivanyos et al., 2018]. It can be solved in randomized polynomial time in the black-box model [Harm Derksen and Visu Makam, 2017], where the running time is polynomial in the size of the formula. The complexity of identity testing of noncommutative rational functions, in general, remains open for noncommutative circuits with inverses. We solve the problem for a natural special case. We consider expressions in the free group algebra F(X,X^{-1}) where X={x_1, x_2, ..., x_n}. Our main results are the following. 1) Given a degree d expression f in F(X,X^{-1}) as a black-box, we obtain a randomized poly(n,d) algorithm to check whether f is an identically zero expression or not. The technical contribution is an Amitsur-Levitzki type theorem [A. S. Amitsur and J. Levitzki, 1950] for F(X, X^{-1}). This also yields a deterministic identity testing algorithm (and even an expression reconstruction algorithm) that is polynomial time in the sparsity of the input expression. 2) Given an expression f in F(X,X^{-1}) of degree D and sparsity s, as black-box, we can check whether f is identically zero or not in randomized poly(n,log s, log D) time. This yields a randomized polynomial-time algorithm when D and s are exponential in n.
Cite as

V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Efficient Black-Box Identity Testing for Free Group Algebras. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.APPROX-RANDOM.2019.57,
  author =	{Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha},
  title =	{{Efficient Black-Box Identity Testing for Free Group Algebras}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{57:1--57:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.57},
  URN =		{urn:nbn:de:0030-drops-112723},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.57},
  annote =	{Keywords: Rational identity testing, Free group algebra, Noncommutative computation, Randomized algorithms}
}
  • Refine by Type
  • 11 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 5 2025
  • 1 2024
  • 1 2023
  • 1 2022
  • Show More...

  • Refine by Author
  • 2 Arvind, V.
  • 2 Chatterjee, Abhranil
  • 2 Derksen, Harm
  • 2 Lee, Chin Ho
  • 2 Mukhopadhyay, Partha
  • Show More...

  • Refine by Series/Journal
  • 11 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Algebraic complexity theory
  • 4 Theory of computation → Pseudorandomness and derandomization
  • 1 Computing methodologies → Algebraic algorithms
  • 1 Computing methodologies → Symbolic and algebraic manipulation
  • 1 Mathematics of computing → Coding theory
  • Show More...

  • Refine by Keyword
  • 1 Algebraic Complexity
  • 1 Algebraic circuits
  • 1 Deterministic algorithms
  • 1 Error-Correcting Codes
  • 1 FPT algorithm
  • 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