Search

Computing with non-linear polynomial constraints over the real numbers has been an important area within Computer Algebra since the field's inception. More recently, satisfiability for this theory has become an important problem in the SMT-solving community. Inspired by the S C 2 project, this paper combines ideas from both communities to produce a fast "partial solver" for the theory — i.e. a solver that can sometimes decide the satisfiability of formulas, but sometimes fails to make a determination. The partial solver is based on existing "black-box/white-box" simplification algorithms, which this paper extends to allow for the production of UNSAT cores (and stronger simplifications). The production of UNSAT cores is required if the partial solver is to be used in SMT-solving, which is one of the primary motivations for this work. The authors have implemented the partial solver in the Image 1 system, and this paper also reports on experiments based on that implementation. [ABSTRACT FROM AUTHOR]

The slice-rank method, introduced by Tao as a symmetrized version of the polynomial method of Croot, Lev and Pach and Ellenberg and Gijswijt, has proved to be a useful tool in a variety of combinatorial problems. Explicit tensors have been introduced in different contexts but little is known about the limitations of the method. In this paper, building upon a method presented by Tao and Sawin, it is proved that the asymptotic slice rank of any k -tensor in any field is either 1 or at least k / (k − 1) (k − 1) / k. This provides evidence that straight-forward application of the method cannot give useful results in certain problems for which non-trivial exponential bounds are already known. An example, actually a motivation for starting this work, is the problem of bounding the size of sets of trifferent sequences, which constitutes a long-standing open problem in information theory and in theoretical computer science. [ABSTRACT FROM AUTHOR]