Search Results

Documents authored by Volkovich, Ilya

Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.9
Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae

Authors: Pranav Bisht, Nikhil Gupta, and Ilya Volkovich

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
An arithmetic formula is an arithmetic circuit where each gate has fan-out one. An arithmetic read-once formula (ROF in short) is an arithmetic formula where each input variable labels at most one leaf. In this paper we present several efficient blackbox polynomial identity testing (PIT) algorithms for some classes of polynomials related to read-once formulas. Namely, for polynomial of the form: - f = Φ_1 ⋅ … ⋅ Φ_m + Ψ₁ ⋅ … ⋅ Ψ_r, where Φ_i,Ψ_j are ROFs for every i ∈ [m], j ∈ [r]. - f = Φ_1^{e₁} + Φ₂^{e₂} + Φ₃^{e₃}, where each Φ_i is an ROF and e_i-s are arbitrary positive integers. Earlier, only a whitebox polynomial-time algorithm was known for the former class by Mahajan, Rao and Sreenivasaiah (Algorithmica 2016). In the same paper, they also posed an open problem to come up with an efficient PIT algorithm for the class of polynomials of the form f = Φ_1^{e₁} + Φ_2^{e₂} + … + Φ_k^{e_k}, where each Φ_i is an ROF and k is some constant. Our second result answers this partially by giving a polynomial-time algorithm when k = 3. More generally, when each Φ₁,Φ₂,Φ₃ is a multilinear bounded-read formulae, we also give a quasi-polynomial-time blackbox PIT algorithm. Our main technique relies on the hardness of representation approach introduced in Shpilka and Volkovich (Computational Complexity 2015). Specifically, we show hardness of representation for the resultant polynomial of two ROFs in our first result. For our second result, we lift hardness of representation for a sum of three ROFs to sum of their powers.
Cite as

Pranav Bisht, Nikhil Gupta, and Ilya Volkovich. Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bisht_et_al:LIPIcs.FSTTCS.2023.9,
  author =	{Bisht, Pranav and Gupta, Nikhil and Volkovich, Ilya},
  title =	{{Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.9},
  URN =		{urn:nbn:de:0030-drops-193829},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.9},
  annote =	{Keywords: Identity Testing, Derandomization, Bounded-Read Formulae, Arithmetic Formulas}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.31
Synergy Between Circuit Obfuscation and Circuit Minimization

Authors: Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich

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

Abstract
We study close connections between Indistinguishability Obfuscation (IO) and the Minimum Circuit Size Problem (MCSP), and argue that efficient algorithms/construction for MCSP and IO create a synergy. Some of our main results are: - If there exists a perfect (imperfect) IO that is computationally secure against nonuniform polynomial-size circuits, then for all k ∈ ℕ: NP ∩ ZPP^{MCSP} ⊈ SIZE[n^k] (MA ∩ ZPP^{MCSP} ⊈ SIZE[n^k]). - In addition, if there exists a perfect IO that is computationally secure against nonuniform polynomial-size circuits, then NEXP ∩ ZPEXP^{MCSP} ⊈ P/poly. - If MCSP ∈ BPP, then statistical security and computational security for IO are equivalent. - If computationally-secure perfect IO exists, then MCSP ∈ BPP iff NP = ZPP. - If computationally-secure perfect IO exists, then ZPEXP ≠ BPP. To the best of our knowledge, this is the first consequence of strong circuit lower bounds from the existence of an IO. The results are obtained via a construction of an optimal universal distinguisher, computable in randomized polynomial time with access to the MCSP oracle, that will distinguish any two circuit-samplable distributions with the advantage that is the statistical distance between these two distributions minus some negligible error term. This is our main technical contribution. As another immediate application, we get a simple proof of the result by Allender and Das (Inf. Comput., 2017) that SZK ⊆ BPP^{MCSP}.
Cite as

Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. Synergy Between Circuit Obfuscation and Circuit Minimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{impagliazzo_et_al:LIPIcs.APPROX/RANDOM.2023.31,
  author =	{Impagliazzo, Russell and Kabanets, Valentine and Volkovich, Ilya},
  title =	{{Synergy Between Circuit Obfuscation and Circuit Minimization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{31:1--31:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.31},
  URN =		{urn:nbn:de:0030-drops-188569},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.31},
  annote =	{Keywords: Minimal Circuit Size Problem (MCSP), Circuit Lower Bounds, Complexity Classes, Indistinguishability Obfuscation, Separation of Classes, Statistical Distance}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.10
On Solving Sparse Polynomial Factorization Related Problems

Authors: Pranav Bisht and Ilya Volkovich

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first factor sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most s terms and individual degree bounded by d can itself have at most s^O(d²log n) terms. It is conjectured, though, that the "true" sparsity bound should be polynomial (i.e. s^poly(d)). In this paper we provide supporting evidence for this conjecture by presenting polynomial-time algorithms for several problems that would be implied by a polynomial-size sparsity bound. In particular, we give efficient (deterministic) algorithms for identity testing of Σ^[2]ΠΣΠ^[ind-deg d] circuits and testing if a sparse polynomial is an exact power. Hence, our algorithms rely on different techniques.
Cite as

Pranav Bisht and Ilya Volkovich. On Solving Sparse Polynomial Factorization Related Problems. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bisht_et_al:LIPIcs.FSTTCS.2022.10,
  author =	{Bisht, Pranav and Volkovich, Ilya},
  title =	{{On Solving Sparse Polynomial Factorization Related Problems}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.10},
  URN =		{urn:nbn:de:0030-drops-174023},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.10},
  annote =	{Keywords: Sparse Polynomials, Identity Testing, Derandomization, Factor-Sparsity, Multivariate Polynomial Factorization}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.7
One-Way Functions and a Conditional Variant of MKTP

Authors: Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence for the average-case hardness of some natural NP-complete problem. In this paper, we make progress on this question by studying a conditional variant of the Minimum KT-complexity Problem (MKTP), which we call McKTP, as follows. 1) First, we prove that if McKTP is average-case hard on a polynomial fraction of its instances, then there exist OWFs. 2) Then, we observe that McKTP is NP-complete under polynomial-time randomized reductions. 3) Finally, we prove that the existence of OWFs implies the nontrivial average-case hardness of McKTP. Thus the existence of OWFs is inextricably linked to the average-case hardness of this NP-complete problem. In fact, building on recently-announced results of Ren and Santhanam [Rahul Ilango et al., 2021], we show that McKTP is hard-on-average if and only if there are logspace-computable OWFs.
Cite as

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich. One-Way Functions and a Conditional Variant of MKTP. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{allender_et_al:LIPIcs.FSTTCS.2021.7,
  author =	{Allender, Eric and Cheraghchi, Mahdi and Myrisiotis, Dimitrios and Tirumala, Harsha and Volkovich, Ilya},
  title =	{{One-Way Functions and a Conditional Variant of MKTP}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.7},
  URN =		{urn:nbn:de:0030-drops-155181},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.7},
  annote =	{Keywords: Kolmogorov complexity, KT Complexity, Minimum KT-complexity Problem, MKTP, Conditional KT Complexity, Minimum Conditional KT-complexity Problem, McKTP, one-way functions, OWFs, average-case hardness, pseudorandom generators, PRGs, pseudorandom functions, PRFs, distinguishers, learning algorithms, NP-completeness, reductions}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.17
Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function

