On measure-preserving functions over ?3

This paper is devoted to (discrete) p-adic dynamical systems, an important domain of algebraic and arithmetic dynamics [31]?C[41], [5]?C[8]. In this note we study properties of measurepreserving dynamical systems in the case p = 3. This case differs crucially from the case p = 2. The latter was studied in the very detail in [43]. We state results on all compatible functions which preserve measure on the space of 3-adic integers, using previous work of A. Khrennikov and author of present paper, see [24]. To illustrate one of the obtained theorems we describe conditions for the 3-adic generalized polynomial to be measure-preserving on ?₃. The generalized polynomials with integral coefficients were studied in [17, 33] and represent an important class of T-functions. In turn, it is well known that T-functions are well-used to create secure and efficient stream ciphers, pseudorandom number generators.     

An uncertainty principle for function fields

In a recent paper, Granville and Soundararajan (2007) [5] proved an “uncertainty principle” for arithmetic sequences, which limits the extent to which such sequences can be well-distributed in both short intervals and arithmetic progressions. In the present paper we follow the methods of Granville and Soundararajan (2007) [5] and prove that a similar phenomenon holds in Fq[t].     

The method of Iterated Defect-Correction and its application to two-point boundary value problems

Summary In Part II of this paper we present a rigorous analysis of the Iterated Defect-Correction — applied to two-point boundary value problems — which was introduced in Part I of this paper [1]. A complete proof of Theorem 5. 1 of [1] is given.     

Computing a matrix symmetrizer exactly using modified multiple modulus residue arithmetic

A symmetric solution X satisfying the matrix equation XA = A^tX is called a symmetrizer of the matrix A. A general algorithm to compute a matrix symmetrizer is obtained. A new multiple-modulus residue arithmetic called floating-point modular arithmetic is described and implemented on the algorithm to compute an error-free matrix symmetrizer.     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （Part Ⅱ Heuristics for the General Case）

A single machine scheduling problem with controllable processing times and compression costs is considered. The objective is to find an optimal sequence to minimize the cost ofcompletion times and the cost of compression. The complexity of this problem is still unknown.In Part Ⅱ of this paper,the authors have considered a special case where the compression timesand the compression costs are equal among all jobs. Such a problem appears polynomiafiy solvable by developing an O(n^2) algorithm. In this part(Part Ⅱ ),a general case where the controllable processing times and the compression costs are not equal is discussed. Authors proposehere two heuristics with the first based on some previous work and the second based on the algorithm developed in Part Ⅱ . Computational results are presented to show the efficiency and therobustness of these heuristics.     

On the correspondence between arithmetic theories and propositional proof systems – a survey

