Lower bounds for testing triangle-freeness in Boolean functions

Given a Boolean function , we say a triple (x, y, x + y) is a triangle in f if . A triangle-free function contains no triangle. If f differs from every triangle-free function on at least points, then f is said to be -far from triangle-free. In this work, we analyze the query complexity of testers that, with constant probability, distinguish triangle-free functions from those -far from triangle-free. Let the canonical tester for triangle-freeness denotes the algorithm that repeatedly picks x and y uniformly and independently at random from , queries f(x), f(y) and f(x + y), and checks whether f(x) = f(y) = f(x + y) = 1. Green showed that the canonical tester rejects functions -far from triangle-free with constant probability if its query complexity is a tower of 2's whose height is polynomial in . Fox later improved the height of the tower in Green's upper bound to . A trivial lower bound of on the query complexity is immediate. In this paper, we give the first non-trivial lower bound for the number of queries needed. We show that, for every small enough , there exists an integer such that for all there exists a function depending on all n variables which is -far from being triangle-free and requires queries for the canonical tester. We also show that the query complexity of any general (possibly adaptive) one-sided tester for triangle-freeness is at least square root of the query complexity of the corresponding canonical tester. Consequently, this means that any one-sided tester for triangle-freeness must make at least queries.

On the cubicity of bipartite graphs