Authors: Yang Du and Ilya Volkovich

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
In this work we devise the first efficient deterministic algorithm for approximating ω(N) - the number of prime factors of an integer N ∈ ℕ, given in addition oracle access to Euler’s Totient function Φ(⋅). We also show that the algorithm can be extended to handle a more general class of additive functions that "depend solely on the exponents in the prime factorization of an integer". In particular, our result gives the first algorithm that approximates ω(N) without necessarily factoring N. Indeed, all the previously known algorithms for computing or even approximating ω(N) entail factorization of N, and therefore are either randomized [M. O. Rabin, 1980; D. L. Long, 1981] or require the Generalized Riemann Hypothesis (GRH) [G. L. Miller, 1976]. Our approach combines an application of Coppersmith’s method for finding non-trivial factors of integers whose prime factors satisfy certain "relative size" conditions of [F. Morain et al., 2018], together with a new upper bound on Φ(N) in terms of ω(N) which could be of independent interest.
Cite as

Yang Du and Ilya Volkovich. Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 17:1-17:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{du_et_al:LIPIcs.FSTTCS.2021.17,
  author =	{Du, Yang and Volkovich, Ilya},
  title =	{{Approximating the Number of Prime Factors Given an Oracle to Euler’s Totient Function}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{17:1--17:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.17},
  URN =		{urn:nbn:de:0030-drops-155286},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.17},
  annote =	{Keywords: Euler’s Totient Function, Integer Factorization, Number of Prime Factors, Derandomization}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2019.21
The Complexity of Finding S-Factors in Regular Graphs

Authors: Sanjana Kolisetty, Linh Le, Ilya Volkovich, and Mihalis Yannakakis

Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)

Abstract
A graph G has an S-factor if there exists a spanning subgraph F of G such that for all v in V: deg_F(v) in S. The simplest example of such factor is a 1-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational complexity of finding S-factors in regular graphs. Our techniques combine some classical as well as recent tools from graph theory.
Cite as

Sanjana Kolisetty, Linh Le, Ilya Volkovich, and Mihalis Yannakakis. The Complexity of Finding S-Factors in Regular Graphs. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 21:1-21:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kolisetty_et_al:LIPIcs.FSTTCS.2019.21,
  author =	{Kolisetty, Sanjana and Le, Linh and Volkovich, Ilya and Yannakakis, Mihalis},
  title =	{{The Complexity of Finding S-Factors in Regular Graphs}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{21:1--21:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Chattopadhyay, Arkadev and Gastin, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.21},
  URN =		{urn:nbn:de:0030-drops-115834},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.21},
  annote =	{Keywords: constraint satisfaction problem, Dichotomy theorem, Graph Factors, Regular Graphs}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.7
