6 Search Results for "Guo, Zeyu"

Document
DOI: 10.4230/LIPIcs.CCC.2021.20
Variety Evasive Subspace Families

Authors: Zeyu Guo

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
We introduce the problem of constructing explicit variety evasive subspace families. Given a family ℱ of subvarieties of a projective or affine space, a collection ℋ of projective or affine k-subspaces is (ℱ,ε)-evasive if for every 𝒱 ∈ ℱ, all but at most ε-fraction of W ∈ ℋ intersect every irreducible component of 𝒱 with (at most) the expected dimension. The problem of constructing such an explicit subspace family generalizes both deterministic black-box polynomial identity testing (PIT) and the problem of constructing explicit (weak) lossless rank condensers. Using Chow forms, we construct explicit k-subspace families of polynomial size that are evasive for all varieties of bounded degree in a projective or affine n-space. As one application, we obtain a complete derandomization of Noether’s normalization lemma for varieties of bounded degree in a projective or affine n-space. In another application, we obtain a simple polynomial-time black-box PIT algorithm for depth-4 arithmetic circuits with bounded top fan-in and bottom fan-in that are not in the Sylvester-Gallai configuration, improving and simplifying a result of Gupta (ECCC TR 14-130). As a complement of our explicit construction, we prove a lower bound for the size of k-subspace families that are evasive for degree-d varieties in a projective n-space. When n-k = n^Ω(1), the lower bound is superpolynomial unless d is bounded. The proof uses a dimension-counting argument on Chow varieties that parametrize projective subvarieties.
Cite as

