Symmetric Tardos fingerprinting codes for arbitrary alphabet sizes

Fingerprinting provides a means of tracing unauthorized redistribution of digital data by individually marking each authorized copy with a personalized serial number. In order to prevent a group of users from collectively escaping identification, collusion-secure fingerprinting codes have been proposed. In this paper, we introduce a new construction of a collusion-secure fingerprinting code which is similar to a recent construction by Tardos but achieves shorter code lengths and allows for codes over arbitrary alphabets. We present results for ‘symmetric’ coalition strategies. For binary alphabets and a false accusation probability , a code length of symbols is provably sufficient, for large c ₀, to withstand collusion attacks of up to c ₀ colluders. This improves Tardos’ construction by a factor of 10. Furthermore, invoking the Central Limit Theorem in the case of sufficiently large c ₀, we show that even a code length of is adequate. Assuming the restricted digit model, the code length can be further reduced by moving from a binary alphabet to a q-ary alphabet. Numerical results show that a reduction of 35% is achievable for q = 3 and 80% for q = 10.      

Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation

In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the ratio is dependent on the data of the problem with α being a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at least α δd if every weight is strictly positive,where δd ＞ 0 is a constant depending on the problem dimension and data.     

Dissipative Dynamics for a Class of Nonlinear Pseudo-Differential Equations

We study a class of nonlinear evolutionary equations generated by an elliptic pseudo-differential operator, and with nonlinearity of the form G(u _x ) where cη² ≤ G(η) ≤ Cη² for large |η|. For the evolution in spaces of periodic functions with zero mean we demonstrate existence of a universal absorbing set and compact attractor. Furthermore, we show that the attractor is of a finite Hausdorf dimension. The dissipation mechanism for the class of equations studied in the paper is akin to the nonlinear saturation in the Kuramoto-Sivashinsky equation. A similar generalization of the Kuramoto-Sivashinsky equation was studied by Nicolaenko et al. under the assumption of a purely quadratic nonlinearity and reflection invariance of both: the equation and solutions.      

Differential Calculus on Compact Quantum Group Uθ（2） and its Applications

In this paper, via constructing special matrices, we will show that there exists a differential calculus on Uθ（2）, where θ is an irrational number. Then using the above results, we shall discuss the properties of infinitesimal generators of corepresentations of Uθ（2）. And in the final, we shall discuss its irreducible corepresentations and give the Peter-Weyl theorem explicitly for compact quantum group Uθ（2）.     

Constructing Restricted Patterson Measures for Geometrically Infinite Kleinian Groups

In this paper, we study exhaustions, referred to as p-restrictions, of arbitrary nonelementary Kleinian groups with at most finitely many bounded parabolic elements. Special emphasis is put on the geometrically infinite case, where we obtain that the limit set of each of these Kleinian groups contains an infinite family of closed subsets, referred to as p-restricted limit sets, such that there is a Poincaré series and hence an exponent of convergence δp, canonically associated with every element in this family. Generalizing concepts which are well known in the geometrically finite case, we then introduce the notion of p-restricted Patterson measure, and show that these measures are non-atomic, δp-harmonic, δp-subconformal on special sets and δp-conformal on very special sets. Furthermore, we obtain the results that each p-restriction of our Kleinian group is of δp-divergence type and that the Hausdorff dimension of the p-restricted limit set is equal to δp.     

A multi-dimensional Markov chain and the Meixner ensemble

We show that the transition probability of the Markov chain (G(i,1),...,G(i,n)) _i≥1, where the G(i,j)’s are certain directed last-passage times, is given by a determinant of a special form. An analogous formula has recently been obtained by Warren in a Brownian motion model. Furthermore we demonstrate that this formula leads to the Meixner ensemble when we compute the distribution function for G(m,n). We also obtain the Fredholm determinant representation of this distribution, where the kernel has a double contour integral representation.     

Some extremal problems for functions of bounded boundary rotation

A variational method is developed within the class of functions of boundary rotation not exceedingkπ which is based on the fact that the set of representing measuresμ is convex. It shows that an extremal problem related to a functional with Gateaux derivative and some constraints leads to extremal measuresμ ₀ with finite support. The positive and negative part of aμ ₀ is located at points where a functionJ (depending onμ ₀) reaches its maximum and minimum respectively. The method is tested successfully on various problems.     

Explicit Models for Perverse Sheaves,II

