Parameter choices and a better bound on the list size in the Guruswami–Sudan algorithm for algebraic geometry codes

Given an algebraic geometry code C_L(D, aP){C_{\mathcal L}(D, \alpha P)}, the Guruswami–Sudan algorithm produces a list of all codewords in C_L(D, aP){C_{\mathcal L}(D, \alpha P)} within a specified distance of a received word. The initialization step in the algorithm involves parameter choices that bound the degree of the interpolating polynomial and hence the length of the list of codewords generated. In this paper, we use simple properties of discriminants of polynomials over finite fields to provide improved parameter choices for the Guruswami–Sudan list decoding algorithm for algebraic geometry codes. As a consequence, we obtain a better bound on the list size as well as a lower degree interpolating polynomial.     

Recursive error correction for general Reed-Muller codes

Reed-Muller (RM) codes of growing length n and distance d are considered over a binary symmetric channel. A recursive decoding algorithm is designed that has complexity of order nlogn and corrects most error patterns of weight (dlnd)/2. The presented algorithm outperforms other algorithms with nonexponential decoding complexity, which are known for RM codes. We evaluate code performance using a new probabilistic technique that disintegrates decoding into a sequence of recursive steps. This allows us to define the most error-prone information symbols and find the highest transition error probability p, which yields a vanishing output error probability on long codes.     

An abstract doubly nonlinear equation with a measure as initial value

The solvability of the abstract implicit nonlinear nonautonomous differential equation (A(t)u^′(t))+B(t)u(t)+C(t)u(t)∋f(t) will be investigated in the case of a measure as an initial value. It will be shown that this problem has a solution if the inner product of A(t)x and B(t)x+C(t)x is bounded below.     

Extensions and new observations of Tychonoff,Stone-Weierstrass theorems,compactifications and the realcompactification

An extension of the Tychonoff theorem is obtained in characterizing a compact space by the nets and the images induced by any family of continuous functions on it. The idea of this extension is applied to get a new process and new observations of compactifications and the realcompactification. Finally, a sufficient and necessary condition of a vector sublattice or a subalgebra of C¹(X) to be dense in (C¹(X),∥·∥) is provided in terms of the nets in X induced by C¹(X), where C¹(X) is the space of all bounded real continuous functions on a topological space X with pointwise ordering, and ∥·∥ is the supremum norm.     

The small weight codewords of the functional codes associated to non-singular Hermitian varieties

This article studies the small weight codewords of the functional code C _Herm (X), with X a non-singular Hermitian variety of PG(N, q ²). The main result of this article is that the small weight codewords correspond to the intersections of X with the singular Hermitian varieties of PG(N, q ²) consisting of q + 1 hyperplanes through a common (N ? 2)-dimensional space Π, forming a Baer subline in the quotient space of Π. The number of codewords having these small weights is also calculated. In this way, similar results are obtained to the functional codes C ₂(Q), Q a non-singular quadric (Edoukou et al., J. Pure Appl. Algebra 214:1729–1739, 2010), and C ₂(X), X a non-singular Hermitian variety (Hallez and Storme, Finite Fields Appl. 16:27–35, 2010).     

Decoding Algebraic Geometry Codes by a Key Equation

A new effective decoding algorithm is presented for arbitrary algebraic-geometric codes on the basis of solving a generalized key equation with the majority coset scheme of Duursma. It is an improvement of Ehrhard's algorithm, since the method corrects up to half of the Goppa distance with complexity order $\text{O}$(n^2.81), and with no further assumption on the degree of the divisor G.     

An exact algorithm for MAX-CUT in sparse graphs

We study exact algorithms for the MAX-CUT problem. Introducing a new technique, we present an algorithmic scheme that computes a maximum cut in graphs with bounded maximum degree. Our algorithm runs in time O^*(2^(1-(2/Δ))n). We also describe a MAX-CUT algorithm for general graphs. Its time complexity is O^*(2^mn/(m+n)). Both algorithms use polynomial space.     

Fast decoding of quasi-perfect Lee distance codes

