Optimising Gröbner Bases on Bivium

Bivium is a reduced version of the stream cipher Trivium. In this paper we investigate how fast a key recovery attack on Bivium using Gröbner bases is. First we explain the attack scenario and the cryptographic background. Then we identify the factors that have impact on the computation time and show how to optimise them. As a side effect these experiments benchmark several Gröbner basis implementations. The optimised version of the Gröbner attack has an expected running time of 2^39.12 s, beating the attack time of our previous SAT solver attack by a factor of more than 330. Furthermore this approach is faster than an attack based on BDDs, an exhaustive key search, a generic time-memory trade-off attack and a guess-and-determine strategy.     

Estimating the Volumes of the Cones in a Gröbner Fan

We present a stochastic method for estimating the relative volumes of the Gröbner cones of a Gröbner fan without computing the actual fan. The method is particularly useful when the dimension of the Gröbner fan is large and/or the volumes of several or all cones need to be estimated. A Macaulay 2 implementation for uniform sampling from the Gröbner fan is provided by the author.     

On the Lovász theta function and some variants

The Lovász theta function of a graph is a well-known upper bound on the stability number. It can be computed efficiently by solving a semidefinite program (SDP). Actually, one can solve either of two SDPs, one due to Lovász and the other to Grötschel et al. The former SDP is often thought to be preferable computationally, since it has fewer variables and constraints. We derive some new results on these two equivalent SDPs. The surprising result is that, if we weaken the SDPs by aggregating constraints, or strengthen them by adding cutting planes, the equivalence breaks down. In particular, the Grötschel et al. scheme typically yields a stronger bound than the Lovász one.     

Ideals of Graph Homomorphisms

In combinatorial commutative algebra and algebraic statistics many toric ideals are constructed from graphs. Keeping the categorical structure of graphs in mind we give previous results a more functorial context and generalize them by introducing the ideals of graph homomorphisms. For this new class of ideals we investigate how the topology of the graphs influences the algebraic properties. We describe explicit Gröbner bases for several classes, generalizing results by Hibi, Sturmfels, and Sullivant. One of our main tools is the toric fiber product, and we employ results by Engström, Kahle, and Sullivant. The lattice polytopes defined by our ideals include important classes in optimization theory, as the stable set polytopes.     

On the robust hardness of Gröbner basis computation

The computation of Gröbner bases is an established hard problem. By contrast with many other problems, however, there has been little investigation of whether this hardness is robust. In this paper, we frame and present results on the problem of approximate computation of Gröbner bases. We show that it is NP-hard to construct a Gröbner basis of the ideal generated by a set of polynomials, even when the algorithm is allowed to discard a $1??$ fraction of the generators, and likewise when the algorithm is allowed to discard variables (and the generators containing them). Our results show that computation of Gröbner bases is robustly hard even for simple polynomial systems (e.g. maximum degree 2, with at most 3 variables per generator). We conclude by greatly strengthening results for the Strong c-Partial Gröbner problem posed by De Loera et al. [10]. Our proofs also establish interesting connections between the robust hardness of Gröbner bases and that of SAT variants and graph-coloring.     

Rees algebras and gröbner bases

This paper deals with the following problem. Robbiano showed in [9] that standard bases, Gröbner bases, Macaulay bases are all instances of the same general situation. In this paper, we develop this philosophy from the point of view of the Rees algebra R of a ring A w.r.t. a filtration F given on A. The ring R plays a fine job between A and the graded ring G associated to A, F. The use of R and the properties of termorderings and their relate Gröbner bases led naturally to the definition of Gröbnerfiltrations ingeneral commutative rings.     

Gröbner bases of characteristic ideals of LRS over UFD

LetR be a unique factorization domain (UFD). A method of Gröbner bases and localization in commutative algebra is applied to compute and analyze the characteristic ideals of semi-infinite linear recurring sequences (lrs), infinite linear recurring sequences (LRS), and finite lrs over UFD. The canonical form of a minimal Gröbner basis of the homogeneous characteristic ideal is described for a finite segment of an lrs, from which a precise relation between every step in the classical Berlekamp-Massey algorithm and every member of the Gröbner basis is derived.     

Free Rota-Baxter systems and a Hopf algebra structure

In this paper, we give a linear basis of a free Rota-Baxter system on a set by using the Gröbner-Shirshov bases method and then we obtain a Hopf algebra structure on a free Rota-Baxter system.     

Parallel algorithms for Gröbner-basis construction

The problem of the Gröbner-basis construction is important both from the theoretical and applied points of view. As examples of applications of Gröbner bases, one can mention the consistency problem for systems of nonlinear algebraic equations and the determination of the number of solutions to a system of nonlinear algebraic equations. The Gröbner bases are actively used in the constructive theory of polynomial ideals and at the preliminary stage of numerical solution of systems of nonlinear algebraic equations. Unfortunately, many real examples cannot be processed due to the high computational complexity of known algorithms for computing the Gröbner bases. However, the efficiency of the standard basis construction can be significantly increased in practice. In this paper, we analyze the known algorithms for constructing the standard bases and consider some methods for increasing their efficiency. We describe a technique for estimating the efficiency of paralleling the algorithms and present some estimates.     