The purpose of this paper is to survey the correspondence between bounded arithmetic and propositional proof systems. In addition, it also contains some new results which have appeared as an extended abstract in the proceedings of the conference TAMC 2008 [11]. Bounded arithmetic is closely related to propositional proof systems; this relation has found many fruitful applications. The aim of this paper is to explain and develop the general correspondence between propositional proof systems and arithmetic theories, as introduced by Krají?ek and Pudlák [46]. Instead of focusing on the relation between particular proof systems and theories, we favour a general axiomatic approach to this correspondence. In the course of the development we particularly highlight the role played by logical closure properties of propositional proof systems, thereby obtaining a characterization of extensions of EF in terms of a simple combination of these closure properties (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On linear combinatorics I. Concurrency—An algebraic approach

This article is the first one in a series of three. It contains concurrency results for sets of linear mappings of with few compositions and/or small image sets. The fine structure of such sets of mappings will be described in part II [3]. Those structure theorems can be considered as a first attempt to find Freiman-Ruzsa type results for a non-Abelian group. Part III [4] contains some geometric applications.Dedicated to the memory of P. ErdsResearch partially supported by HU-NSF grants OTKA T014302 and T019367.     

An algebraic approach to approximate evaluation of a polynomial on a set of real points

The previous best algorithm for approximate evaluation of a polynomial on a real set was due to Rokhlin and required of the order ofmu+nu ³ infinite precision arithmetic operations to approximate [on a fixed bounded setX(m) ofm+1 real points] a degreen polynomial $p\left( z \right) = \sum\nolimits_{i = 0}^n {p_i x^i } $ within the error bound $2^{ - u} \sum\nolimits_{i = 0}^n {\left| {p_i } \right|} $ . We develop an approximation algorithm which exploits algebraic computational techniques and decreases Rokhlin's record estimate toO(mlog² u+nmin-u, logn}). For logu=o(logn), this result may also be favorably compared with the record boundO(m+n)log² n) on the complexity of the exact multipoint polynomial evaluation. The new algorithm can be performed in the fields (or rings) generated by the input values, which enables us to decrease the precision of the computations [by using modular (residue) arithmetic] and to simplify our computations further in the case whereu=O(logn). Our algorithm allows NC and simultaneously processor efficient parallel implementation. Because of the fundamental nature of the multipoint polynomial evaluation, our results have further applications to numerical and algebraic computational problems. In passing, we also show a substantial improvement in the Chinese remainder algorithm for integers based on incorporating Kaminski's fast residue computation.     

Maximal functions and ergodic averages related to Waring’s problem

We study the arithmetic analogue of maximal functions on diagonal hypersurfaces. This paper is a natural step following the papers of [13], [14] and [16]. We combine more precise knowledge of oscillatory integrals and exponential sums to generalize the asymptotic formula in Waring’s problem to an approximation formula for the Fourier transform of the solution set of lattice points on hypersurfaces arising in Waring’s problem and apply this result to arithmetic maximal functions and ergodic averages. In sufficiently large dimensions, the approximation formula, ? ²-maximal theorems and ergodic theorems were previously known. Our contribution is in reducing the dimensional constraint in the approximation formula using recent bounds of Wooley, and improving the range of ? ^p spaces in the maximal and ergodic theorems. We also conjecture the expected range of spaces.     

A nonsmooth Newton method for variational inequalities,II: Numerical results

This paper presents the results of extensive computational testing of the modified damped Newton algorithm for solving variational inequality problems presented in Part I [8].Corresponding author.     

An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices

The multi-vehicle covering tour problem (m-CTP) involves finding a minimum-length set of vehicle routes passing through a subset of vertices, subject to constraints on the length of each route and the number of vertices that it contains, such that each vertex not included in any route lies within a given distance of a route. This paper tackles a particular case of m-CTP where only the restriction on the number of vertices is considered, i.e., the constraint on the length is relaxed. The problem is solved by a branch-and-cut algorithm and a metaheuristic. To develop the branch-and-cut algorithm, we use a new integer programming formulation based on a two-commodity flow model. The metaheuristic is based on the evolutionary local search (ELS) method proposed in [23]. Computational results are reported for a set of test problems derived from the TSPLIB.     

About the generalized LM-inverse and the weighted Moore-Penrose inverse

The recursive method for computing the generalized LM-inverse of a constant rectangular matrix augmented by a column vector is proposed in Udwadia and Phohomsiri (2007) [16] and [17]. The corresponding algorithm for the sequential determination of the generalized LM-inverse is established in the present paper. We prove that the introduced algorithm for computing the generalized LM-inverse and the algorithm for the computation of the weighted Moore-Penrose inverse developed by Wang and Chen (1986) in [23] are equivalent algorithms. Both of the algorithms are implemented in the present paper using the package MATHEMATICA. Several rational test matrices and randomly generated constant matrices are tested and the CPU time is compared and discussed.     

Calculs de Présentations de Groupes Fuchsiens via les Graphes Rubanés

We show how to compute a geometrical presentation for a finitely generated fuchsian group G from the explicit knowledge of a fundamental polygon for G. We use a previous work on fat-graphs [4]. In particular, our result is a complement to the works of R.S. Kulkarni [10] and S. Johansson [5] on arithmetic fuchsian groups.     

Circumference, chromatic number and online coloring

Erd?s conjectured that if G is a triangle free graph of chromatic number at least k≥3, then it contains an odd cycle of length at least k ^2?o(1) [13,15]. Nothing better than a linear bound ([3], Problem 5.1.55 in [16]) was so far known. We make progress on this conjecture by showing that G contains an odd cycle of length at least Ω(k log logk). Erd?s’ conjecture is known to hold for graphs with girth at least five. We show that if a graph with girth four is C ₅ free, then Erd?s’ conjecture holds. When the number of vertices is not too large we can prove better bounds on χ. We also give bounds on the chromatic number of graphs with at most r cycles of length 1 mod k, or at most s cycles of length 2 mod k, or no cycles of length 3 mod k. Our techniques essentially consist of using a depth first search tree to decompose the graph into ordered paths, which are then fed to an online coloring algorithm. Using this technique we give simple proofs of some old results, and also obtain several other results. We also obtain a lower bound on the number of colors which an online coloring algorithm needs to use to color triangle free graphs.