In this paper we show that any p-perverse sheaf on an arbitrary stratified topological space (p is a perversity function) is functorially determined by a system of usual sheaves on the open sets U _r (r≥0) and certain gluing data, where U _r is the union of strata of perversity ≤r. Both authors are partially supported by BFM2001-3207 and MTM2004-07203-C02-01 and FEDER.     

A Three Solutions Theorem for Nonlinear Operator Equations in Ordered Banach Spaces

In this paper we consider the operator equation in a real Banach space E with cone P: where A = KF; here K is a e-positive, e-continuous and completely continuous operator, and F is a strictly increasing and continuous operator which is Fréchet differentiable at θ. Under certain conditions, we show that the operator equation has at least three solutions x₁, x₂, x₃ such that x₁ ∈ P, x₂ ∈ (−P), x₃ ∈ E\(P ∪ (−P)). Now since the third solution x₃ ∈ E\(P ∪ (−P)), we call it a sign-changing solution. As an application of the main results, we investigate the existence of sign-changing solutions for some three-point boundary value problem.     

Laplace approximations for sums of independent random vectors

Let X _i , i∈N, be i.i.d. B-valued random variables, where B is a real separable Banach space. Let Φ be a mapping B→R. Under a central limit theorem assumption, an asymptotic evaluation of Z _n = E (exp (n Φ (∑ _{i =1} ⁿ X _i /n))), up to a factor (1 + o(1)), has been gotten in Bolthausen [1]. In this paper, we show that the same asymptotic evaluation can be gotten without the central limit theorem assumption. Received: 19 September 1997 / Revised version:22 April 1999     

Stability estimates for h-p spectral element methods for elliptic problems

In a series of papers of which this is the first we study how to solve elliptic problems on polygonal domains using spectral methods on parallel computers. To overcome the singularities that arise in a neighborhood of the corners we use a geometrical mesh. With this mesh we seek a solution which minimizes a weighted squared norm of the residuals in the partial differential equation and a fractional Sobolev norm of the residuals in the boundary conditions and enforce continuity by adding a term which measures the jump in the function and its derivatives at inter-element boundaries, in an appropriate fractional Sobolev norm, to the functional being minimized. Since the second derivatives of the actual solution are not square integrable in a neighborhood of the corners we have to multiply the residuals in the partial differential equation by an appropriate power of r_k, where r_k measures the distance between the pointP and the vertexA _k in a sectoral neighborhood of each of these vertices. In each of these sectoral neighborhoods we use a local coordinate system (τ_k, θ_k) where τ_k = lnr_k and (r_k, θ_k) are polar coordinates with origin at A_k, as first proposed by Kondratiev. We then derive differentiability estimates with respect to these new variables and a stability estimate for the functional we minimize. In [6] we will show that we can use the stability estimate to obtain parallel preconditioners and error estimates for the solution of the minimization problem which are nearly optimal as the condition number of the preconditioned system is polylogarithmic inN, the number of processors and the number of degrees of freedom in each variable on each element. Moreover if the data is analytic then the error is exponentially small inN.     

Two-letter group codes that preserve aperiodicity of inverse finite automata

We construct group codes over two letters (i.e., bases of subgroups of a two-generated free group) with special properties. Such group codes can be used for reducing algorithmic problems over large alphabets to algorithmic problems over a two-letter alphabet. Our group codes preserve aperiodicity of inverse finite automata. As an application we show that the following problems are PSpace-complete for two-letter alphabets (this was previously known for large enough finite alphabets): The intersection-emptiness problem for inverse finite automata, the aperiodicity problem for inverse finite automata, and the closure-under-radical problem for finitely generated subgroups of a free group. The membership problem for 3-generated inverse monoids is PSpace-complete. Both authors were supported in part by NSF grant DMS-9970471. The first author was also supported in part by NSF grant CCR-0310793. The second author acknowledges the support of the Excellency Center, “Group Theoretic Methods for the Study of Algebraic Varieties” of the Israeli Science Foundation.     

The Bellman function,the two-weight Hilbert transform,and embeddings of the model spaces<Emphasis Type="Italic">K</Emphasis><Subscript>θ</Subscript>

