Search Results

Documents authored by Dewan, Agrim

Document
DOI: 10.4230/LIPIcs.MFCS.2026.90
Testing Equivalence to the Hamiltonian Cycle Polynomial

Authors: Agrim Dewan

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
The Hamiltonian Cycle polynomial, denoted as HC_n, is defined to be the sum of the weighted Hamiltonian Cycles in an n-vertex complete digraph, with vertices labeled 1 to n and edges weighted by formal variables x_{i,j}. The Permanent and HC, defined as the family {HC_n | n ≥ 1}, were studied by Valiant (STOC 1979), with the former shown to be VNP-complete over all fields of characteristic other than 2, and the latter to be VNP-complete over every field. Since its introduction, HC has been studied from the perspective of circuit lower bounds by Jerrum-Snir (JACM 1982), determinantal complexity by Huttenhain-Ikenmeyer (LAA 2016), and its connection with the Permanent and the Determinant polynomials by Goulden-Jackson (EJC 1981) and Grochow (ToC 2017). It has been the most prominent choice for generalising results to all fields, such as in Malod (CCC 2007) and Grochow-Mulmuley-Qiao (ICALP 2016), owing to its VNP-completeness over every field. Hrubes (ToCT, 2016) showed the VNP-completeness of many graph-based polynomial families over every field by using HC. In Kayal (STOC 2012), a randomised polynomial time algorithm was given for the following problem: Given an n²-variate degree-n polynomial f(𝐱) ∈ 𝔽[𝐱] as a black box, decide if there exists A ∈ GL_{n²}(𝔽) such that f(𝐱) = Perm_n(A𝐱). Here, the Permanent polynomial Perm_n computes the permanent of the n × n symbolic matrix (x_{i,j}). This problem is known as testing equivalence to the Permanent, or alternatively, ET for Permanent. In this work, we study ET for HC. While both families are VNP-complete, the efficient ET algorithm for Permanent does not imply the same for HC. Besides, there are crucial differences between the two polynomials that make studying the complexity of ET for HC interesting: The underlying decision problem corresponding to the Permanent is in P (detecting perfect matchings in a bipartite graph), but that for HC (detecting Hamiltonian cycles in a digraph) is NP-complete. The Permanent polynomial is known to be characterised by its symmetries as shown by Mulmuley-Sohoni (SIAM J. Computing, 2001). This property yields an efficient algorithm for the circuit-testing problem for the Permanent, a special case of ET for the Permanent, in which we check whether a given circuit computes the Permanent. In contrast, we show HC_n is not characterised by its symmetries. In this work, we give a randomised polynomial time ET algorithm for HC with mild constraints on the underlying field. The algorithm is obtained by studying and completely characterising the Lie algebra and the symmetries of HC_n. We show that, like the Permanent polynomial, the symmetries of HC_n are generated by permutation and scaling matrices over large enough fields. However, we also show that, unlike the Permanent polynomial, HC_n is not characterised by its symmetries. Nevertheless, like the Permanent polynomial, HC_n is downward self-reducible, as shown in Zhang-Bai (TCS 2011), which implies HC_n is characterised by circuit identities and that we can efficiently test whether a given circuit C computes HC_n. We also get a Flip theorem for HC_n as a result of its circuit identities.
Cite as

