Search

Martin-Löf defined algorithmic randomness, the use of martingales in this definition and several variants were explored by Schnorr, and Lutz introduced resource-bounded randomness. Ambos-Spies et al. have studied resource-bounded randomness under time-bounds and have shown that resource-bounded randomness implies resource-bounded genericity. While the genericity of Ambos-Spies is based on time-bound on finite-extension strategy, the genericity of Dowd, the main topic of this paper, is based on an analogy of the forcing theorem. For a positive integer r , an oracle D is r -generic in the sense of Dowd ( r -Dowd) if the following holds: If a certain formula F on an exponential-sized portion of D is a tautology then a polynomial-sized subfunction of D forces F to be a tautology. Here, r is the number of occurrences of query symbols in F . The relationship between resource-bounded randomness and Dowd-type genericity has been not clear so far. We show that there exists a primitive recursive function t ( n ) with the following property: Every t ( n ) -random set is r -Dowd for each positive integer r . A proof is done by means of constructing resource-bounded martingales. In our former paper, we left an open problem whether there exists a primitive recursive set which is r -Dowd for every positive integer r . In our recent work, we give an affirmative answer to the problem. The main theorem of the present paper gives an alternative proof of the affirmative answer. [ABSTRACT FROM AUTHOR]

In this paper, we first give a corollary to Snevily’s Theorem on L -intersecting families, which implies a result that cuts by almost half the bound given by Grolmusz and Sudakov (2002), and provide a k -wise extension to the theorem by Babai et al. (2001) on set systems with L -intersections modulo prime powers which implies polynomial bounds for such families. We then extend Alon–Babai–Suzuki type inequalities on set systems to k -wise L -intersecting families and derive a result which improves the existing bound substantially for the non-modular case. We also provide the first known polynomial bounds for codes with restricted Hamming distances for all prime powers moduli p t , in contrast with Grolmusz’s result from Grolmusz (2006) that for non-prime power composite moduli, no polynomial bound exists for such codes. [ABSTRACT FROM AUTHOR]

Over finite fields, if the image of a polynomial map is not the entire field, then its cardinality can be bounded above by a significantly smaller value. Earlier results bound the cardinality of the value set using the degree of the polynomial, but more recent results make use of the powers of all monomials. In this paper, we explore the geometric properties of the Newton polytope and show how they allow for tighter upper bounds on the cardinality of the multivariate value set. We then explore a method which allows for even stronger upper bounds, regardless of whether one uses the multivariate degree or the Newton polytope to bound the value set. Effectively, this provides improvement of a degree matrix-based result given by Zan and Cao, making our new bound the strongest upper bound thus far. [ABSTRACT FROM AUTHOR]

Spherical t -design is a finite subset on sphere such that, for any polynomial of degree at most t , the average value of the integral on sphere can be replaced by the average value at the finite subset. It is well-known that an equivalent condition of spherical design is given in terms of harmonic polynomials. In this paper, we define a spherical design of harmonic index t from the viewpoint of this equivalent condition, and we give its construction and a Fisher type lower bound on the cardinality. Also we investigate whether there is a spherical design of harmonic index attaining the bound. [ABSTRACT FROM AUTHOR]

Abstract: Let be the triangle in bounded by the lines (the standard simplex in ). Denote by the set of all real bivariate algebraic polynomials of total degree at most two. Let be the unit ball of the space endowed with the supremum norm on . We give a full description of the semidefinite extreme points of . The present paper completes the description of the set of all extreme points of started in Milev and Naidenov (2008) [13] and Milev and Naidenov (2011) [14]. We study, as an application, the path-connectedness of . The conclusion is that consists of two path-connected components. [Copyright &y& Elsevier]

Abstract: We discuss parametric polynomial systems, with algorithms for real root classification and triangular decomposition of semi-algebraic systems as our main applications. We exhibit new results in the theory of border polynomials of parametric semi-algebraic systems: in particular a geometric characterization of its “true boundary” (Definition 1). In order to optimize the corresponding decomposition algorithms, we also propose a technique, that we call relaxation, which can simplify the decomposition process and reduce the number of components in the output. This paper extends our earlier works (Chen et al., 2010, 2011). [Copyright &y& Elsevier]