8 Search Results for "Joglekar, Pushkar S."

Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.47
The Algebraic Cost of a Boolean Sum

Authors: Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, and Amir Yehudayoff

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

Abstract
It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despite its similar expression. We study the question of why the VNP-completeness proof of the permanent fails for the determinant. We isolate three fundamental properties that are sufficient to prove a polynomial sequence is VNP-hard, of which two are shared by both the permanent and the determinant. We proceed to show that the permanent satisfies the third property, which we refer to as the "cost of a boolean sum", while the determinant does not, showcasing the fundamental difference between the polynomial families. We further note that this differentiation also applies in the border complexity setting and that our results apply for counting complexity.
Cite as

Ian Orzel, Srikanth Srinivasan, Sébastien Tavenas, and Amir Yehudayoff. The Algebraic Cost of a Boolean Sum. 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. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{orzel_et_al:LIPIcs.FSTTCS.2025.47,
  author =	{Orzel, Ian and Srinivasan, Srikanth and Tavenas, S\'{e}bastien and Yehudayoff, Amir},
  title =	{{The Algebraic Cost of a Boolean Sum}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{47:1--47:13},
  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.47},
  URN =		{urn:nbn:de:0030-drops-251271},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.47},
  annote =	{Keywords: Algebraic Complexity, Computational Complexity, Permanent, Determinant}
}
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.STACS.2025.53
On Read-k Projections of the Determinant

Authors: Pavel Hrubeš and Pushkar S. Joglekar

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We consider read-k determinantal representations of polynomials and prove some non-expressibility results. A square matrix M whose entries are variables or field elements will be called read-k, if every variable occurs at most k times in M. It will be called a determinantal representation of a polynomial f if f = det(M). We show that - the n × n permanent polynomial does not have a read-k determinantal representation for k ∈ o(√n/log n) (over a field of characteristic different from two). We also obtain a quantitative strengthening of this result by giving a similar non-expressibility for k ∈ o(√n/log n) for an explicit n-variate multilinear polynomial (as opposed to the permanent which is n²-variate).
Cite as

Pavel Hrubeš and Pushkar S. Joglekar. On Read-k Projections of the Determinant. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 53:1-53:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hrubes_et_al:LIPIcs.STACS.2025.53,
  author =	{Hrube\v{s}, Pavel and Joglekar, Pushkar S.},
  title =	{{On Read-k Projections of the Determinant}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{53:1--53:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.53},
  URN =		{urn:nbn:de:0030-drops-228785},
  doi =		{10.4230/LIPIcs.STACS.2025.53},
  annote =	{Keywords: determinant, permanent, projection of determinant, VNP completeness of permanent}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.14
A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results

Authors: Vikraman Arvind and Pushkar S. Joglekar

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We study the noncommutative rank problem, ncRANK, of computing the rank of matrices with linear entries in n noncommuting variables and the problem of noncommutative Rational Identity Testing, RIT, which is to decide if a given rational formula in n noncommuting variables is zero on its domain of definition. Motivated by the question whether these problems have deterministic NC algorithms, we revisit their interrelationship from a parallel complexity point of view. We show the following results: 1) Based on Cohn’s embedding theorem [Cohn, 1990; Cohn, 2006] we show deterministic NC reductions from multivariate ncRANK to bivariate ncRANK and from multivariate RIT to bivariate RIT. 2) We obtain a deterministic NC-Turing reduction from bivariate RIT to bivariate ncRANK, thereby proving that a deterministic NC algorithm for bivariate ncRANK would imply that both multivariate RIT and multivariate ncRANK are in deterministic NC.
Cite as