A code D over Z ² _n is called a quasi-perfect Lee distance-(2t + 1) code if d _L(V,W) ≥ 2t + 1 for every two code words V,W in D, and every word in Z ² _n is at distance ≤ t + 1 from at least one code word, where D _L(V,W) is the Lee distance of V and W. In this paper we present a fast decoding algorithm for quasi-perfect Lee codes. The basic idea of the algorithm comes from a geometric representation of D in the 2-dimensional plane. It turns out that to decode a word it suffices to calculate its distance to at most four code words.     

Coloring graphs from random lists of size 2

Let G=G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set C of size σ(n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring φ such that φ(v)∈L(v) for all v∈V(G). In particular, we show that if g is odd and σ(n)=ω(n^1/(2g−2)), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n→∞. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n≥g, there is a graph H=H(n,g) with bounded maximum degree and girth g, such that if σ(n)=o(n^1/(2g−2)), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n→∞. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size σ(n), exhibits a sharp threshold at σ(n)=2n.     

Farthest-polygon Voronoi diagrams

Given a family of k disjoint connected polygonal sites in general position and of total complexity n, we consider the farthest-site Voronoi diagram of these sites, where the distance to a site is the distance to a closest point on it. We show that the complexity of this diagram is O(n), and give an O(nlog³n) time algorithm to compute it. We also prove a number of structural properties of this diagram. In particular, a Voronoi region may consist of k−1 connected components, but if one component is bounded, then it is equal to the entire region.     

Heat flow and Hardy inequality in complete Riemannian manifolds with singular initial conditions

Upper bounds are obtained for the heat content of an open set D with singular initial condition f on a complete Riemannian manifold, provided (i) the Dirichlet-Laplace-Beltrami operator satisfies a strong Hardy inequality, and (ii) f satisfies an integrability condition. Precise asymptotic results for the heat content are obtained for an open bounded and connected set D in Euclidean space with C² boundary, and with initial condition f(x)=δ(x)^−α,0<α<2, where δ(x) is the distance from x to the boundary of D.     

On codewords in the dual code of classical generalised quadrangles and classical polar spaces

In [J.L. Kim, K. Mellinger, L. Storme, Small weight codewords in LDPC codes defined by (dual) classical generalised quadrangles, Des. Codes Cryptogr. 42 (1) (2007) 73-92], the codewords of small weight in the dual code of the code of points and lines of Q(4,q) are characterised. Inspired by this result, using geometrical arguments, we characterise the codewords of small weight in the dual code of the code of points and generators of Q⁺(5,q) and H(5,q²), and we present lower bounds on the weight of the codewords in the dual of the code of points and k-spaces of the classical polar spaces. Furthermore, we investigate the codewords with the largest weights in these codes, where for q even and k sufficiently small, we determine the maximum weight and characterise the codewords of maximum weight. Moreover, we show that there exists an interval such that for every even number w in this interval, there is a codeword in the dual code of Q⁺(5,q), q even, with weight w and we show that there is an empty interval in the weight distribution of the dual of the code of Q(4,q), q even. To prove this, we show that a blocking set of Q(4,q), q even, of size q²+1+r, where 0<r<(q+4)/6, contains an ovoid of Q(4,q), improving on [J. Eisfeld, L. Storme, T. Sz?nyi, P. Sziklai, Covers and blocking sets of classical generalised quadrangles, Discrete Math. 238 (2001) 35-51, Theorem 9].     

On holomorphic families of Schrödinger-type operators with singular potentials on manifolds of bounded geometry

We consider a family of Schrödinger-type differential expressions L(κ)=D²+V+κV(1), where κ∈C, and D is the Dirac operator associated with a Clifford bundle (E,∇E) of bounded geometry over a manifold of bounded geometry (M,g) with metric g, and V and V(1) are self-adjoint locally integrable sections of EndE. We also consider the family I(κ)=^*(∇F)∇F+V+κV(1), where κ∈C, and ∇F is a Hermitian connection on a Hermitian vector bundle F of bonded geometry over a manifold of bounded geometry (M,g), and V and V(1) are self-adjoint locally integrable sections of EndF. We give sufficient conditions for L(κ) and I(κ) to have a realization in L²(E) and L²(F), respectively, as self-adjoint holomorphic families of type (B). In the proofs we use Kato's inequality for Bochner Laplacian operator and Weitzenböck formula.     

Harmonic analysis and asymptotic behavior of solutions to the abstract cauchy problem

LetC _ub ( $\mathbb{J}$ , X) denote the Banach space of all uniformly continuous bounded functions defined on $\mathbb{J}$ 2 ε {?⁺, ?} with values in a Banach spaceX. Let ? be a class fromC _ub( $\mathbb{J}$ ,X). We introduce a spectrumsp?(φ) of a functionφ εC _ub (?,X) with respect to ?. This notion of spectrum enables us to investigate all twice differentiable bounded uniformly continuous solutions on ? to the abstract Cauchy problem (*)ω′(t) =Aω(t) +φ(t),φ(0) =x,φ ε ?, whereA is the generator of aC ₀-semigroupT(t) of bounded operators. Ifφ = 0 andσ(A) ∩i? is countable, all bounded uniformly continuous mild solutions on ?⁺ to (*) are studied. We prove the bound-edness and uniform continuity of all mild solutions on ?⁺ in the cases (i)T(t) is a uniformly exponentially stableC ₀-semigroup andφ εC _ub(?,X); (ii)T(t) is a uniformly bounded analyticC ₀-semigroup,φ εC _ub (?,X) andσ(A) ∩i sp(φ) = Ø. Under the condition (i) if the restriction ofφ to ?⁺ belongs to ? = ?(?⁺,X), then the solutions belong to ?. In case (ii) if the restriction ofφ to ?⁺ belongs to ? = ?(?⁺,X), andT(t) is almost periodic, then the solutions belong to ?. The existence of mild solutions on ? to (*) is also discussed.     

Reed-Muller codes and permutation decoding

We show that the first- and second-order Reed-Muller codes, R(1,m) and R(2,m), can be used for permutation decoding by finding, within the translation group, (m−1)- and (m+1)-PD-sets for R(1,m) for m≥5,6, respectively, and (m−3)-PD-sets for R(2,m) for m≥8. We extend the results of Seneviratne [P. Seneviratne, Partial permutation decoding for the first-order Reed-Muller codes, Discrete Math., 309 (2009), 1967-1970].     

Nodal solutions for singularly perturbed equations with critical exponential growth

The existence and concentration behavior of nodal solutions are established for the equation −?²Δu+V(z)u=f(u) in Ω, where Ω is a domain in R², not necessarily bounded, V is a positive Hölder continuous function and f∈C¹ is an odd function having critical exponential growth.     

Distance regularity of Kerdock codes

A code is called distance regular, if for every two codewords x, y and integers i, j the number of codewords z such that d(x, z) = i and d(y, z) = j, with d the Hamming distance, does not depend on the choice of x, y and depends only on d(x, y) and i, j. Using some properties of the discrete Fourier transform we give a new combinatorial proof of the distance regularity of an arbitrary Kerdock code. We also calculate the parameters of the distance regularity of a Kerdock code.     

Polynomially bounded solutions to the Loewner differential equation in several complex variables

We determine the form of polynomially bounded solutions to the Loewner differential equation that is satisfied by univalent subordination chains of the form f(z,t)=etAz+?, where A∈L(Cn,Cn) has the property m(A)>0. Here m(A)=min{R〈A(z),z〉:‖z‖=1}. We also give sufficient conditions for g(z,t)=L(f(z,t)) to be polynomially bounded, where f(z,t) is an A-normalized polynomially bounded Loewner chain solution to the Loewner differential equation.     

Fixed point theorems for multivalued nonexpansive mappings satisfying inwardness conditions

Let X be a Banach space whose characteristic of noncompact convexity is less than 1 and satisfies the nonstrict Opial condition. Let C be a bounded closed convex subset of X, KC(X) the family of all compact convex subsets of X and T a nonexpansive mapping from C into KC(X) with bounded range. We prove that T has a fixed point. The nonstrict Opial condition can be removed if, in addition, T is an 1-χ-contractive mapping.