Does truth-table of linear norm reduce the one-query tautologies to a random oracle?

In our former works, for a given concept of reduction, we study the following hypothesis: “For a random oracle A, with probability one, the degree of the one-query tautologies with respect to A is strictly higher than the degree of A.” In our former works (Suzuki in Kobe J. Math. 15, 91–102, 1998; in Inf. Comput. 176, 66–87, 2002; in Arch. Math. Logic 44, 751–762), the following three results are shown: The hypothesis for p-T (polynomial-time Turing) reduction is equivalent to the assertion that the probabilistic complexity class R is not equal to NP; The hypothesis for p-tt (polynomial-time truth-table) reduction implies that P is not NP; The hypothesis holds for each of the following: disjunctive reduction, conjunctive reduction, and p-btt (polynomial-time bounded-truth-table) reduction. In this paper, we show the following three results: (1) Let c be a positive real number. We consider a concept of truth-table reduction whose norm is at most c times size of input, where for a relativized propositional formula F, the size of F denotes the total number of occurrences of propositional variables, constants and propositional connectives. Then, our main result is that the hypothesis holds for such tt-reduction, provided that c is small enough. How small c can we take so that the above holds? It depends on our syntactic convention on one-query tautologies. In our setting, the statement holds for all c < 1. (2) The hypothesis holds for monotone truth-table reduction (also called positive reduction). (3) Dowd (in Inf. Comput. 96, 65–76, 1992) shows a polynomial upper bound for the minimum sizes of forcing conditions associated with a random oracle. We apply the above result (1), and get a linear lower bound for the sizes.     

Stochastic modeling of the growth process

In this paper we estimate the upper boundary of the number of trees in the selection stand determined for harvesting in a future. At the same time we showed that the present resource of the number of trees in selection stand is sustained. This is achieved by stochastic modeling of the number of trees and the number of felled trees and by solving the partial differential equation. The same problem is solved in the papers, Mitrović (Stochastic modeling of the number of trees and the number of felled trees in selection stands, YUJOR, vol 14(1), pp 57–64, 2004; Stochastic modeling of the number of felled trees in selection stands, Computational and Applied Mathematics, vol 24(2), pp 285–292, 2005). In this paper the modified mathematical model is represented.      

Directed t-Packings and Directed t-Steiner Systems

The aim of this paper is an investigation of directed t-packings and in particular of directed t-Steiner systems. A new upper bound on the number of points k for directed t-Steiner systems T(t,k,k) is obtained. We disprove a conjecture of Levenshtein on T(t,k,k) for t 3 by showing that a T(4,6,6) exists. Furthermore, it is proved that the symmetric group S ₆ can be partitioned into 30 disjoint T(4,6,6)s. Extensive computer search shows that the tight upper bound on K for t =4,5 is 6 and for t=6 is 7. The non-existence of further small directed t-Steiner systems is established, and large directed t-packings for t,4,5,6 are constructed.     

Minimum Weight and Dimension Formulas for Some Geometric Codes

The geometric codes are the duals of the codes defined by the designs associated with finite geometries. The latter are generalized Reed–Muller codes, but the geometric codes are, in general, not. We obtain values for the minimum weight of these codes in the binary case, using geometric constructions in the associated geometries, and the BCH bound from coding theory. Using Hamada's formula, we also show that the dimension of the dual of the code of a projective geometry design is a polynomial function in the dimension of the geometry.     

A Class of Perfect Ternary Constant-Weight Codes

We construct a class of perfect ternary constant-weight codes of length 2 ^r , weight 2 ^r -1 and minimum distance 3. The codes have codewords. The construction is based on combining cosets of binary Hamming codes. As a special case, for r=2 the construction gives the subcode of the tetracode consisting of its nonzero codewords. By shortening the perfect codes, we get further optimal codes.     

Limit law for transition probabilities and moderate deviations for Sinai's random walk in random environment

We consider a one-dimensional random walk in random environment in the Sinai's regime. Our main result is that logarithms of the transition probabilities, after a suitable rescaling, converge in distribution as time tends to infinity, to some functional of the Brownian motion. We compute the law of this functional when the initial and final points agree. Also, among other things, we estimate the probability of being at time t at distance at least z from the initial position, when z is larger than ln²t, but still of logarithmic order in time.Partially supported by CNRS (UMR 7599 ``Probabilités et Modéles Aléatoires'), and by the ``Réseau Mathématique France-Brésil'Partially supported by CNPq (300676/00–0 and 302981/02–0), COFECUB, and by the ``Rede Matemática Brasil-França'     

Large deviations for Brownian motion in a random scenery

We prove large deviations principles in large time, for the Brownian occupation time in random scenery . The random field is constant on the elements of a partition of ^d into unit cubes. These random constants, say consist of i.i.d. bounded variables, independent of the Brownian motion {B_s,s0}. This model is a time-continuous version of Kesten and Spitzer's random walk in random scenery. We prove large deviations principles in ``quenched' and ``annealed' settings.Mathematics Subject Classification (2000):60F10, 60J55, 60K37     

Designs in Additive Codes over GF(4)

In this paper we discuss the security of digital signature schemes based on error-correcting codes. Several attacks to the Xinmei scheme are surveyed, and some reasons given to explain why the Xinmei scheme failed, such as the linearity of the signature and the redundancy of public keys. Another weakness is found in the Alabbadi-Wicker scheme, which results in a universal forgery attack against it. This attack shows that the Alabbadi-Wicker scheme fails to implement the necessary property of a digital signature scheme: it is infeasible to find a false signature algorithm D from the public verification algorithm E such that E(D ( )) = for all messages . Further analysis shows that this new weakness also applies to the Xinmei scheme.     

Logarithmic Sobolev Inequalities,Matrix Models and Free Entropy

We give two applications of logarithmic Sobolev inequalities to matrix models and free probability. We also provide a new characterization of semi-circular systems through a Poincare-type inequality.     

Itoh-Tsujii Inversion in Standard Basis and Its Application in Cryptography and Codes

This contribution is concerned with a generalization of Itoh and Tsujii's algorithm for inversion in extension fields . Unlike the original algorithm, the method introduced here uses a standard (or polynomial) basis representation. The inversion method is generalized for standard basis representation and relevant complexity expressions are established, consisting of the number of extension field multiplications and exponentiations. As the main contribution, for three important classes of fields we show that the Frobenius map can be explored to perform the exponentiations required for the inversion algorithm efficiently. As an important consequence, Itoh and Tsujii's inversion method shows almost the same practical complexity for standard basis as for normal basis representation for the field classes considered.