Agrim Dewan. Testing Equivalence to the Hamiltonian Cycle Polynomial. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 90:1-90:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dewan:LIPIcs.MFCS.2026.90,
  author =	{Dewan, Agrim},
  title =	{{Testing Equivalence to the Hamiltonian Cycle Polynomial}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{90:1--90:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.90},
  URN =		{urn:nbn:de:0030-drops-274729},
  doi =		{10.4230/LIPIcs.MFCS.2026.90},
  annote =	{Keywords: Equivalence Testing, Hamiltonian Cycle Polynomial, Symmetries, Lie Algebra, Circuit identities}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.16
NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials

Authors: Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha

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

Abstract
An s-sparse polynomial has at most s monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial f is equivalent to (i.e., in the orbit of) some s-sparse polynomial. In other words, given f ∈ 𝔽[𝐱] and s ∈ ℕ, ETsparse asks to check if there exist A ∈ GL(|𝐱|, 𝔽) and 𝐛 ∈ 𝔽^|𝐱| such that f(A𝐱 + 𝐛) is s-sparse. We show that ETsparse is NP-hard over any field 𝔽, if f is given in the sparse representation, i.e., as a list of nonzero coefficients and exponent vectors. This answers a question posed by Gupta, Saha and Thankey (SODA 2023) and also, more explicitly, by Baraskar, Dewan and Saha (STACS 2024). The result implies that the Minimum Circuit Size Problem (MCSP) is NP-hard for a dense subclass of depth-3 arithmetic circuits if the input is given in sparse representation. We also show that approximating the smallest s₀ such that a given s-sparse polynomial f is in the orbit of some s₀-sparse polynomial to within a factor of s^{1/3 - ε} is NP-hard for any ε > 0; observe that s-factor approximation is trivial as the input is s-sparse. Finally, we show that for any constant σ ≥ 6, checking if a polynomial (given in sparse representation) is in the orbit of some support-σ polynomial is NP-hard. Support of a polynomial f is the maximum number of variables present in any monomial of f. These results are obtained via direct reductions from the 3-SAT problem.
Cite as

Omkar Baraskar, Agrim Dewan, Chandan Saha, and Pulkit Sinha. NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{baraskar_et_al:LIPIcs.ICALP.2024.16,
  author =	{Baraskar, Omkar and Dewan, Agrim and Saha, Chandan and Sinha, Pulkit},
  title =	{{NP-Hardness of Testing Equivalence to Sparse Polynomials and to Constant-Support Polynomials}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{16:1--16:21},
  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.16},
  URN =		{urn:nbn:de:0030-drops-201598},
  doi =		{10.4230/LIPIcs.ICALP.2024.16},
  annote =	{Keywords: Equivalence testing, MCSP, sparse polynomials, 3SAT}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.9
Testing Equivalence to Design Polynomials

Authors: Omkar Baraskar, Agrim Dewan, and Chandan Saha

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
An n-variate polynomial g of degree d is a (n,d,t) design polynomial if the degree of the gcd of every pair of monomials of g is at most t-1. The power symmetric polynomial PSym_{n,d} : = ∑_{i = 1}ⁿ x^d_i and the sum-product polynomial SP_{s,d} : = ∑_{i = 1}^{s}∏_{j = 1}^{d} x_{i,j} are instances of design polynomials for t = 1. Another example is the Nisan-Wigderson design polynomial NW, which has been used extensively to prove various arithmetic circuit lower bounds. Given black-box access to an n-variate, degree-d polynomial f(𝐱) ∈ 𝔽[𝐱], how fast can we check if there exist an A ∈ GL(n, 𝔽) and a 𝐛 ∈ 𝔽ⁿ such that f(A𝐱+𝐛) is a (n,d,t) design polynomial? We call this problem "testing equivalence to design polynomials", or alternatively, "equivalence testing for design polynomials". In this work, we present a randomized algorithm that finds (A, 𝐛) such that f(A𝐱+𝐛) is a (n,d,t) design polynomial, if such A and 𝐛 exist, provided t ≤ d/3. The algorithm runs in (nd)^O(t) time and works over any sufficiently large 𝔽 of characteristic 0 or > d. As applications of this test, we show two results - one is structural and the other is algorithmic. The structural result establishes a polynomial-time equivalence between the graph isomorphism problem and the polynomial equivalence problem for design polynomials. The algorithmic result implies that Patarin’s scheme (EUROCRYPT 1996) can be broken in quasi-polynomial time if a random sparse polynomial is used in the key generation phase. We also give an efficient learning algorithm for n-variate random affine projections of multilinear degree-d design polynomials, provided n ≥ d⁴. If one obtains an analogous result under the weaker assumption "n ≥ d^ε, for any ε > 0", then the NW family is not VNP-complete unless there is a VNP-complete family whose random affine projections are learnable. It is not known if random affine projections of the permanent are learnable. The above algorithms are obtained by using the vector space decomposition framework, introduced by Kayal and Saha (STOC 2019) and Garg, Kayal and Saha (FOCS 2020), for learning non-degenerate arithmetic circuits. A key technical difference between the analysis in the papers by Garg, Kayal and Saha (FOCS 2020) and Bhargava, Garg, Kayal and Saha (RANDOM 2022) and the analysis here is that a certain adjoint algebra, which turned out to be trivial (i.e., diagonalizable) in prior works, is non-trivial in our case. However, we show that the adjoint arising here is triangularizable which then helps in carrying out the vector space decomposition step.
Cite as

Omkar Baraskar, Agrim Dewan, and Chandan Saha. Testing Equivalence to Design Polynomials. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{baraskar_et_al:LIPIcs.STACS.2024.9,
  author =	{Baraskar, Omkar and Dewan, Agrim and Saha, Chandan},
  title =	{{Testing Equivalence to Design Polynomials}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.9},
  URN =		{urn:nbn:de:0030-drops-197193},
  doi =		{10.4230/LIPIcs.STACS.2024.9},
  annote =	{Keywords: Polynomial equivalence, design polynomials, graph isomorphism, vector space decomposition}
}
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