Vikraman Arvind and Pushkar S. Joglekar. A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.ICALP.2024.14,
  author =	{Arvind, Vikraman and Joglekar, Pushkar S.},
  title =	{{A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.14},
  URN =		{urn:nbn:de:0030-drops-201571},
  doi =		{10.4230/LIPIcs.ICALP.2024.14},
  annote =	{Keywords: noncommutative rank, rational formulas, identity testing, parallel complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.14
Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization

Authors: Vikraman Arvind and Pushkar S. Joglekar

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Based on a theorem of Bergman [Cohn, 2006] we show that multivariate noncommutative polynomial factorization is deterministic polynomial-time reducible to the factorization of bivariate noncommutative polynomials. More precisely, we show the following: 1) In the white-box setting, given an n-variate noncommutative polynomial f ∈ 𝔽⟨X⟩ over a field 𝔽 (either a finite field or the rationals) as an arithmetic circuit (or algebraic branching program), computing a complete factorization of f into irreducible factors is deterministic polynomial-time reducible to white-box factorization of a noncommutative bivariate polynomial g ∈ 𝔽⟨x,y⟩; the reduction transforms f into a circuit for g (resp. ABP for g), and given a complete factorization of g (namely, arithmetic circuits (resp. ABPs) for irreducible factors of g) the reduction recovers a complete factorization of f in polynomial time. We also obtain a similar deterministic polynomial-time reduction in the black-box setting. 2) Additionally, we show over the field of rationals that bivariate linear matrix factorization of 4× 4 matrices is at least as hard as factoring square-free integers. This indicates that reducing noncommutative polynomial factorization to linear matrix factorization (as done in [Vikraman Arvind and Pushkar S. Joglekar, 2022]) is unlikely to succeed over the field of rationals even in the bivariate case. In contrast, multivariate linear matrix factorization for 3×3 matrices over rationals is in polynomial time.
Cite as

Vikraman Arvind and Pushkar S. Joglekar. Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.MFCS.2023.14,
  author =	{Arvind, Vikraman and Joglekar, Pushkar S.},
  title =	{{Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.14},
  URN =		{urn:nbn:de:0030-drops-185480},
  doi =		{10.4230/LIPIcs.MFCS.2023.14},
  annote =	{Keywords: Arithmetic circuits, algebraic branching programs, polynomial factorization, automata, noncommutative polynomial ring}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.12
On Efficient Noncommutative Polynomial Factorization via Higman Linearization

Authors: Vikraman Arvind and Pushkar S. Joglekar

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

Abstract
In this paper we study the problem of efficiently factorizing polynomials in the free noncommutative ring 𝔽∠{x_1,x_2,…,x_n} of polynomials in noncommuting variables x_1,x_2,…,x_n over the field 𝔽. We obtain the following result: - We give a randomized algorithm that takes as input a noncommutative arithmetic formula of size s computing a noncommutative polynomial f ∈ 𝔽∠{x_1,x_2,…,x_n}, where 𝔽 = 𝔽_q is a finite field, and in time polynomial in s, n and log₂q computes a factorization of f as a product f = f_1f_2 ⋯ f_r, where each f_i is an irreducible polynomial that is output as a noncommutative algebraic branching program. - The algorithm works by first transforming f into a linear matrix L using Higman’s linearization of polynomials. We then factorize the linear matrix L and recover the factorization of f. We use basic elements from Cohn’s theory of free ideals rings combined with Ronyai’s randomized polynomial-time algorithm for computing invariant subspaces of a collection of matrices over finite fields.
Cite as

Vikraman Arvind and Pushkar S. Joglekar. On Efficient Noncommutative Polynomial Factorization via Higman Linearization. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.CCC.2022.12,
  author =	{Arvind, Vikraman and Joglekar, Pushkar S.},
  title =	{{On Efficient Noncommutative Polynomial Factorization via Higman Linearization}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{12:1--12:22},
  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.12},
  URN =		{urn:nbn:de:0030-drops-165747},
  doi =		{10.4230/LIPIcs.CCC.2022.12},
  annote =	{Keywords: Noncommutative Polynomials, Arithmetic Circuits, Factorization, Identity testing}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2304
Arithmetic Circuits and the Hadamard Product of Polynomials

Authors: Vikraman Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
Motivated by the Hadamard product of matrices we define the Hadamard product of multivariate polynomials and study its arithmetic circuit and branching program complexity. We also give applications and connections to polynomial identity testing. Our main results are the following. \begin{itemize} \item[$\bullet$] We show that noncommutative polynomial identity testing for algebraic branching programs over rationals is complete for the logspace counting class $\ceql$, and over fields of characteristic $p$ the problem is in $\ModpL/\Poly$. \item[$\bullet$] We show an exponential lower bound for expressing the Raz-Yehudayoff polynomial as the Hadamard product of two monotone multilinear polynomials. In contrast the Permanent can be expressed as the Hadamard product of two monotone multilinear formulas of quadratic size. \end{itemize}
Cite as

Vikraman Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan. Arithmetic Circuits and the Hadamard Product of Polynomials. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 25-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2009.2304,
  author =	{Arvind, Vikraman and Joglekar, Pushkar S. and Srinivasan, Srikanth},
  title =	{{Arithmetic Circuits and the Hadamard Product of Polynomials}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{25--36},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2304},
  URN =		{urn:nbn:de:0030-drops-23046},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2304},
  annote =	{Keywords: Hadamard product, identity testing, lower bounds, algebraic branching programs}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2008.1738