A unit cube in k-dimension (or a k-cube) is defined as the Cartesian product R-1 x R-2 x ... x R-k, where each R-i is a closed interval on the real line of the form [a(j), a(i), + 1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph. It is known that for graph G, cub(G) <= left perpendicular2n/3right perpendicular. Recently it has been shown that for a graph G, cub(G) >= 4(Delta + 1) In n, where n and Delta are the number of vertices and maximum degree of G, respectively. In this paper, we show that for a bipartite graph G = (A boolean OR B, E) with |A| = n(1), |B| = n2, n(1) <= n(2), and Delta' = min {Delta(A),Delta(B)}, where Delta(A) = max(a is an element of A)d(a) and Delta(B) = max(b is an element of B) d(b), d(a) and d(b) being the degree of a and b in G, respectively , cub(G) <= 2(Delta' + 2) bar left rightln n(2)bar left arrow. We also give an efficient randomized algorithm to construct the cube representation of G in 3 (Delta' + 2) bar right arrowIn n(2)bar left arrow dimension. The reader may note that in general Delta' can be much smaller than Delta.

An eigenproblem approach to classical screw theory

This paper presents a novel algebraic formulation of the central problem of screw theory, namely the determination of the principal screws of a given system. Using the algebra of dual numbers, it shows that the principal screws can be determined via the solution of a generalised eigenproblem of two real, symmetric matrices. This approach allows the study of the principal screws of the general two-, three-systems associated with a manipulator of arbitrary geometry in terms of closed-form expressions of its architecture and configuration parameters. We also present novel methods for the determination of the principal screws for four-, five-systems which do not require the explicit computation of the reciprocal systems. Principal screws of the systems of different orders are identified from one uniform criterion, namely that the pitches of the principal screws are the extreme values of the pitch.The classical results of screw theory, namely the equations for the cylindroid and the pitch-hyperboloid associated with the two-and three-systems, respectively have been derived within the proposed framework. Algebraic conditions have been derived for some of the special screw systems. The formulation is also illustrated with several examples including two spatial manipulators of serial and parallel architecture, respectively.

Algebraic characterization of decentralized fixed modes

An input-output, frequency-domain characterization of decentralized fixed modes is given in this paper, using only standard block-diagram algebra, well-known determinantal expansions and the Binet-Cauchy formula.

Representations and properties of para-Bose oscillator operators. I. Energy position and momentum eigenstates

Para-Bose commutation relations are related to the SL(2,R) Lie algebra. The irreducible representation [script D]alpha of the para-Bose system is obtained as the direct sum Dbeta[direct-sum]Dbeta+1/2 of the representations of the SL(2,R) Lie algebra. The position and momentum eigenstates are then obtained in this representation [script D]alpha, using the matrix mechanical method. The orthogonality, completeness, and the overlap of these eigenstates are derived. The momentum eigenstates are also derived using the wave mechanical method by specifying the domain of the definition of the momentum operator in addition to giving it a formal differential expression. By a careful consideration in this manner we find that the two apparently different solutions obtained by Ohnuki and Kamefuchi in this context are actually unitarily equivalent. Journal of Mathematical Physics is copyrighted by The American Institute of Physics.

On the Arrangement of Cliques in Chordal Graphs with respect to the Cuts

A cut (A, B) (where B = V - A) in a graph G = (V, E) is called internal if and only if there exists a vertex x in A that is not adjacent to any vertex in B and there exists a vertex y is an element of B such that it is not adjacent to any vertex in A. In this paper, we present a theorem regarding the arrangement of cliques in a chordal graph with respect to its internal cuts. Our main result is that given any internal cut (A, B) in a chordal graph G, there exists a clique with kappa(G) + vertices (where kappa(G) is the vertex connectivity of G) such that it is (approximately) bisected by the cut (A, B). In fact we give a stronger result: For any internal cut (A, B) of a chordal graph, and for each i, 0 <= i <= kappa(G) + 1 such that vertical bar K-i vertical bar = kappa(G) + 1, vertical bar A boolean AND K-i vertical bar = i and vertical bar B boolean AND K-i vertical bar = kappa(G) + 1 - i. An immediate corollary of the above result is that the number of edges in any internal cut (of a chordal graph) should be Omega(k(2)), where kappa(G) = k. Prompted by this observation, we investigate the size of internal cuts in terms of the vertex connectivity of the chordal graphs. As a corollary, we show that in chordal graphs, if the edge connectivity is strictly less than the minimum degree, then the size of the mincut is at least kappa(G)(kappa(G)+1)/2 where kappa(G) denotes the vertex connectivity. In contrast, in a general graph the size of the mincut can be equal to kappa(G). This result is tight.

Superconformal transformations of theN = 2,D = 4, SSYM

We obtain the superconformal transformation laws for theN=2,D=4 SSYM. The transformations involve Yang-Mills fields and the corresponding field strength tensor is not constrained to be self antidual. We explicitly demonstrate the closure of the superconformal algebra.

Embedding Of Non-Simple Lie-Groups, Coupling-Constant Relations And Non-Uniqueness Of Models Of Unification

A general derivation of the coupling constant relations which result on embedding a non-simple group like SU L (2) @ U(1) in a larger simple group (or graded Lie group) is given. It is shown that such relations depend only on the requirement (i) that the multiplet of vector fields form an irreducible representation of the unifying algebra and (ii) the transformation properties of the fermions under SU L (2). This point is illustrated in two ways, one by constructing two different unification groups containing the same fermions and therefore have same Weinberg angle; the other by putting different SU L (2) structures on the same fermions and consequently have different Weinberg angles. In particular the value sin~0=3/8 is characteristic of the sequential doublet models or models which invoke a large number of additional leptons like E 6, while addition of extra charged fermion singlets can reduce the value of sin ~ 0 to 1/4. We point out that at the present time the models of grand unification are far from unique.

Functional programming systems revisited

Functional Programming (FP) systems are modified and extended to form Nondeterministic Functional Programming (NFP) systems in which nondeterministic programs can be specified and both deterministic and nondeterministic programs can be verified essentially within the system. It is shown that the algebra of NFP programs has simpler laws in comparison with the algebra of FP programs. "Regular" forms are introduced to put forward a disciplined way of reasoning about programs. Finally, an alternative definition of "linear" forms is proposed for reasoning about recursively defined programs. This definition, when used to test the linearity of forms, results in simpler verification conditions than those generated by the original definition of linear forms.

Spinorial relativistic rotator: The transformation from quasi-Newtonian to Minkowski coordinates

There exists a remarkably close relationship between the operator algebra of the Dirac equation and the corresponding operators of the spinorial relativistic rotator (an indecomposable object lying on a mass-spin Regge trajectory). The analog of the Foldy-Wouthuysen transformation (more generally, the transformation between quasi-Newtonian and Minkowski coordinates) is constructed and explicit results are discussed for the spin and position operators. Zitterbewegung is shown to exist for a system having only positive energies.

Geometrical interpretation of Inönü-Wigner contractions

The Inönü-Wigner contractions which interrelate the Lie algebras of the isometry groups of metric spaces are discussed with reference to deformations of the absolutes of the spaces. A general formula is derived for the Lie algebra commutation relations of the isometry group for anyN-dimensional metric space. These ideas are illustrated by a discussion of important particular cases, which interrelate the four-dimensional de Sitter, Poincaré, and Galilean groups.

Use of Multiblade Coordinates for Helicopter Flap-Lag Stability with Dynamic Inflow

Rotor flap-lag stability in forward flight is studied with and without dynamic inflow feedback via a multiblade coordinate transformation (MCT). The algebra of MCT is found to be so involved that it requires checking the final equations by independent means. Accordingly, an assessment of three derivation methods is given. Numerical results are presented for three- and four-bladed rotors up to an advance ratio of 0.5. While the constant-coefficient approximation under trimmed conditions is satisfactory for low-frequency modes, it is not satisfactory for high-frequency modes or for untrimmed conditions. The advantages of multiblade coordinates are pronounced when the blades are coupled by dynamic inflow.

Multipliers of Sobolev spaces

Let Wm,p denote the Sobolev space of functions on Image n whose distributional derivatives of order up to m lie in Lp(Image n) for 1 less-than-or-equals, slant p less-than-or-equals, slant ∞. When 1 < p < ∞, it is known that the multipliers on Wm,p are the same as those on Lp. This result is true for p = 1 only if n = 1. For, we prove that the integrable distributions of order less-than-or-equals, slant1 whose first order derivatives are also integrable of order less-than-or-equals, slant1, belong to the class of multipliers on Wm,1 and there are such distributions which are not bounded measures. These distributions are also multipliers on Lp, for 1 < p < ∞. Moreover, they form exactly the multiplier space of a certain Segal algebra. We have also proved that the multipliers on Wm,l are necessarily integrable distributions of order less-than-or-equals, slant1 or less-than-or-equals, slant2 accordingly as m is odd or even. We have obtained the multipliers from L1(Image n) into Wm,p, 1 less-than-or-equals, slant p less-than-or-equals, slant ∞, and the multiplier space of Wm,1 is realised as a dual space of certain continuous functions on Image n which vanish at infinity.

Generalised quaternion methods in conformal geometry

A new approach to Penrose's twistor algebra is given. It is based on the use of a generalised quaternion algebra for the translation of statements in projective five-space into equivalent statements in twistor (conformal spinor) space. The formalism leads toSO(4, 2)-covariant formulations of the Pauli-Kofink and Fierz relations among Dirac bilinears, and generalisations of these relations.

Reed-Muller Canonical Forms in Multivalued Logic

Canonical forms for m-valued functions referred to as m-Reed-Muller canonical (m-RMC) forms that are a generalization of RMC forms of two-valued functions are proposed. m-RMC forms are based on the operations ?m (addition mod m) and .m (multiplication mod m) and do not, as in the cases of the generalizations proposed in the literature, require an m-valued function for m not a power of a prime, to be expressed by a canonical form for M-valued functions, where M > m is a power of a prime. Methods of obtaining the m-RMC forms from the truth vector or the sum of products representation of an m-valued function are discussed. Using a generalization of the Boolean difference to m-valued logic, series expansions for m-valued functions are derived.