A class of finitary codes

It is shown that for any two Bernoulli schemes with a finite number of states and unequal entropies, there exists a finitary homomorphism from the scheme with larger entropy to the one with smaller entropy.     

Relaxation Lax-Friedrichs sweeping scheme for static Hamilton-Jacobi equations

This paper presents a relaxation Lax-Friedrichs sweeping scheme to approximate viscosity solutions of static Hamilton Jacobi equations in any number of spatial dimensions. It is a generalization of the scheme proposed in Kao et al. (J Comput Phys 196:367–391, 2004). Numerical examples suggest that the relaxation Lax-Friedrichs sweeping scheme has smaller number of iterations than the original Lax-Friedrichs sweeping scheme when the relaxation factor ω is slightly larger than one. And first order convergence is also demonstrated by numerical results. A theoretical analysis for our scheme in a special case is given.     

An entropy satisfying MUSCL scheme for systems of conservation laws

Summary. For the high-order numerical approximation of hyperbolic systems of conservation laws, we propose to use as a building principle an entropy diminishing criterion instead of the familiar total variation diminishing criterion introduced by Harten for scalar equations. Based on this new criterion, we derive entropy diminishing projections that ensure, both, the second order of accuracy and all of the classical discrete entropy inequalities. The resulting scheme is a nonlinear version of the classical Van Leer's MUSCL scheme. Strong convergence of this second order, entropy satisfying scheme is proved for systems of two equations. Numerical tests demonstrate the interest of our theory. Received March 28, 1995 / Revised version received June 17, 1995     

一维单个守恒型方程的二阶熵耗散格式

本文考虑一维单个守恒律方程，对其设计了一种非线性守恒型差分格式，此格式为二阶Godunov型的，用的是分片线性重构，重构函数的斜率是根据熵耗散得到的，格式满足熵条件，且数值实验表明格式具有非线性稳定性，在此格式中一个所谓的熵耗散函数起了很重要的作用，它在每个网格的计算中耗散熵，在文中我们给出了熵耗散函数应满足的条件，并给出了一种具体的构造形式，最后给出了一些数值算例，从中可看出熵耗散函数是如何抑制非物理振荡的，及格式对计算的有效性。     

New results on measures of maximal entropy

It has recently been demonstrated that there are strongly irreducible subshifts of finite type with more than one measure of maximal entropy. Here we obtain a number of results concerning the uniqueness of the measure of maximal entropy. In addition, we construct for anyd≥2 andk a strongly irreducible subshift of finite type ind dimensions with exactlyk ergodic (extremal) measures of maximal entropy. Ford≥3, we construct a strongly irreducible subshift of finite type ind dimensions with a continuum of ergodic measures of maximal entropy. Research supported in part by AFOSR grant # 91-0215 and NSF grant # DMS-9103738. Research supported by the Swedish National Science Foundation.     

Monotone difference schemes stabilized by discrete mollification for strongly degenerate parabolic equations

The discrete mollification method is a convolution‐based filtering procedure suitable for the regularization of ill‐posed problems and for the stabilization of explicit schemes for the solution of PDEs. This method is applied to the discretization of the diffusive terms of a known first‐order monotone finite difference scheme [Evje and Karlsen, SIAM J Numer Anal 37 (2000) 1838–1860] for initial value problems of strongly degenerate parabolic equations in one space dimension. It is proved that the mollified scheme is monotone and converges to the unique entropy solution of the initial value problem, under a CFL stability condition which permits to use time steps that are larger than with the unmollified (basic) scheme. Several numerical experiments illustrate the performance and gains in CPU time for the mollified scheme. Applications to initial‐boundary value problems are included. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 38–62, 2012     

Numerical viscosity and the entropy condition

