The nth reduced BKP hierarchy, the string equation and BW 1+∞-constraints

We study the BKP hierarchy and its n-reduction, for the case that n is odd. This is related to the principal realization of the basic module of the twisted affine Lie algebra % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqaqpepeea0dXdb9aqVe% 0larpepe0lb9cs0-LqLs-Jarpepeea0-qqVe0Firpepa0xar-xfr-x% fj-hmeGabaqaciGacaGaaeqabaWaaeaaeaaakeaadaWfGaqaaiGaco% hacaGGSbWaaSbaaSqaaiaac6gaaeqaaaqabKqaGhaacqWIh4ETaaGc% daahaaWcbeqaaiaacIcacaaIYaGaaiykaaaaaaa!3B2F!\[\mathop {{\mathop{\rm sl}\nolimits} _n }\limits^ ^{(2)} \]. We show that the following two statements for a BKP function are equivalent: (1) is is n-reduced and satisfies the string equation, i.e., L _-1=0, where L _-1 is an element of some natural Virasoro algebra. (2) satisfies the vacuum constraints of the BW ₁₊ algebra. Here BW ₁₊ is the natural analog of the W ₁₊ algebra, which plays a role in the KP case.The research of Johan van de Leur is financially supported by the Stichting Fundamenteel Onderzoek der Materie (FOM).     

On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

Information categories

Information systems have been introduced by Dana Scott as a convenient means of presenting a certain class of domains of computation, usually known as Scott domains. Essentially the same idea has been developed, if less systematically, by various authors in connection with other classes of domains. In previous work, the present authors introduced the notion of anI-category as an abstraction and enhancement of this idea, with emphasis on the solution ofdomain equations of the formD F(D), withF a functor. An important feature of the work is that we arenot confined to domains of computation as usually understood; other classes of spaces, more familiar to mathematicians in general, become also accessible. Here we present the idea in terms of what we callinformation categories, which are concrete I-categories in which the objects are structured sets of tokens and morphisms are relations between tokens. This is more in the spirit of information system work, and enables more specific results to be obtained. Following an account of the general theory, several examples are discussed in some detail: Stone spaces (as an ordinary mathematical example), Scott domains, SFP domains, and continuous bounded complete domains.     

New lower semicontinuity results for polyconvex integrals

Summary We study integral functionals of the formF(u, )= f(u)dx, defined foru C¹(;R ^k), R ⁿ . The functionf is assumed to be polyconvex and to satisfy the inequalityf(A) c₀¦(A)¦ for a suitable constant c₀ > 0, where (A) is then-vector whose components are the determinants of all minors of thek×n matrixA. We prove thatF is lower semicontinuous onC ¹(;R ^k) with respect to the strong topology ofL ¹(;R ^k). Then we consider the relaxed functional , defined as the greatest lower semicontinuous functional onL ¹(;R ^k ) which is less than or equal toF on C¹(;R ^k). For everyu BV(;R ^k) we prove that (u,) f(u)dx+c₀¦D^su¦(), whereDu=u dx+D^su is the Lebesgue decomposition of the Radon measureDu. Moreover, under suitable growth conditions onf, we show that (u,)= f(u)dx for everyu W^1,p(;R ^k), withp min{n,k}. We prove also that the functional (u, ) can not be represented by an inte- gral for an arbitrary functionu BV_loc(R ⁿ;R ^k). In fact, two examples show that, in general, the set function (u, ) is not subadditive whenu BV_loc(R ⁿ;R ^k), even ifu W _loc ^1,p (R ⁿ;R ^k) for everyp < min{n,k}. Finally, we examine in detail the properties of the functionsu BV(;R ^k) such that (u, )= f(u)dx, particularly in the model casef(A)=¦(A)¦.     

Finding the αn-th largest element

