Search

As in earlier works, we consider {0,1}n as a sample space with a probability measure on it, thus making pseudo-Boolean functions into random variables. Under the assumption that the coordinate random variables are independent, we show it is very easy to give an orthonormal basis for the space of pseudo-Boolean random variables of degree at most k. We use this orthonormal basis to find the transform of a given pseudo-Boolean random variable and to answer various least squares minimization questions.

We consider {0,1}n as a sample space with a probability measure on it, thus making pseudo-Boolean functions into random variables. We then derive explicit formulas for approximating a pseudo-Boolean random variable by a linear function if the measure is permutation-invariant, and by a function of degree at most k if the measure is a product measure. These formulas generalize results due to Hammer–Holzman and Grabisch–Marichal–Roubens. We also derive a formula for the best faithful linear approximation that extends a result due to Charnes–Golany–Keane–Rousseau concerning generalized Shapley values. We show that a theorem of Hammer–Holzman that states that a pseudo-Boolean function and its best approximation of degree at most k have the same derivatives up to order k does not generalize to this setting for arbitrary probability measures, but does generalize if the probability measure is a product measure.

We consider anonymous secure communication, where parties not only wish to conceal their communications from outside observers, but also wish to conceal the very fact that they are communicating. We consider the bus framework introduced by Beimel and Dolev (J. Cryptology 16 (2003) 25), where messages are delivered by a bus traveling on a random walk. We generalize this idea to consider more than one bus. We show that if w buses are allowed, then the expected delivery time for a message can be decreased from Θ(n) to Θ(n/w) in the case of a complete graph. Additionally, we introduce a class of graphs called r-partite directed collars and obtain analogous bounds on the expected delivery time for these graphs. We also propose several new features that resolve possible shortcomings in the systems proposed by Beimel and Dolev.

We define a class of codes that we call affine variety codes. These codes are obtained by evaluating functions in the coordinate ring of an affine variety on all the F_q-rational points of the variety. We show that one can, at least in theory, decode these codes up to half the true minimum distance by using the theory of Grobner bases. We extend results of A. B. Cooper and of X. Chen, I. S. Reed, T. Helleseth, and T. K. Truong.

Let X X denote the rational curve with n + 1 n+1 nodes obtained from the Riemann sphere by identifying 0 with ∞ \infty and ζ j \zeta ^j with − ζ j -\zeta ^j for j = 0 , 1 , … , n − 1 j=0,1,\dots ,n-1 , where ζ \zeta is a primitive ( 2 n ) (2n) th root of unity. We show that if n n is even, then X X has no smooth Weierstrass points, while if n n is odd, then X X has 2 n 2n smooth Weierstrass points.

We prove that if there are consecutive gaps at a rational point on a smooth curve defined over a finite field, then one can improve the usual lower bound on the minimum distance of certain algebraic-geometric codes defined using a multiple of the point.

We recently proposed the Edgewise Greedy Algorithm (EGA) for learning a decomposable Markov network of treewidth k approximating a given joint probability distribution of n discrete random variables. The main ingredient of our algorithm is the stepwise forward selection algorithm (FSA) due to Deshpande, Garofalakis, and Jordan. EGA is an efficient alternative to the algorithm (HGA) by Malvestuto, which constructs a model of treewidth k by selecting hyperedges of order k+1. In this paper, we present results of empirical studies that compare HGA, EGA and FSA-K which is a straightforward application of FSA, in terms of approximation accuracy (measured by KL-divergence) and computational time. Our experiments show that (1) on the average, all three algorithms produce similar approximation accuracy; (2) EGA produces comparable or better approximation accuracy and is the most efficient among the three. (3) Malvestuto's algorithm is the least efficient one, although it tends to produce better accuracy when the treewidth is bigger than half of the number of random variabls; (4) EGA coupled with local search has the best approximation accuracy overall, at a cost of increased computation time by 50 percent.

Let Y denote a smooth, projective curve of genus g defined over C. A point P G Y is a Weierstrass point if there exists a rational function on Y with a pole only at P of order at most g, or if there exists a regular differential on Y which vanishes at P to order at least g, or if the divisor gP is special. However, the most "functorial" way to define Weierstrass points is as the zeros of the wronskian, a section of the (g(g + l)/2)th tensor power of the canonical bundle on Y. It is this last definition that we use as the foundation for defining Weierstrass points on singular curves. What is essential is that the sheaf of dualizing differentials should be locally free and this is exactly the property satisfied by Gorenstein curves. Let X be an integral, projective Gorenstein curve of arithmetic genus g > 0 over C. Let ω denote the bundle of dualizing differentials on X and let Sf denote an invertible sheaf on X. Put s = dim H°(X,J?) = h°(&). Assume s > 0 and choose a basis φΪ9...9φsfoτH0(X,5?). We will define a section of S?®sΘω^s'1^2 as follows: Suppose that {U^} is a covering of X by open subsets such that ^f(U^) and ω(UM) are free ^(^ (α) )-modules generated by ψ(a) and τ^a\ respectively. Define FJ f e YilJ^^x) inductively

