8 Search Results for "Korwar, Arpita"

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.ESA.2025.19
On Finding 𝓁-Th Smallest Perfect Matchings

Authors: Nicolas El Maalouly, Sebastian Haslebacher, Adrian Taubner, and Lasse Wulf

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Given an undirected weighted graph G and an integer k, Exact-Weight Perfect Matching (EWPM) is the problem of finding a perfect matching of weight exactly k in G. In this paper, we study EWPM and its variants. The EWPM problem is famous, since in the case of unary encoded weights, Mulmuley, Vazirani, and Vazirani showed almost 40 years ago that the problem can be solved in randomized polynomial time. However, up to this date no derandomization is known. Our first result is a simple deterministic algorithm for EWPM that runs in time n^𝒪(𝓁), where 𝓁 is the number of distinct weights that perfect matchings in G can take. In fact, we show how to find an 𝓁-th smallest perfect matching in any weighted graph (even if the weights are encoded in binary, in which case EWPM in general is known to be NP-complete) in time n^𝒪(𝓁) for any integer 𝓁. Similar next-to-optimal variants have also been studied recently for the shortest path problem. For our second result, we extend the list of problems that are known to be equivalent to EWPM. We show that EWPM is equivalent under a weight-preserving reduction to the Exact Cycle Sum problem (ECS) in undirected graphs with a conservative (i.e. no negative cycles) weight function. To the best of our knowledge, we are the first to study this problem. As a consequence, the latter problem is contained in RP if the weights are encoded in unary. Finally, we identify a special case of EWPM, called BCPM, which was recently studied by El Maalouly, Steiner and Wulf. We show that BCPM is equivalent under a weight-preserving transformation to another problem recently studied by Schlotter and Sebő as well as Geelen and Kapadia: the Shortest Odd Cycle problem (SOC) in undirected graphs with conservative weights. Finally, our n^𝒪(𝓁) algorithm works in this setting as well, identifying a tractable special case of SOC, BCPM, and ECS.
Cite as

Nicolas El Maalouly, Sebastian Haslebacher, Adrian Taubner, and Lasse Wulf. On Finding 𝓁-Th Smallest Perfect Matchings. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{elmaalouly_et_al:LIPIcs.ESA.2025.19,
  author =	{El Maalouly, Nicolas and Haslebacher, Sebastian and Taubner, Adrian and Wulf, Lasse},
  title =	{{On Finding 𝓁-Th Smallest Perfect Matchings}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.19},
  URN =		{urn:nbn:de:0030-drops-244875},
  doi =		{10.4230/LIPIcs.ESA.2025.19},
  annote =	{Keywords: Exact Matching, Perfect Matching, Exact-Weight Perfect Matching, Shortest Odd Cycle, Exact Cycle Sum, l-th Smallest Solution, l-th Largest Solution, k-th Best Solution, Derandomization}
}
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.ITCS.2022.119
Polynomial Identity Testing via Evaluation of Rational Functions

Authors: Dieter van Melkebeek and Andrew Morgan

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We introduce a hitting set generator for Polynomial Identity Testing based on evaluations of low-degree univariate rational functions at abscissas associated with the variables. In spite of the univariate nature, we establish an equivalence up to rescaling with a generator introduced by Shpilka and Volkovich, which has a similar structure but uses multivariate polynomials in the abscissas. We study the power of the generator by characterizing its vanishing ideal, i.e., the set of polynomials that it fails to hit. Capitalizing on the univariate nature, we develop a small collection of polynomials that jointly produce the vanishing ideal. As corollaries, we obtain tight bounds on the minimum degree, sparseness, and partition size of set-multi-linearity in the vanishing ideal. Inspired by an alternating algebra representation, we develop a structured deterministic membership test for the vanishing ideal. As a proof of concept we rederive known derandomization results based on the generator by Shpilka and Volkovich, and present a new application for read-once oblivious arithmetic branching programs that provably transcends the usual combinatorial techniques.
Cite as

