The complexity of solving a random polynomial system

• URL: http://arxiv.org/abs/2309.03855v1
• Date: Thu, 7 Sep 2023 17:14:59 GMT
• Title: The complexity of solving a random polynomial system
• Authors: Giulia Gaggero, Elisa Gorla,
• Abstract summary: In this paper there is an overview on a general algorithm used to solve a multivariate system. We then speak about random systems and in particular what "random" means to us. We give an upper bound on both the degree of regularity and the solving degree of such random systems.
• Score: 3.420117005350141
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A multivariate cryptograpic instance in practice is a multivariate polynomial system. So the security of a protocol rely on the complexity of solving a multivariate polynomial system. In this paper there is an overview on a general algorithm used to solve a multivariate system and the quantity to which the complexity of this algorithm depends on: the solving degree. Unfortunately, it is hard to compute. For this reason, it is introduced an invariant: the degree of regularity. This invariant, under certain condition, give us an upper bound on the solving degree. Then we speak about random polynomial systems and in particular what "random" means to us. Finally, we give an upper bound on both the degree of regularity and the solving degree of such random systems.

Related papers

• Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformers [7.953947994427209]
  We consider a long-standing open problem in mathematics: discovering a Lyapunov function that ensures the global stability of a system. This problem has no known general solution, only exist for some small algorithmic systems. We propose a new method for generating synthetic training samples from solutions, and show that sequence-to-sequence transformers perform better than solvers and humans on systems.
  arXiv  Detail & Related papers  (2024-10-10T18:50:10Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Solving Degree Bounds For Iterated Polynomial Systems [0.0]
  We prove regularity estimations for attacks on MiMC, Feistel-MiMC, Feistel-MiMC-Hash, Hades and GMiMC. Our bounds fall in line with the hypothesized complexity of Gr"obner basis attacks on these designs.
  arXiv  Detail & Related papers  (2023-10-05T16:10:14Z)
• An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
  We establish an abstraction of on-the-fly determinization of finite-state automata and demonstrate how it can be applied to bound the automatons. A special case of our findings is that automata with many non-deterministic transitions almost always admit a determinization of complexity.
  arXiv  Detail & Related papers  (2023-08-27T11:51:27Z)
• Automatic Solver Generator for Systems of Laurent Polynomial Equations [1.7188280334580197]
  Given a family of triangulation (Laurent) systems with the same monomial structure but varying coefficients, find a solver that computes solutions for any family as fast as possible. We propose an automatic solver generator for systems of Laurent equations.
  arXiv  Detail & Related papers  (2023-07-01T12:12:52Z)
• A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium [0.3749861135832073]
  We present an implementation of this strategy in an algorithm called Multi which is designed for systems having at most one solution. We prove that an optimal complexity of Multi is achieved by using a full multistep strategy with a maximum number of steps and in turn the standard guess-and-determine strategy, which essentially is a strategy consisting of a single step, is the worst choice.
  arXiv  Detail & Related papers  (2023-04-16T16:09:14Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Power of human-algorithm collaboration in solving combinatorial optimization problems [0.0]
  We show that a class of optimization problems can be solved efficiently in expectation up to a multiplicative factor $epsilon$ where $epsilon$ is arbitrary constant. While our proposed methods are merely theoretical, they cast new light on how to approach solving these problems that have been usually considered intractable.
  arXiv  Detail & Related papers  (2021-07-25T11:21:59Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  This work considers a large family of bandit problems where the unknown underlying reward function is non-concave. Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality. We show that the standard optimistic algorithms are sub-optimal by dimension factors.
  arXiv  Detail & Related papers  (2021-07-09T16:04:24Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  We propose to accelerate existing linear bandit algorithms to achieve per-step time complexity sublinear in the number of arms $K$. We show that our proposed algorithms can achieve $O(K1-alpha(T))$ per-step complexity for some $alpha(T) > 0$ and $widetilde O(stT)$ regret, where $T$ is the time horizon.
  arXiv  Detail & Related papers  (2021-03-03T22:42:15Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURF is an algorithm for approximating distributions by piecewises. It outperforms state-of-the-art algorithms in experiments.
  arXiv  Detail & Related papers  (2020-02-22T01:03:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.