Weak solutions of hyperbolic conservation laws are not uniquely determined by their initial values; an entropy condition is needed to pick out the physically relevant solutions. The question arises whether finite difference approximations converge to this particular solution. It is known that this is not always the case with the standard Lax-Wendroff (L-W) difference scheme. In this paper a simple variant of the L-W scheme is devised which retains its desirable computational features—conservation form, three point scheme, second-order accuracy on smooth solutions, but which has the additional property that limit solutions satisfy the entropy condition. This variant is constructed by adding a simple nonlinear artificial viscosity to the usual L-W operator. The nature of the viscosity is deduced by first analyzing a model differential equation derived from the truncation error for the L-W operator, keeping only terms of order (Δx)². Furthermore, this viscosity is “switched on” only when sufficiently steep discrete gradients develop in the approximate solution: The full L-W scheme is then shown to have the desired property provided that the Courant-Friedrichs-Lewy restriction |λf′(u)|≤0.14 is satisfied.     

Convergence of a large time step generalization of Godunov's method for conservation laws

A natural generalization of Godunov's method for Courant numbers larger than 1 is obtained by handling interactions between neighboring Riemann problems linearly, i.e., by allowing waves to pass through one another with no change in strength or speed. This method is well defined for arbitrarily large Courant numbers and can be written in conservation form. It follows that if a sequence of approximations converges to a limit u(x,t) as the mesh is refined, then u is a weak solution to the system of conservation laws. For scalar problems the method is total variation diminishing and every sequence contains a convergent subsequence. It is conjectured that in fact every sequence converges to the (unique) entropy solution provided the correct entropy solution is used for each Riemann problem. If the true Riemann solutions are replaced by approximate Riemann solutions which are consistent with the conservation law, then the above convergence results for general systems continue to hold.     

Analyzing linear mergers