1. Let X denote a nonsingular, geometrically irreducible, projective curve of genus g defined over the finite field Fq with q elements. Assume that X has Fq-rational points. Let D be a divisor on X defined over Fq (i.e., D is invariant under Gal(F-~q/Fq)). Then L ( D ) will denote the Fq-vector space of all rational functions f on X, defined over Fq, with divisor (f) > D , together with the zero function, and f~(D) will denote the Fqvector space of all rational differentials 77 on X, defined over Fq, with divisor (~/) > D, together with the zero differential. Put l (D) = dimfqL(D) and i (D) = dimFqf~(D). The Riemann-Roch Theorem states that

Let T g {T_g} denote the Teichmüller space and let V V denote the universal family of Teichmüller surfaces of genus g g Let V T g ( n ) V_{{T_g}}^{(n)} denote the n n th symmetric product of V V over T g {T_g} and let J J denote the family of Jacobians over T g {T_g} . Let f : V T g ( n ) → J f:V_{{T_g}}^{(n)} \to \text {J} be the natural relativization over T g {T_g} of the classical map defined by integrating holomorphic differentials. Let \[ u : f ∗ Ω J / T g 1 → Ω V T g / T g ( n ) 1 u:{f^\ast }\Omega _{\text {J} /{T_g}}^1 \to \Omega _{V_{{T_g}/{T_g}}^{(n)}}^1 \] be the map induced by f f . We define G n r G_n^r to be the analytic subspace of V T g ( n ) V_{{T_g}}^{(n)} defined by the vanishing of ∧ n − r + 1 u { \wedge ^{n - r + 1}}u . Put τ = ( r + 1 ) ( n − r ) − r g \tau = (r + 1)(n - r) - rg . We show that G n 1 − G n 2 G_n^1 - G_n^2 , if nonempty, is smooth of pure dimension 3 g − 3 + τ + 1 3g - 3 + \tau + 1 . From this result, we may conclude that, for a generic curve X X , the fiber of G n 1 − G n 2 G_n^1 - G_n^2 over the module point of X X , if nonempty, is smooth of pure dimension τ + 1 \tau + 1 , a classical assertion. Variational formulas due to Schiffer and Spencer and Rauch are employed in the study of G n r G_n^r .

Complex spacss W n r \mathcal {W}_n^r of Weierstrass points are isomorphic to the intersection, on the n n th symmetric product of the universal curve over the Teichmüller space, of complex spaces G n r \mathcal {G}_n^r of special divisors with the diagonal Δ n {\Delta _n} consisting of divisors which are multiples of a point. The tangent space at a point of this intersection is described and it is shown that G n 1 − G n 2 \mathcal {G}_n^1 - \mathcal {G}_n^2 and Δ n {\Delta _n} intersect transversally.

We determine, except for one unsettled case, which combinations of Weierstrass weights can occur on irreducible rational nodal curves of arithmetic genus three. It is shown that the number of nonsingular Weierstrass points on such curves can be any integer between 0 and 6, except 1.

C. Widland [14] has defined Weierstrass points on integral, projective Gorenstein curves. We show here that the Weierstrass points on a generic integral rational nodal curve have the minimal possible weights or, equivalently, that such a curve has the maximum possible number of distinct nonsingular Weierstrass points. Rational curves with g nodes arise in degeneration arguments involving smooth curves of genus g and they have also recently arisen in connection with g-soliton solutions to certain nonlinear partial differential equations [11], [13].

Weierstrass points are defined for invertible sheaves on integral, projective Gorenstein curves. An example is given of a rational nodal curveX and an invertible sheaf ℒ of positive degree onX such that the set of all higher order Weierstrass points of ℒ is not dense inX.

Let X denote a compact Riemann surface of genus g > 1. At each point P~X, there is a sequence of g integers, l=71(P) g. Every compact Riemann surface of genus > 1 has a finite number of Weierstrass points. (See [6] for details.) The question of describing the moduli of compact Riemann surfaces of genus g which have a Weierstrass point with a specified first nongap has been answered by Rauch [14] and Arbarello [1]. The problem of describing the moduli of curves of genus g which have a Weierstrass point with a specified gap sequence has been considered by Hensel-Landsberg [7] and Rauch [15] and recently results on this question have been obtained by Pinkham [13] and RimVitulli [16]. In [9], we defined complex spaces of Weierstrass points of the universal curve and obtained a theorem concerning the smoothness and dimension of these spaces. From this, one can recover the moduli results of Rauch [14]. In order to study the higher Weierstrass nongaps and the entire gap sequence, we must extend our definition in [9]. We do this in w and then prove a theorem concerning the smoothness and dimension of these spaces which is analogous to the main result in [9]. F rom this, we can recover a moduli result of Pinkham [13]. In w 3, we study the geometry of these complex spaces of Weierstrass points of the universal curve of genus 4. We obtain a description of the moduli of Teichmiiller surfaces of genus 4 which have a Weierstrass point with a specified gap sequence. In the following, a complex space is not necessarily reduced. If Y is a complex space, then IYI will denote the underlying set of points. If Y, Z1 . . . . . Z , are closed complex subspaces of a complex space, then by Y Z 1 Z 2 . . . Z