We describe an algorithm for selecting the n-th largest element (where 0<<1), from a totally ordered set ofn elements, using at most (1+(1+o(1))H())·n comparisons whereH() is the binary entropy function and theo(1) stands for a function that tends to 0 as tends to 0. For small values of this is almost the best possible as there is a lower bound of about (1+H())·n comparisons. The algorithm obtained beats the global 3n upper bound of Schönhage, Paterson and Pippenger for <1/3.     

On a global descent method for polynomials

Summary Given a complex polynomialp we determine a functionf _p : such that |p(f _p (z))||p(z)|,z withk<1. This result is used to introduce a global root-finding algorithm for polynomials.     

An Ω(n 5/4) lower bound on the randomized complexity of graph properties

A decision tree algorithm determines whether an input graph withn nodes has a property by examining the entries of the graph's adjacency matrix and branching according to the information already gained. All graph properties which are monotone (not destroyed by the addition of edges) and nontrivial (holds for somes but not all graphs) have been shown to require (n ²) queries in the worst case.In this paper, we investigate the power of randomness in recognizing these properties by considering randomized decision tree algorithms in which coins may be flipped to determine the next entry to be examined. The complexity of a randomized algorithm is the expected number of entries that are examined in the worst case. The randomized complexity of a property is the minimum complexity of any randomized decision tree algorithm which computes the property. We improve Yao's lower bound on the randomized complexity of any nontrivial monotone graph property from (n log^1/12 n) to (n ^5/4).     

On depth first search strees inm-out digraphs

We consider depth first search (DFS for short) trees in a class of random digraphs: am-out model. Let _i be thei ^th vertex encountered by DFS andL(i, m, n) be the height of _i in the corresponding DFS tree. We show that ifi/n asn, then there exists a constanta(,m), to be defined later, such thatL(i, m, n)/n converges in probability toa(,m) asn. We also obtain results concerning the number of vertices and the number of leaves in a DFS tree.     

Isomorphisms of Steinberg groups over commutative rings

LetA andR be commutative rings, andm andn be integers3. It is proved that, if :St _m (A)St _n (R) is an isomorphism, thenm=n. Whenn4, we have: (1) Every isomorphism :St _n(A)St _n(R) induces an isomorphism:E _n (A)E _n (R), and is uniquely determined by; (2) IfSt _n (A) St _n (R) thenK _2.n (A)K _2.n (R); (3) Every isomorphismE _n (A) E _n (R) can be lifted to an isomorphismSt _n(A)St _n(R); (4)St _n(A) St _n(R) if and only ifAR. For the casen=3, ifSt ₃(A) andSt ₃(R) are respectively central extensions ofE ₃(A) andE ₃ (R), then the above (1) and (2) hold.The Project supported by National Natural Science Foundation of China     

Maximal order for quadratures usingn evaluations

The problem is to find approximationsI (f; h) to the integralI(f; h)= ₀ ^h f. Such an approximation has local orderp ifI(f; h)–I (f; h)=O(h ^p ) ash0. Let(n) denote the maximal local order possible for a method usingn evaluations of a function or its derivatives. We show that (n)=2n+1 if the information used is Hermitian. This is conjectured to be true in general. The conjecture is established for all methods using three or fewer evaluations.This research was supported in part by the National Science Foundation under Grant MCS75-222-55 and the Office of Naval Research under Contract N00014-76-C-0370, NR 044-422. Numerical results reported in this paper were obtained through the computing facilities of the University of Maryland.     

Weakly isomorphic transformations that are not isomorphic

Summary A new method for construction of transformations T _i: (X _i, B _i, _i) , i=1,2, that are factors of each other but that are not measuretheoretically isomorphic is provided. This method uses ergodic product cocycles of the form S ⁱ ₁xS ⁱ ₂x...,, where : XZ ₂ is a cocycle, S belongs to the centralizer of T and T is an ergodic translation on a compact, monothetic group X.     

A “from scratch” proof of a theorem of Rockafellar and Fulkerson