Mergers are functions that transform k (possibly dependent) random sources (distributions) into a single random source, in a way that ensures that if one of the input sources has min‐entropy rate δ then the output has min‐entropy rate close to δ. Mergers have proven to be a very useful tool in explicit constructions of extractors and condensers, and are also interesting objects in their own right. In this work we give a refined analysis of the merger constructed by [Raz, STOC'05] (based on [Lu, Reingold, Vadhan, and Wigderson, STOC'03 pp. 602–611, 2003]). Our analysis uses min‐entropy instead of Shannon's entropy to derive tighter results than the ones obtained in [Raz STOC'05]. We show that for every constant r and k it is possible to construct a merger that takes as input k strings of length n bits each, and outputs a string of length n/r bits, such that if one of the input sources has min‐entropy b, the output will be close to having min‐entropy b/(r + 1). This merger uses a constant number of additional uniform bits. One advantage of our analysis is that b (the min‐entropy of the “good” source) can be as small as a constant (this constant depends on r and k), while in the analysis given in [Raz STOC'05], b is required to be linear in n. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

An impossibility result on graph secret sharing

A perfect secret sharing scheme based on a graph G is a randomized distribution of a secret among the vertices of the graph so that the secret can be recovered from the information assigned to vertices at the endpoints of any edge, while the total information assigned to an independent set of vertices is independent (in statistical sense) of the secret itself. The efficiency of a scheme is measured by the amount of information the most heavily loaded vertex receives divided by the amount of information in the secret itself. The (worst case) information ratio of G is the infimum of this number. We calculate the best lower bound on the information ratio for an infinite family of graphs the entropy method can give. We argue that almost all existing constructions for secret sharing schemes are special cases of the generalized vector space construction. We give direct constructions of this type for the first two members of the family, and show that for the other members no such construction exists which would match the bound yielded by the entropy method.     

Smooth interval maps have symbolic extensions

We prove that if X denotes the interval or the circle then every transformation T:X→X of class C ^r , where r>1 is not necessarily an integer, admits a symbolic extension, i.e., every such transformation is a topological factor of a subshift over a finite alphabet. This is done using the theory of entropy structure. For such transformations we control the entropy structure by providing an upper bound, in terms of Lyapunov exponents, of local entropy in the sense of Newhouse of an ergodic measure ν near an invariant measure μ (the antarctic theorem). This bound allows us to estimate the so-called symbolic extension entropy function on invariant measures (the main theorem), and as a consequence, to estimate the topological symbolic extension entropy; i.e., a number such that there exists a symbolic extension with topological entropy arbitrarily close to that number. This last estimate coincides, in dimension 1, with a conjecture stated by Downarowicz and Newhouse [13, Conjecture 1.2]. The passage from the antarctic theorem to the main theorem is applicable to any topological dynamical system, not only to smooth interval or circle maps.     

Convergence of a finite volume scheme for nonlinear degenerate parabolic equations

Summary. One approximates the entropy weak solution u of a nonlinear parabolic degenerate equation by a piecewise constant function using a discretization in space and time and a finite volume scheme. The convergence of to u is shown as the size of the space and time steps tend to zero. In a first step, estimates on are used to prove the convergence, up to a subsequence, of to a measure valued entropy solution (called here an entropy process solution). A result of uniqueness of the entropy process solution is proved, yielding the strong convergence of to{\it u}. Some on a model equation are shown. Received September 27, 2000 / Published online October 17, 2001     

McEliece Public Key Cryptosystems Using Algebraic-Geometric Codes

McEliece proposed a public-key cryptosystem based on algebraic codes, in particular binary classical Goppa codes. Actually, his scheme needs only a class of codes with a good decoding algorithm and with a huge number of inequivalent members with given parameters. In the present paper we look at various aspects of McEliece's scheme using the new and much larger class of R-ary algebraic-geometric Goppa codes.     

Monotonicity and error bounds in schemes of Romberg type for the computation off(n) (0) by central differences and extrapolation

Summary An integral form of the remainder terms of the entries in the extrapolation scheme is shown to have kernels of constant sign within columns. Monotonicity of one or more derivatives of the function to be differentiated is transformed into certain monotonicity properties of the scheme. For functions of this kind the extrapolation scheme also provides for strict inclusions off(ⁿ) (0). This property may be extended to a larger class of functions through a majorant concept.     

Deterministic particle approximation for nonlocal transport equations with nonlinear mobility

We construct a deterministic, Lagrangian many-particle approximation to a class of nonlocal transport PDEs with nonlinear mobility arising in many contexts in biology and social sciences. The approximating particle system is a nonlocal version of the follow-the-leader scheme. We rigorously prove that a suitable discrete piece-wise density reconstructed from the particle scheme converges strongly in $L_{loc}^1$ towards the unique entropy solution to the target PDE as the number of particles tends to infinity. The proof is based on uniform BV estimates on the approximating sequence and on the verification of an approximated version of the entropy condition for large number of particles. As part of the proof, we also prove uniqueness of entropy solutions. We further provide a specific example of non-uniqueness of weak solutions and discuss the interplay of the entropy condition with the steady states. Finally, we produce numerical simulations supporting the need of a concept of entropy solution in order to get a well-posed semigroup in the continuum limit, and showing the behaviour of solutions for large times.     

Entropy dissipative one‐leg multistep time approximations of nonlinear diffusive equations

New one‐leg multistep time discretizations of nonlinear evolution equations are investigated. The main features of the scheme are the preservation of the non‐negativity and the entropy dissipation structure of the diffusive equations. The key ideas are to combine Dahlquist's G‐stability theory with entropy dissipation methods and to introduce a nonlinear transformation of variables, which provides a quadratic structure in the equations. It is shown that G‐stability of the one‐leg scheme is sufficient to derive discrete entropy dissipation estimates. The general result is applied to a cross‐diffusion system from population dynamics and a nonlinear fourth‐order quantum diffusion model, for which the existence of semidiscrete weak solutions is proved. Under some assumptions on the operator of the evolution equation, the second‐order convergence of solutions is shown. Moreover, some numerical experiments for the population model are presented, which underline the theoretical results. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1119–1149, 2015     

On an aggregation model with long and short range interactions

In recent papers the authors had proposed a stochastic model for swarm aggregation, based on individuals subject to long range attraction and short range repulsion, in addition to a classical Brownian random dispersal. Under suitable laws of large numbers they showed that, for a large number of individuals, the evolution of the empirical distribution of the population can be expressed in terms of an approximating nonlinear degenerate and nonlocal parabolic equation, which describes the limit.In this paper the well-posedness of such evolution equation is investigated, which invokes a notion of entropy solutions extended to the nonlocal case. We motivate entropy solutions from the discrete particle system and use them to prove uniqueness. Moreover, we provide existence results and discuss some basic properties of solutions. Finally, we apply a Lagrangian numerical scheme to perform numerical simulations in spatial dimension one.     

Mathematical and numerical study of a system of conservation laws

The system of equations (f (u))_t − (a(u)v + b(u))_x = 0 and u_t − (c(u)v + d(u))_x = 0, where the unknowns u and v are functions depending on , arises within the study of some physical model of the flow of miscible fluids in a porous medium. We give a definition for a weak entropy solution (u, v), inspired by the Liu condition for admissible shocks and by Krushkov entropy pairs. We then prove, in the case of a natural generalization of the Riemann problem, the existence of a weak entropy solution only depending on x/t. This property results from the proof of the existence, by passing to the limit on some approximations, of a function g such that u is the classical entropy solution of u_t − ((cg + d)(u))_x = 0 and simultaneously w = f (u) is the entropy solution of w_t − ((ag + b)(f⁽⁻¹⁾(w)))_x = 0. We then take v = g(u), and the proof that (u, v) is a weak entropy solution of the coupled problem follows from a linear combination of the weak entropy inequalities satisfied by u and f (u). We then show the existence of an entropy weak solution for a general class of data, thanks to the convergence proof of a coupled finite volume scheme. The principle of this scheme is to compute the Godunov numerical flux with some interface functions ensuring the symmetry of the finite volume scheme with respect to both conservation equations.     

Conservation law with the flux function discontinuous in the space variable—II: Convex–concave type fluxes and generalized entropy solutions

We deal with a single conservation law with discontinuous convex–concave type fluxes which arise while considering sign changing flux coefficients. The main difficulty is that a weak solution may not exist as the Rankine–Hugoniot condition at the interface may not be satisfied for certain choice of the initial data. We develop the concept of generalized entropy solutions for such equations by replacing the Rankine–Hugoniot condition by a generalized Rankine–Hugoniot condition. The uniqueness of solutions is shown by proving that the generalized entropy solutions form a contractive semi-group in L¹$L^1$. Existence follows by showing that a Godunov type finite difference scheme converges to the generalized entropy solution. The scheme is based on solutions of the associated Riemann problem and is neither consistent nor conservative. The analysis developed here enables to treat the cases of fluxes having at most one extrema in the domain of definition completely. Numerical results reporting the performance of the scheme are presented.     

A Public-Key Traitor Tracing Scheme with Revocation Using Dynamic Shares

We proposed a new public-key traitor tracing scheme with revocation capability using dynamic shares and entity revocation techniques. Our schemes traitor tracing and revocation programs cohere tightly. The size of the enabling block of our scheme is independent of the number of receivers. Each receiver holds one decryption key only. The distinct feature of our scheme is that when traitors are found, we can revoke their private keys (up to some threshold z) without updating the private keys of other receivers. In particular, no revocation messages are broadcast and all receivers do nothing. Previously proposed revocation schemes need update existing keys and entail large amount of broadcast messages. Our traitor tracing algorithm works in a black-box way. It is conceptually simple and fully k-resilient, that is, it can find all traitors if the number of them is k or less. The encryption algorithm of our scheme is semantically secure assuming that the decisional Diffie-Hellman problem is hard.AMS Classification: 11T71, 68P30