Dieter van Melkebeek and Andrew Morgan. Polynomial Identity Testing via Evaluation of Rational Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 119:1-119:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vanmelkebeek_et_al:LIPIcs.ITCS.2022.119,
  author =	{van Melkebeek, Dieter and Morgan, Andrew},
  title =	{{Polynomial Identity Testing via Evaluation of Rational Functions}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{119:1--119:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.119},
  URN =		{urn:nbn:de:0030-drops-157158},
  doi =		{10.4230/LIPIcs.ITCS.2022.119},
  annote =	{Keywords: Derandomization, Gr\"{o}bner Basis, Lower Bounds, Polynomial Identity Testing}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.33
Factorization of Polynomials Given By Arithmetic Branching Programs

Authors: Amit Sinhababu and Thomas Thierauf

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size s, we show that all its factors can be computed by arithmetic branching programs of size poly(s). Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was poly(s^(log s)).
Cite as

Amit Sinhababu and Thomas Thierauf. Factorization of Polynomials Given By Arithmetic Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{sinhababu_et_al:LIPIcs.CCC.2020.33,
  author =	{Sinhababu, Amit and Thierauf, Thomas},
  title =	{{Factorization of Polynomials Given By Arithmetic Branching Programs}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  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.CCC.2020.33},
  URN =		{urn:nbn:de:0030-drops-125854},
  doi =		{10.4230/LIPIcs.CCC.2020.33},
  annote =	{Keywords: Arithmetic Branching Program, Multivariate Polynomial Factorization, Hensel Lifting, Newton Iteration, Hardness vs Randomness}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.29
Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs

Authors: Rohit Gurjar, Arpita Korwar, and Nitin Saxena

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We give improved hitting-sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known variable order. The best hitting-set known for this case had cost (nw)^{O(log(n))}, where n is the number of variables and w is the width of the ROABP. Even for a constant-width ROABP, nothing better than a quasi-polynomial bound was known. We improve the hitting-set complexity for the known-order case to n^{O(log(w))}. In particular, this gives the first polynomial time hitting-set for constant-width ROABP (known-order). However, our hitting-set works only over those fields whose characteristic is zero or large enough. To construct the hitting-set, we use the concept of the rank of partial derivative matrix. Unlike previous approaches whose starting point is a monomial map, we use a polynomial map directly. The second case we consider is that of commutative ROABP. The best known hitting-set for this case had cost d^{O(log(w))}(nw)^{O(log(log(w)))}, where d is the individual degree. We improve this hitting-set complexity to (ndw)^{O(log(log(w)))}. We get this by achieving rank concentration more efficiently.
Cite as

Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.CCC.2016.29,
  author =	{Gurjar, Rohit and Korwar, Arpita and Saxena, Nitin},
  title =	{{Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.29},
  URN =		{urn:nbn:de:0030-drops-58438},
  doi =		{10.4230/LIPIcs.CCC.2016.29},
  annote =	{Keywords: PIT, hitting-set, constant-width ROABPs, commutative ROABPs}
}
Document
DOI: 10.4230/LIPIcs.CCC.2015.323
Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs

Authors: Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf

Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)

Abstract
A read-once oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity n^(O(log(n))). In both the cases, our time complexity is double exponential in the number of ROABPs. ROABPs are a generalization of set-multilinear depth-3 circuits. The prior results for the sum of constantly many set-multilinear depth-3 circuits were only slightly better than brute-force, i.e. exponential-time. Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives).
Cite as

Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 323-346, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.CCC.2015.323,
  author =	{Gurjar, Rohit and Korwar, Arpita and Saxena, Nitin and Thierauf, Thomas},
  title =	{{Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs}},
  booktitle =	{30th Conference on Computational Complexity (CCC 2015)},
  pages =	{323--346},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-81-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{33},
  editor =	{Zuckerman, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.323},
  URN =		{urn:nbn:de:0030-drops-50647},
  doi =		{10.4230/LIPIcs.CCC.2015.323},
  annote =	{Keywords: PIT, Hitting-set, Sum of ROABPs, Evaluation Dimension, Rank Concentration}
}
  • Refine by Type
  • 8 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2025
  • 1 2022
  • 1 2020
  • 1 2016
  • Show More...

  • Refine by Author
  • 2 Gurjar, Rohit
  • 2 Korwar, Arpita
  • 2 Saxena, Nitin
  • 2 Thierauf, Thomas
  • 1 Andrews, Robert
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Algebraic complexity theory
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 2 Derandomization
  • 2 PIT
  • 2 Polynomial Identity Testing
  • 1 +-Regular Circuits
  • 1 Algebraic Circuits
  • 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