The theorem of this paper is of the same general class as Farkas' Lemma, Stiemke's Theorem, and the Kuhn—Fourier Theorem in the theory of linear inequalities. LetV be a vector subspace ofR ⁿ , and let intervalsI ¹,, I ⁿ of real numbers be prescribed. A necessary and sufficient condition is given for existence of a vector (x ¹ ,, x ⁿ ) inV such thatx ⁱ I ⁱ (i = 1, ,n); this condition involves the elementary vectors (nonzero vectors with minimal support) ofV . The proof of the theorem uses only elementary linear algebra.The author at present holds a Senior Scientist Award of the Alexander von Humboldt Stiftung.     

The local nature of Δ-coloring and its algorithmic applications

Given a connected graphG=(V, E) with |V|=n and maximum degree such thatG is neither a complete graph nor an odd cycle, Brooks' theorem states thatG can be colored with colors. We generalize this as follows: letG-v be -colored; then,v can be colored by considering the vertices in anO(log n) radius aroundv and by recoloring anO(log n) length augmenting path inside it. Using this, we show that -coloringG is reducible inO(log³ n/log) time to (+1)-vertex coloringG in a distributed model of computation. This leads to fast distributed algorithms and a linear-processorNC algorithm for -coloring.A preliminary version of this paper appeared as part of the paper Improved Distributed Algorithms for Coloring and Network Decomposition Problems, in theProceedings of the ACM Symposium on Theory of Computing pages 581–592, 1992. This research was done when the authors were at the Computer Science Department of Cornell University. The research was supported in part by NSF PYI award CCR-89-96272 with matching funds from UPS and Sun Microsystems.     

Theorem on a convergence condition in the spaces

For a given -function (u), a condition on a -function (u) is found such that it is necessary and sufficient for the following to hold: if f_n(x) f(x) and f _n (x)M (n=1, 2, ...) where M>0 is an absolute constant, then f _n (x)–f(x)0(n). An analogous condition for convergence in Orlicz spaces is obtained as a corollary.Translated from Matematicheskie Zametki, Vol. 21, No. 5, pp. 615–626, May, 1977.The author thanks V. A. Skvortsov for his constant attention and guidance on this paper.     

On the problem of two linearized wells

We study the behaviour of sequences of elastic deformationsy ^{n n} whose gradients approach two linearized wells, and give an application to magnetostriction.This article was processed by the author using the style filepljour1m from Springer-Verlag.     

Complexity of the Frobenius problem

Consider the Frobenius Problem: Given positive integersa ₁,...,a _n witha _i 2 and such that their greatest common divisor is one, find the largest natural number that is not expressible as a non-negative integer combination ofa ₁,...,a _n. In this paper we prove that the Frobenius problem is NP-hard, under Turing reductions.     

Constraint decomposition algorithms in global optimization

Many global optimization problems can be formulated in the form min{c(x, y): x X, y Y, (x, y) Z, y G} where X, Y are polytopes in ^p , ⁿ , respectively, Z is a closed convex set in ^p+n, while G is the complement of an open convex set in ⁿ . The function c: ^p+n is assumed to be linear. Using the fact that the nonconvex constraints depend only upon they-variables, we modify and combine basic global optimization techniques such that some new decomposition methods result which involve global optimization procedures only in ⁿ . Computational experiments show that the resulting algorithms work well for problems with smalln.     

Convergence in distribution and Skorokhod Convergence for the general theory of processes

Summary This paper proves some Skorokhod Convergence Theorems for processes with filtration. Roughly, these are theorems which say that if a family of processes with filtration (X ⁿ , ⁿ ),n, converges in distribution in a suitable sense, then there exists a family of equivalent processes (Y ⁿ , ⁿ ),n, which converges almost surely. The notion of equivalence used is that of adapted distribution, which guarantees that each (X ⁿ , ⁿ ) has the same stochastic properties as (X ⁿ , ⁿ ), with respect to its filtration, such as the martingale property or the Markov property. The appropriate notion of convergence in distribution is convergence in adapted distribution, which is developed in the paper. Fortunately, any tight sequence of processes has a subsequence which converges in adapted distribution. For discrete time processes, (Y ⁿ , ⁿ ),n, and their limit (Y, ) may be taken as all having the same fixed filtration ⁿ =. In the continuous time case, theY ⁿ , ⁿ may require different filtrations ⁿ , which converge to. To handle this, convergence of filtrations is defined and its theory developed.During part of the time this work was in progress, it was supported by an NSERC operating grant, and the author was an NSERC University Research Fellow. The author wishes to thank the Steklov Mathematical Institute of the Soviet Academy of Sciences for its hospitality while the principle research in this paper was being begun, A.N. Shiryaev and P.C. Greenwood, who made the author's visit there possible, and Ján Miná for his hospitality while that research was being finished. We thank the referee who suggested the results in Sect. 12     

