On the complexity of a family related to the Legendre symbol

Ahlswede, Khachatrian, Mauduit and A. Sárközy introduced the notion of family-complexity of families of binary sequences. They estimated the family-complexity of a large family related to Legendre symbol introduced by Goubin, Mauduit and Sárközy. Here their result is improved, and apart from the constant factor the best lower bound is given for the family-complexity.     

The complexity of many cells in arrangements of planes and related problems

We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m ^2/3 n logn +n ²); we can calculatem such cells specified by a point in each, in worst-case timeO(m ^2/3 n log³ n+n ² logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m ^2/3 n logn+n ²), but this number is onlyO(m ^3/5– n ^4/5+2 +m+n logm), for any>0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m ^3/4– n ^3/4+3 +m) log² n+n logn logm) for any>0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m ^3/4– n ^3/4+3 +m] log² n+n logn logm) for any>0. (v) The maximum number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d>3, isO(m ^2/3 n ^d/3 logn+n ^d–1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by NSF Grant CCR-8714565. Work by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-82-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development. An abstract of this paper has appeared in theProceedings of the 13th International Mathematical Programming Symposium, Tokyo, 1988, p. 147.     

On a class of diophantine equations related to the numbers of cells in hyperplane arrangements

Using some results from the modern theory of diophantine equations we prove that the numbers of cells in simple arrangements of hyperplanes in Rm and Rn (m and n are different positive integers with m,n?2) are finitely many times equal.     

On arithmetic complexity of certain constructive logics

A constructive arithmetical theory is an arbitrary set of closed arithmetical formulas that is closed with respect to derivability in an intuitionsitic arithmetic with the Markov principle and the formal Church thesis. For each arithmetical theory T there is a corresponding logic L(T) consisting of closed predicate formulas in which all arithmetic instances belong to T. For so-called internally enumerable constructive arithmetical theories with the property of existentiality, it is proved that the logic L(T) is II₁ ^T -@#@ complete. This implies, for example, that the logic of traditional constructivism is II₂ ⁰-complete.Translated from Matematicheskie Zametki, Vol. 52, No. 1, pp. 94–104, July, 1992.     

On the complexity of some problems related to graph extensions

The computational complexity of problems related to the construction of k-extensions of graphs is studied. It is proved that the problems of recognizing vertex and edge k-extensions are NP-complete. The complexity of recognizing irreducible, minimal, and exact vertex and edge k-extensions is considered.     

On a family of lie algebras related to homogeneous surfaces

Real affine homogeneous hypersurfaces of general position in three-dimensional complex space ?³ are studied. The general position is defined in terms of the Taylor coefficients of the surface equation and implies, first of all, that the isotropy groups of the homogeneous manifolds under consideration are discrete. It is this case that has remained unstudied after the author’s works on the holomorphic (in particular, affine) homogeneity of real hypersurfaces in three-dimensional complex manifolds. The actions of affine subgroups G ? Aff(3, ?) in the complex tangent space T ^? _p M of a homogeneous surface are considered. The situation with homogeneity can be described in terms of the dimensions of the corresponding Lie algebras. The main result of the paper eliminates “almost trivial” actions of the groups G on the spaces T _p ^? M for affine homogeneous strictly pseudoconvex surfaces of general position in ?³ that are different from quadrics.     

On the complexity of the projective classification of surfaces

LetX be a complex, connected, projective surface. LetL be a very ample line bundle onX, i.e. there is an embedding :X P _c with . In this article we study projective classification for surfaces when the independent variable is large.     

On certain functional equation related to two-sided centralizers

Let m ≥ 0, n ≥ 0 be fixed integers with m + n ≠ 0 and let R be a prime ring with char(R) = 0 or m + n + 1 ≤ char(R) ≠ 2. Suppose that there exists an additive mapping T : R → R satisfying the relation 2T(x ^m+n+1) = x ^m T(x) x ⁿ  + x ⁿ T(x)x ^m for all ${x\in R}$ . In this case T is a two-sided centralizer.     

On certain integral inequalities related to Opial's inequality

The aim of the present paper is to establish some new integral inequalities involving three functions and their derivatives which in the special cases yield the well known Opial inequality and some of its generalizations.     

On information complexity of certain classes of operator equations

For some classes of operator equations of the second kind, we obtain an estimate of information complexity exact in order. We construct a new projection-type method that realizes the optimal estimate. Institute of Mathematics, Ukrainian Academy of Sciences, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 49, No. 9, pp. 1271–1277, September, 1997.     

On critical orientations in the kedem-sharir motion planning algorithm

We discuss a technical problem arising in the motion planning algorithm of Kedem and Sharir [KS], and propose a way to overcome it without increasing the asymptotic complexity of the algorithm The first author was supported by the Eshkol Grant 04601-90 from the Israeli Ministry of Science and Technology. The second author was partly supported by the Fund for Basic Research administered by the Israeli Academy of Sciences, by National Science Foundation Grants CCR-91-22103 and CCR-93-11127, and by grants from the U.S.-Israeli Binational Science Foundation, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. The third author was partly supported by the Interdisciplinary Program at Tel-Aviv University. The third author’s current address is: Department of Computer Science, MIT, Boston, MA, USA.