Zeyu Guo. Variety Evasive Subspace Families. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 20:1-20:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{guo:LIPIcs.CCC.2021.20,
  author =	{Guo, Zeyu},
  title =	{{Variety Evasive Subspace Families}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{20:1--20:33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.20},
  URN =		{urn:nbn:de:0030-drops-142949},
  doi =		{10.4230/LIPIcs.CCC.2021.20},
  annote =	{Keywords: algebraic complexity, dimension reduction, Noether normalization, polynomial identity testing, pseudorandomness, varieties}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.42
Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach

Authors: Zeyu Guo

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Let f̃(X) ∈ ℤ[X] be a degree-n polynomial such that f(X): = f̃(X)od p factorizes into n distinct linear factors over 𝔽_p. We study the problem of deterministically factoring f(X) over 𝔽_p given f̃(X). Under the generalized Riemann hypothesis (GRH), we give an improved deterministic algorithm that computes the complete factorization of f(X) in the case that the Galois group of f̃(X) is (permutation isomorphic to) a linear group G ≤ GL(V) on the set S of roots of f̃(X), where V is a finite-dimensional vector space over a finite field 𝔽 and S is identified with a subset of V. In particular, when |S| = |V|^{Ω(1)}, the algorithm runs in time polynomial in n^{log n/(log log log log n)^{1/3}} and the size of the input, improving Evdokimov’s algorithm. Our result also applies to a general Galois group G when combined with a recent algorithm of the author. To prove our main result, we introduce a family of objects called linear m-schemes and reduce the problem of factoring f(X) to a combinatorial problem about these objects. We then apply techniques from additive combinatorics to obtain an improved bound. Our techniques may be of independent interest.
Cite as

Zeyu Guo. Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{guo:LIPIcs.MFCS.2020.42,
  author =	{Guo, Zeyu},
  title =	{{Factoring Polynomials over Finite Fields with Linear Galois Groups: An Additive Combinatorics Approach}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.42},
  URN =		{urn:nbn:de:0030-drops-127082},
  doi =		{10.4230/LIPIcs.MFCS.2020.42},
  annote =	{Keywords: polynomial factoring, permutation group, finite field, algebraic combinatorics, additive combinatorics, derandomization}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.4
Improved Explicit Hitting-Sets for ROABPs

Authors: Zeyu Guo and Rohit Gurjar

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

Abstract
We give improved explicit constructions of hitting-sets for read-once oblivious algebraic branching programs (ROABPs) and related models. For ROABPs in an unknown variable order, our hitting-set has size polynomial in (nr)^{(log n)/(max{1, log log n-log log r})}d over a field whose characteristic is zero or large enough, where n is the number of variables, d is the individual degree, and r is the width of the ROABP. A similar improved construction works over fields of arbitrary characteristic with a weaker size bound. Based on a result of Bisht and Saxena (2020), we also give an improved explicit construction of hitting-sets for sum of several ROABPs. In particular, when the characteristic of the field is zero or large enough, we give polynomial-size explicit hitting-sets for sum of constantly many log-variate ROABPs of width r = 2^{O(log d/log log d)}. Finally, we give improved explicit hitting-sets for polynomials computable by width-r ROABPs in any variable order, also known as any-order ROABPs. Our hitting-set has polynomial size for width r up to 2^{O(log(nd)/log log(nd))} or 2^{O(log^{1-ε} (nd))}, depending on the characteristic of the field. Previously, explicit hitting-sets of polynomial size are unknown for r = ω(1).
Cite as

Zeyu Guo and Rohit Gurjar. Improved Explicit Hitting-Sets for ROABPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.APPROX/RANDOM.2020.4,
  author =	{Guo, Zeyu and Gurjar, Rohit},
  title =	{{Improved Explicit Hitting-Sets for ROABPs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.4},
  URN =		{urn:nbn:de:0030-drops-126076},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.4},
  annote =	{Keywords: polynomial identity testing, hitting-set, ROABP, arithmetic branching programs, derandomization}
}
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-dev.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.2018.10
Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity

Authors: Zeyu Guo, Nitin Saxena, and Amit Sinhababu

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

Abstract
Testing whether a set f of polynomials has an algebraic dependence is a basic problem with several applications. The polynomials are given as algebraic circuits. Algebraic independence testing question is wide open over finite fields (Dvir, Gabizon, Wigderson, FOCS'07). Previously, the best complexity known was NP^{#P} (Mittmann, Saxena, Scheiblechner, Trans.AMS'14). In this work we put the problem in AM cap coAM. In particular, dependence testing is unlikely to be NP-hard and joins the league of problems of "intermediate" complexity, eg. graph isomorphism & integer factoring. Our proof method is algebro-geometric- estimating the size of the image/preimage of the polynomial map f over the finite field. A gap in this size is utilized in the AM protocols. Next, we study the open question of testing whether every annihilator of f has zero constant term (Kayal, CCC'09). We give a geometric characterization using Zariski closure of the image of f; introducing a new problem called approximate polynomials satisfiability (APS). We show that APS is NP-hard and, using projective algebraic-geometry ideas, we put APS in PSPACE (prior best was EXPSPACE via Gröbner basis computation). As an unexpected application of this to approximative complexity theory we get- over any field, hitting-sets for overline{VP} can be verified in PSPACE. This solves an open problem posed in (Mulmuley, FOCS'12, J.AMS 2017); greatly mitigating the GCT Chasm (exponentially in terms of space complexity).
Cite as

Zeyu Guo, Nitin Saxena, and Amit Sinhababu. Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.CCC.2018.10,
  author =	{Guo, Zeyu and Saxena, Nitin and Sinhababu, Amit},
  title =	{{Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{10:1--10:21},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.10},
  URN =		{urn:nbn:de:0030-drops-88786},
  doi =		{10.4230/LIPIcs.CCC.2018.10},
  annote =	{Keywords: algebraic dependence, Jacobian, Arthur-Merlin, approximate polynomial, satisfiability, hitting-set, border VP, finite field, PSPACE, EXPSPACE, GCT Chasm}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.47
Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields

Authors: Zeyu Guo, Anand Kumar Narayanan, and Chris Umans

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
The fastest known algorithm for factoring univariate polynomials over finite fields is the Kedlaya-Umans (fast modular composition) implementation of the Kaltofen-Shoup algorithm. It is randomized and takes ~O(n^{3/2}*log(q)+n*log^2(q)) time to factor polynomials of degree n over the finite field F_q with q elements. A significant open problem is if the 3/2 exponent can be improved. We study a collection of algebraic problems and establish a web of reductions between them. A consequence is that an algorithm for any one of these problems with exponent better than 3/2 would yield an algorithm for polynomial factorization with exponent better than 3/2.
Cite as

Zeyu Guo, Anand Kumar Narayanan, and Chris Umans. Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.MFCS.2016.47,
  author =	{Guo, Zeyu and Narayanan, Anand Kumar and Umans, Chris},
  title =	{{Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{47:1--47:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.47},
  URN =		{urn:nbn:de:0030-drops-64609},
  doi =		{10.4230/LIPIcs.MFCS.2016.47},
  annote =	{Keywords: algorithms, complexity, finite fields, polynomials, factorization}
}
  • Refine by Author
  • 5 Guo, Zeyu
  • 2 Sinhababu, Amit
  • 1 Gurjar, Rohit
  • 1 Narayanan, Anand Kumar
  • 1 Saxena, Nitin
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Algebraic complexity theory
  • 2 Mathematics of computing → Computations in finite fields
  • 2 Mathematics of computing → Computations on polynomials
  • 2 Theory of computation → Pseudorandomness and derandomization
  • 1 Computing methodologies → Algebraic algorithms
  • Show More...

  • Refine by Keyword
  • 2 derandomization
  • 2 finite field
  • 2 hitting-set
  • 2 polynomial identity testing
  • 1 Arithmetic Branching Program
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2020
  • 1 2016
  • 1 2018
  • 1 2021

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