Improved Low-Degree Testing and its Applications

NP = PCP(log n, 1) and related results crucially depend upon the close connection between the probability with which a function passes a low degree test and the distance of this function to the nearest degree d polynomial. In this paper we study a test proposed by Rubinfeld and Sudan [30]. The strongest previously known connection for this test states that a function passes the test with probability for some > 7/8 iff the function has agreement with a polynomial of degree d. We present a new, and surprisingly strong, analysis which shows that the preceding statement is true for arbitrarily small , provided the field size is polynomially larger than d/. The analysis uses a version of Hilbert irreducibility, a tool of algebraic geometry.As a consequence we obtain an alternate construction for the following proof system: A constant prover 1-round proof system for NP languages in which the verifier uses O(log n) random bits, receives answers of size O(log n) bits, and has an error probability of at most . Such a proof system, which implies the NP-hardness of approximating Set Cover to within (log n) factors, has already been obtained by Raz and Safra [29]. Raz and Safra obtain their result by giving a strong analysis, in the sense described above, of a new low-degree test that they present.A second consequence of our analysis is a self tester/corrector for any buggy program that (supposedly) computes a polynomial over a finite field. If the program is correct only on fraction of inputs where , then the tester/corrector determines and generates values for every input, such that one of them is the correct output. In fact, our results yield something stronger: Given the buggy program, we can construct randomized programs such that one of them is correct on every input, with high probability. Such a strong self-corrector is a useful tool in complexity theory—with some applications known.* Supported by an NSF CAREER award, an Alfred P. Sloan Fellowship, and a Packard Fellowship. Part of this work was done when this author was at the IBM Thomas J. Watson Research Center.     

Query complexity,or why is it difficult to separateNP A ∩coNP A fromP A by random oraclesA?

By thequery-time complexity of a relativized algorithm we mean the total length of oracle queries made; thequery-space complexity is the maximum length of the queries made. With respect to these cost measures one can define polynomially time- or space-bounded deterministic, nondeterministic, alternating, etc. Turing machines and the corresponding complexity classes. It turns out that all known relativized separation results operate essentially with this cost measure. Therefore, if certain classes do not separate in the query complexity model, this can be taken as an indication that their relativized separation in the classical cost model will require entirely new principles.A notable unresolved question in relativized complexity theory is the separation of NP^A co NP^A fromP ^A under random oraclesA. We conjecture that the analogues of these classes actually coincide in the query complexity model, thus indicating an answer to the question in the title. As a first step in the direction of establishing the conjecture, we prove the following result, where polynomial bounds refer to query complexity.If two polynomially query-time-bounded nondeterministic oracle Turing machines accept precisely complementary (oracle dependent) languages L^A and {0, 1}^*L^A under every oracle A then there exists a deterministic polynomially query-time-bounded oracle Turing machine that accept L^A. The proof involves a sort of greedy strategy to selecting deterministically, from the large set of prospective queries of the two nondeterministic machines, a small subset that suffices to perform an accepting computation in one of the nondeterministic machines. We describe additional algorithmic strategies that may resolve the same problem when the condition holds for a (1–) fraction of the oracles A, a step that would bring us to a non-uniform version of the conjecture. Thereby we reduce the question to a combinatorial problem on certain pairs of sets of partial functions on finite sets.