This paper is devoted to embedding theorems for the spaceK _θ , where θ is an inner function in the unit disc D. It turns out that the question of embedding ofK _θ into L²(Μ) is virtually equivalent to the boundedness of the two-weight Hilbert transform. This makes the embedding question quite difficult (general boundedness criteria of Hunt-Muckenhoupt-Wheeden type for the twoweight Hilbert transform have yet to be found). Here we are not interested in sufficient conditions for the embedding ofKg into L²(Μ) (equivalent to a certain two-weight problem for the Hilbert transform). Rather, we are interested in the fact that a certain natural set of conditions is not sufficient for the embedding ofK _θ intoL ² (Μ) (equivalently, a certain set of conditions is not sufficient for the boundedness in a two-weight problem for the Hilbert transform). In particular, we answer (negatively) certain questions of W. Cohn about the embedding ofK _θ into L²(Μ). Our technique leads naturally to the conclusion that there can be a uniform embedding of all the reproducing kernels ofK _θ but the embedding of the wholeK _θ intoL ²(Μ) may fail. Moreover, it may happen that the embedding into a potentially larger spaceL ²(μ) fails too. Both authors are supported by the NSF grant DMS 9970395 and joint American-Israeli grant BSF 00030.     

Asymptotic behavior and uniqueness of blow-up solutions of quasilinear elliptic equations

In this paper, we study the asymptotic behavior of solutions of the problem Δ _p u = f (u) in Ω, u = ∞ on ∂Ω, under general conditions on the function f, where Ω _p is the p-Laplace operator. We show that the technique used by the author for the special case p = 2 works in this more general setting, and that the behavior described by various authors for the case p = 2 is easily derived from this technique for the general case.     

Representation,interpolation, and reiteration theorems for generalized approximation spaces

We show that the representation theorem for classical approximation spaces can be generalized to spaces A(X,l ^q (ℬ))={f∈X:{E _n (f)}∈l ^q (ℬ)} in which the weighted l ^q -space l ^q (ℬ) can be (more or less) arbitrary. We use this theorem to show that generalized approximation spaces can be viewed as real interpolation spaces (defined with K-functionals or main-part K-functionals) between couples of quasi-normed spaces which satisfy certain Jackson and Bernstein-type inequalities. Especially, interpolation between an approximation space and the underlying quasi-normed space leads again to an approximation space. Together with a general reiteration theorem, which we also prove in the present paper, we obtain formulas for interpolation of two generalized approximation spaces. Received: December 6, 2001; in final form: April 2, 2002?Published online: March 14, 2003     

The Neumann problem for some degenerate elliptic equations

In the paper we study the equation L _u = f, where L is a degenerate elliptic operator, with Neumann boundary condition in a bounded open set μ. We prove existence and uniqueness of solutions in the space H(μ) for the Neumann problem.     

Conductors and newforms for U(1,1)

Let F be a non-Archimedean local field whose residue characteristic is odd. In this paper we develop a theory of newforms forU (1, 1)(F), building on previous work onSL ₂(F). This theory is analogous to the results of Casselman forGL ₂(F) and Jacquet, Piatetski-Shapiro, and Shalika forGL _n(F). To a representation π ofU(1, 1)(F), we attach an integer c(π) called the conductor of π, which depends only on theL-packet π containing π. A newform is a vector in π which is essentially fixed by a congruence subgroup of level c(π). We show that our newforms are always test vectors for some standard Whittaker functionals, and, in doing so, we give various explicit formulae for newforms.     

Quasirecognition by prime graph of F4(q) where q?=?2n?>?2

The prime graph of a finite group G is denoted by Γ(G). In this paper as the main result, we show that if G is a finite group such that Γ(G) = Γ(F ₄(q)), where q = 2 ⁿ  > 2, then G has a unique nonabelian composition factor isomorphic to F ₄(q). We also show that if G is a finite group satisfying |G| = |F ₄(q)| and Γ(G) = Γ(F ₄(q)), where q = 2 ⁿ  > 2, then G @ F₄(q){G \cong F_4(q)}. As a consequence of our result we give a new proof for a conjecture of Shi and Bi for F ₄(q) where q = 2 ⁿ  > 2.     

Saddlepoint approximation for moments of random variables

In this paper, we introduce a saddlepoint approximation method for higher-order moments like E(S − a)₊ ^m , a>0, where the random variable S in these expectations could be a single random variable as well as the average or sum of some i.i.d random variables, and a > 0 is a constant. Numerical results are given to show the accuracy of this approximation method.     

Finite 2-groups with a nonabelian Frattini subgroup of order 16

According to a classical result of Burnside, if G is a finite 2-group, then the Frattini subgroup Φ(G) of G cannot be a nonabelian group of order 8. Here we study the next possible case, where G is a finite 2-group and Φ(G) is nonabelian of order 16. We show that in that case Φ(G) ≅ M × C₂, where M ≅ D₈ or M ≅ Q₈ and we shall classify all such groups G (Theorem A). Received: 16 February 2005; revised: 7 March 2005