Some Sieving Algorithms for Lattice Problems

Authors: V. Arvind and Pushkar S. Joglekar

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

Abstract
We study the algorithmic complexity of lattice problems based on the sieving technique due to Ajtai, Kumar, and Sivakumar~\cite{aks}. Given a $k$-dimensional subspace $M\subseteq \R^n$ and a full rank integer lattice $\L\subseteq \Q^n$, the \emph{subspace avoiding problem} SAP, defined by Bl\"omer and Naewe \cite{blomer}, is to find a shortest vector in $\L\setminus M$. We first give a $2^{O(n+k \log k)}$ time algorithm to solve \emph{the subspace avoiding problem}. Applying this algorithm we obtain the following results. \begin{enumerate} \item We give a $2^{O(n)}$ time algorithm to compute $i^{th}$ successive minima of a full rank lattice $\L\subset \Q^n$ if $i$ is $O(\frac{n}{\log n})$. \item We give a $2^{O(n)}$ time algorithm to solve a restricted \emph{closest vector problem CVP} where the inputs fulfil a promise about the distance of the input vector from the lattice. \item We also show that unrestricted CVP has a $2^{O(n)}$ exact algorithm if there is a $2^{O(n)}$ time exact algorithm for solving CVP with additional input $v_i\in \L, 1\leq i\leq n$, where $\|v_i\|_p$ is the $i^{th}$ successive minima of $\L$ for each $i$. \end{enumerate} We also give a new approximation algorithm for SAP and the \emph{Convex Body Avoiding problem} which is a generalization of SAP. Several of our algorithms work for \emph{gauge} functions as metric, where the gauge function has a natural restriction and is accessed by an oracle.
Cite as

V. Arvind and Pushkar S. Joglekar. Some Sieving Algorithms for Lattice Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 25-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.FSTTCS.2008.1738,
  author =	{Arvind, V. and Joglekar, Pushkar S.},
  title =	{{Some Sieving Algorithms for Lattice Problems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{25--36},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1738},
  URN =		{urn:nbn:de:0030-drops-17380},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1738},
  annote =	{Keywords: Lattice problems, sieving algorithm, closest vector problem}
}
  • Refine by Type
  • 8 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 3 2025
  • 1 2024
  • 1 2023
  • 1 2022
  • 1 2009
  • Show More...

  • Refine by Author
  • 6 Joglekar, Pushkar S.
  • 4 Arvind, Vikraman
  • 2 Srinivasan, Srikanth
  • 1 Arvind, V.
  • 1 Hrubeš, Pavel
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 6 Theory of computation → Algebraic complexity theory

  • Refine by Keyword
  • 2 algebraic branching programs
  • 2 identity testing
  • 1 +-Regular Circuits
  • 1 Algebraic Circuits
  • 1 Algebraic Complexity
  • 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