The Power of Natural Properties as Oracles

Authors: Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP). We show that in a number of complexity-theoretic results that use the SAT oracle, one can use the MCSP oracle instead. For example, we show that ZPEXP^{MCSP} !subseteq P/poly, which should be contrasted with the previously known circuit lower bound ZPEXP^{NP} !subseteq P/poly. We also show that, assuming the existence of Indistinguishability Obfuscators (IO), SAT and MCSP are equivalent in the sense that one has a ZPP algorithm if and only the other one does. We interpret our results as providing some evidence that MCSP may be NP-hard under randomized polynomial-time reductions.
Cite as

Russell Impagliazzo, Valentine Kabanets, and Ilya Volkovich. The Power of Natural Properties as Oracles. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{impagliazzo_et_al:LIPIcs.CCC.2018.7,
  author =	{Impagliazzo, Russell and Kabanets, Valentine and Volkovich, Ilya},
  title =	{{The Power of Natural Properties as Oracles}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{7:1--7:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.7},
  URN =		{urn:nbn:de:0030-drops-88824},
  doi =		{10.4230/LIPIcs.CCC.2018.7},
  annote =	{Keywords: natural properties, Minimal Circuit Size Problem (MCSP), circuit lower bounds, hardness of MCSP, learning algorithms, obfuscation, Indistinguishability Obfuscators (IO)}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.48
On Some Computations on Sparse Polynomials

Authors: Ilya Volkovich

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

Abstract
In arithmetic circuit complexity the standard operations are +,x. Yet, in some scenarios exponentiation gates are considered as well. In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power. Among applications, we show that: * A reconstruction algorithm for a circuit class c can be extended to handle f^e for f in C. * There exists an efficient deterministic algorithm for factoring sparse multiquadratic polynomials. * There is a deterministic algorithm for testing a factorization of sparse polynomials, with constant individual degrees, into sparse irreducible factors. That is, testing if f = g_1 x ... x g_m when f has constant individual degrees and g_i-s are irreducible. * There is a deterministic reconstruction algorithm for multilinear depth-4 circuits with two multiplication gates. * There exists an efficient deterministic algorithm for testing whether two powers of sparse polynomials are equal. That is, f^d = g^e when f and g are sparse.
Cite as

Ilya Volkovich. On Some Computations on Sparse Polynomials. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 48:1-48:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{volkovich:LIPIcs.APPROX-RANDOM.2017.48,
  author =	{Volkovich, Ilya},
  title =	{{On Some Computations on Sparse Polynomials}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{48:1--48:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.48},
  URN =		{urn:nbn:de:0030-drops-75976},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.48},
  annote =	{Keywords: Derandomization, Arithmetic Circuits, Reconstruction}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.32
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

Authors: Daniel Minahan and Ilya Volkovich

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
In this paper we study the identity testing problem of arithmetic read-once formulas (ROF) and some related models. A read-once formula is formula (a circuit whose underlying graph is a tree) in which the operations are {+,x} and such that every input variable labels at most one leaf. We obtain the first polynomial-time deterministic identity testing algorithm that operates in the black-box setting for read-once formulas, as well as some other related models. As an application, we obtain the first polynomial-time deterministic reconstruction algorithm for such formulas. Our results are obtained by improving and extending the analysis of the algorithm of [Shpilka-Volkovich, 2015]
Cite as

Daniel Minahan and Ilya Volkovich. Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{minahan_et_al:LIPIcs.CCC.2017.32,
  author =	{Minahan, Daniel and Volkovich, Ilya},
  title =	{{Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{32:1--32:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.32},
  URN =		{urn:nbn:de:0030-drops-75128},
  doi =		{10.4230/LIPIcs.CCC.2017.32},
  annote =	{Keywords: Derandomization, Read-Once Formulas, Identity Testing, Arithmetic Circuits, Reconstruction}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.943
Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials

Authors: Ilya Volkovich

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

Abstract
We present the first efficient deterministic algorithm for factoring sparse polynomials that split into multilinear factors and sums of univariate polynomials. Our result makes partial progress towards the resolution of the classical question posed by von zur Gathen and Kaltofen in [von zur Gathen/Kaltofen, J. Comp. Sys. Sci., 1985] to devise an efficient deterministic algorithm for factoring (general) sparse polynomials. We achieve our goal by introducing essential factorization schemes which can be thought of as a relaxation of the regular factorization notion.
Cite as

Ilya Volkovich. Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 943-958, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{volkovich:LIPIcs.APPROX-RANDOM.2015.943,
  author =	{Volkovich, Ilya},
  title =	{{Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{943--958},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.943},
  URN =		{urn:nbn:de:0030-drops-53469},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.943},
  annote =	{Keywords: Derandomization, Multivariate Polynomial Factorization, Sparse polynomials}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact