We present some new and recent algorithmic results concerning polynomial system solving over various rings. In particular, we present some of the best recent bounds on: (a) the complexity of calculating the complex dimension of an algebraic set, (b) the height of the zero-dimensional part of an algebraic set over C, and (c) the number of connected components of a semi-algebraic set. We also present some results which significantly lower the complexity of deciding the emptiness of hypersurface intersections over C and Q, given the truth of the Generalized Riemann Hypothesis. Furthermore, we state some recent progress on the decidability of the prefixes and , quantified over the positive integers. As an application, we conclude with a result connecting Hilbert's Tenth Problem in three variables and height bounds for integral points on algebraic curves. This paper is based on three lectures presented at the conference corresponding to this proceedings volume. The titles of the lectures were Some Speed-Ups in Computational Algebraic Geometry,'' Diophantine Problems Nearly in the Polynomial Hierarchy,'' and Curves, Surfaces, and the Frontier to Undecidability.''
As for more general relations between @math and its analogue over @math , it is easy to see that the decidability of @math implies the decidability of its analogue over @math . Unfortunately, the converse is currently unknown. Via Lagrange's Theorem (that any positive integer can be written as a sum of four squares) one can easily show that the un decidability of @math implies the un decidability of the analogue of @math over @math . More recently, Zhi-Wei Sun has shown that the @math can be replaced by @math @cite_12 .
@cite_12
1924023668 1561261246 2551334724 2807350215
A function @math is @math -resilient if all its Fourier coefficients of degree at most @math are zero, i.e., @math is uncorrelated with all low-degree parities. We study the notion of @math @math of Boolean functions, where we say that @math is @math -approximately @math -resilient if @math is @math -close to a @math -valued @math -resilient function in @math distance. We show that approximate resilience essentially characterizes the complexity of agnostic learning of a concept class @math over the uniform distribution. Roughly speaking, if all functions in a class @math are far from being @math -resilient then @math can be learned agnostically in time @math and conversely, if @math contains a function close to being @math -resilient then agnostic learning of @math in the statistical query (SQ) framework of Kearns has complexity of at least @math . This characterization is based on the duality between @math approximation by degree- @math polynomials and approximate @math -resilience that we establish. In particular, it implies that @math approximation by low-degree polynomials, known to be sufficient for agnostic learning over product distributions, is in fact necessary. Focusing on monotone Boolean functions, we exhibit the existence of near-optimal @math -approximately @math -resilient monotone functions for all @math . Prior to our work, it was conceivable even that every monotone function is @math -far from any @math -resilient function. Furthermore, we construct simple, explicit monotone functions based on @math and @math that are close to highly resilient functions. Our constructions are based on a fairly general resilience analysis and amplification. These structural results, together with the characterization, imply nearly optimal lower bounds for agnostic learning of monotone juntas. We show that termination of a simple class of linear loops over the integers is decidable. Namely we show that termination of deterministic linear loops is decidable over the integers in the homogeneous case, and over the rationals in the general case. This is done by analyzing the powers of a matrix symbolically using its eigenvalues. Our results generalize the work of Tiwari [Tiw04], where similar results were derived for termination over the reals. We also gain some insights into termination of non-homogeneous integer programs, that are very common in practice. Let @math be a partially ordered set. If the Boolean lattice @math can be partitioned into copies of @math for some positive integer @math , then @math must satisfy the following two trivial conditions: (1) the size of @math is a power of @math , (2) @math has a unique maximal and minimal element. Resolving a conjecture of Lonc, it was shown by Gruslys, Leader and Tomon that these conditions are sufficient as well. In this paper, we show that if @math only satisfies condition (2), we can still almost partition @math into copies of @math . We prove that if @math has a unique maximal and minimal element, then there exists a constant @math such that all but at most @math elements of @math can be covered by disjoint copies of @math . We show that any language in nondeterministic time @math , where the number of iterated exponentials is an arbitrary function @math , can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness @math and soundness @math , where the number of iterated exponentials is @math and @math is a universal constant. The result was previously known for @math and @math ; we obtain it for any time-constructible function @math . The result is based on a compression technique for interactive proof systems with entangled provers that significantly simplifies and strengthens a protocol compression result of Ji (STOC'17). As a separate consequence of this technique we obtain a different proof of Slofstra's recent result (unpublished) on the uncomputability of the entangled value of multiprover games. Finally, we show that even minor improvements to our compression result would yield remarkable consequences in computational complexity theory and the foundations of quantum mechanics: first, it would imply that the class MIP* contains all computable languages; second, it would provide a negative resolution to a multipartite version of Tsirelson's problem on the relation between the commuting operator and tensor product models for quantum correlations.