The classical theory of Weierstrass points on a compact Riemann surface is well-known (see, for example, [3]). Ogawa [6] has defined generalized Weierstrass points. Let Y denote a compact complex manifold of (complex) dimension n. Let E denote a holomorphic vector bundle on Y of rank q. Let Jk(E) (k = 0, 1, …) denote the holomorphic vector bundle of k-jets of E [2, p. 112]. Put rk(E) = rank Jk(E) = q.(n + k)!/n!k!. Suppose that Γ(E), the vector space of global holomorphic sections of E, is of dimension γ(E)>0. Consider the trivial bundle Y × Γ(E) and the mapwhich at a point Q∈Y takes a section of E to its k-jet at Q. Put μ = min(γ(E),rk(E)).

We extend results of K. Lee and M.E. OʼSullivan by showing how to use Grobner bases to find the interpolation polynomial for list decoding a one-point AG code C = C L ( r P , D ) on any curve X , where P is an F q -rational point on X and D = P 1 + P 2 + ⋯ + P n is the sum of other F q -rational points on X . We then define the generic interpolation polynomial for list decoding such a code. The generic interpolation polynomial should specialize to the interpolation polynomial for most received strings. We give an example of a family of Reed–Solomon 1-error correcting codes for which a single error can be decoded by a very simple process involving substituting into the generic interpolation polynomial.

Let F"q denote the finite field with q elements. The symmetric group S"n acts on the set G"n","q of all linear subspaces of F"q^n by permuting coordinates. We show that the normalized character of the associated permutation representation of S"n approaches the trivial character as n approaches infinity. We also consider the case of the wreath product of F"q^x and S"n acting on G"n","q, and formulate a conjecture that would yield the asymptotic number of distinct equivalence classes of q-ary linear codes.

It is shown that as a family of projective smooth curves degenerates to an irreducible Gorenstein curve the Weierstrass weight at a point P on the limit curve is the sum of the Weierstrass weights at points on the smooth curves converging to P. C. Widland [8] extended the classical notion of Weierstrass point to integral, projective Gorenstein curves. We considered Weierstrass points of invertible sheaves on such curves in [5] and showed that a singular point is always a Weierstrass point of high weight of any invertible sheaf with at least two linearly independent global sections. We remarked that this may be interpreted to mean that as a family of smooth curves degenerates to an irreducible Gorenstein curve, then many of the Weierstrass points tend towards the singularities. Our goal in this note is to make this statement precise. We work over C. By a "point" of a scheme, we mean a closed point. If X is a scheme of finite type over C, then we denote the associated complex space by Xan. We wish to thank Augusto Nobile and Peter Stiller for helpful conversations. Let S be an integral, noetherian scheme over C and let ir: X -S be a family of Gorenstein curves of arithmetic genus g > 2. By this we will mean that 7r is a flat, proper morphism whose geometric fibers are integral Gorenstein curves of arithmetic genus g. By the theory of duality of coherent sheaves [4, V.9.7 and VII.4 (p. 388)], there is a canonical invertible sheaf w = wx/s on X whose restriction to a fiber X, is the sheaf of dualizing differentials on that curve. Let L be an invertible sheaf on X. Then L is flat over S. Assume that dim h0(X,, Ls) = r > 0 for all s E S. Then 7r2 is locally free of rank r. We define below an effective Cartier divisor 1 (L) on X. We will also use 1 (L) to denote the associated locally principal closed subscheme of X. We note that the subscheme W(L) may not be reduced. The points of W(L) are the L-Weierstrass points of X/S. The wOn-Weierstrass points are called Weierstrass points of order n and the w-Weierstrass points are simply called Weierstrass points. Suppose (s, P) E X and let U be an open neighborhood of (s, P) such that (1) There are sectionsl, ,. . ., Or of L whose restrictions to X,, form a basis for HO(X5,, , L) for all s' e ir(U). (2) LC(U) is a free Ox (U)-module generated by /. (3) wx/s (U) is a free Ox (U)-module generated by r. Define F%,j E F(U, OX) by q$3 = F1,> for j=,...,r, dFi-1,3 = Ft,,3 for i = 2, . ,r and j = 1,. . . ., r, Received by the editors May 15, 1986 and, in revised form, June 27, 1986. 1980 Mathematics Subject Classification (1985 Revision). Primary 14H15.