Finite lattices and Gröbner bases

Gröbner bases of binomial ideals arising from finite lattices will be studied. In terms of Gröbner bases and initial ideals, a characterization of finite distributive lattices as well as planar distributive lattices will be given.     

Some characterizations of minimal Markov basis for sampling from discrete conditional distributions

In this paper we given some basic characterizations of minimal Markov basis for a connected Markov chain, which is used for performing exact tests in discrete exponential families given a sufficient statistic. We also give a necessary and sufficient condition for uniqueness of minimal Markov basis. A general algebraic algorithm for constructing a connected Markov chain was given by Diaconis and Sturmfels (1998,The Annals of Statistics,26, 363–397). Their algorithm is based on computing Gröbner basis for a certain ideal in a polynomial ring, which can be carried out by using available computer algebra packages. However structure and interpretation of Gröbner basis produced by the packages are sometimes not clear, due to the lack of symmetry and minimality in Gröbner basis computation. Our approach clarifies partially ordered structure of minimal Markov basis.     

Variation of cost functions in integer programming

We study the problem of minimizingc · x subject toA · x =b. x ≥ 0 andx integral, for a fixed matrixA. Two cost functionsc andc′ are considered equivalent if they give the same optimal solutions for eachb. We construct a polytopeSt(A) whose normal cones are the equivalence classes. Explicit inequality presentations of these cones are given by the reduced Gröbner bases associated withA. The union of the reduced Gröbner bases asc varies (called the universal Gröbner basis) consists precisely of the edge directions ofSt(A). We present geometric algorithms for computingSt(A), the Graver basis, and the universal Gröbner basis.     

Markov and Artin Normal Form Theorem for Braid Groups∗

In this article, we will present the results of Artin–Markov on braid groups by using the Gröbner–Shirshov basis. As a consequence, we can reobtain the normal form of Artin–Markov–Ivanovsky as an easy corollary.     

Some degenerations of Kazhdan–Lusztig ideals and multiplicities of Schubert varieties

We study Hilbert–Samuel multiplicity for points of Schubert varieties in the complete flag variety, by Gröbner degenerations of the Kazhdan–Lusztig ideal. In the covexillary case, we give a manifestly positive combinatorial rule for multiplicity by establishing (with a Gröbner basis) a reduced limit whose Stanley–Reisner simplicial complex is homeomorphic to a shellable ball or sphere. We show that multiplicity counts the number of facets of this complex. We also obtain a formula for the Hilbert series of the local ring. In particular, our work gives a multiplicity rule for Grassmannian Schubert varieties, providing alternative statements and proofs to formulae of Lakshmibai and Weyman (1990) [26], Rosenthal and Zelevinsky (2001) [37], Krattenthaler (2001) [22], Kodiyalam and Raghavan (2003) [21], Kreiman and Lakshmibai (2004) [24], Ikeda and Naruse (2009) [13] and Woo and Yong (2009) [40]. We suggest extensions of our methodology to the general case.     

Gröbner Bases for Ideals of σ-PBW Extensions

In this article, we introduce the σ-PWB extensions and construct the theory of Gröbner bases for the left ideals of them. We prove the Hilbert's basis theorem and the division algorithm for this more general class of Poincaré–Birkhoff–Witt extensions. For the particular case of bijective and quasi-commutative σ-PWB extensions, we implement the Buchberger's algorithm for computing Gröbner bases of left ideals.     

Toric rings generated by special stable sets of monomials

In this paper we consider some subalgebras of the d-th Veronese subring of a polynomial ring, generated by stable subsets of monomials. We prove that these algebras are Koszul, showing that the presentation ideals have Gröbner bases of quadrics with respect to suitable term orders. Since the initial monomials of the elements of these Gröbner bases are square- free, it follows by a result of STURMFELS [S, 13.15], that the algebras under consideration are normal, and thus Cohen-Macaulay.     

Skew-commutator relations and Gröbner-Shirshov basis of quantum group of type F 4

We give a Grobner-Shirshov basis of quantum group of type F4 by using the Ringel-Hall algebra approach. We compute all skew-commutator relations between the isoclasses of indecomposable representations of Ringel- Hall algebras of type F4 by using an ＇inductive＇ method. Precisely, we do not use the traditional way of computing the skew-commutative relations, that is first compute all Hall polynomials then compute the corresponding skew- commutator relations; instead, we compute the ＇easier＇ skew-commutator relations which correspond to those exact sequences with middle term indecomposable or the split exact sequences first, then ＇deduce＇ others from these ＇easier＇ ones and this in turn gives Hall polynomials as a byproduct. Then using the composition-diamond lemma prove that the set of these relations constitute a minimal CrSbner-Shirshov basis of the positive part of the quantum group of type F4. Dually, we get a Grobner-Shirshov basis of the negative part of the quantum group of type F4. And finally, we give a Gr6bner-Shirshov basis for the whole quantum group of type F4.