On P versus NP $ \cap $ co-NP for decision trees and read-once branching programs

It is known that if a Boolean function f in n variables has a DNF and a CNF of size then f also has a (deterministic) decision tree of size exp(O(log n log² N)). We show that this simulation cannot be made polynomial: we exhibit explicit Boolean functions f that require deterministic trees of size exp where N is the total number of monomials in minimal DNFs for f and ?f. Moreover, we exhibit new examples of explicit Boolean functions that require deterministic read-once branching programs of exponential size whereas both the functions and their negations have small nondeterministic read-once branching programs. One example results from the Bruen—Blokhuis bound on the size of nontrivial blocking sets in projective planes: it is remarkably simple and combinatorially clear. Other examples have the additional property that f is in AC⁰. Received: June 5 1997.     

Fuzzy Information On Discrete And Continuous Domains: Approximation Results

Measures of information based on fuzzy sets have been defined both for finite and for continuous universes. In the continuous case, the measure of information I(f) depends on the concept of non-increasing rearrangement of the function f. It has been observed that I(f) can be obtained as a limit of discrete distributions π^(N) approximating f. We consider the approximation problem in more detail, and study the convergence of I(π^(N)) to I(f) in terms of the smoothness properties of f itself (modulus of continuity and Lipschitz exponent).     

Equivalence of distinct characterizations for rational rotation-minimizing frames on quintic space curves

A rotation-minimizing frame on a space curve r(t) is an orthonormal basis (f₁,f₂,f₃) for R³, where f₁=r^′/|r^′| is the curve tangent, and the normal-plane vectors f₂,f₃ exhibit no instantaneous rotation about f₁. Such frames are useful in spatial path planning, swept surface design, computer animation, robotics, and related applications. The simplest curves that have rational rotation-minimizing frames (RRMF curves) comprise a subset of the quintic Pythagorean-hodograph (PH) curves, and two quite different characterizations of them are currently known: (a) through constraints on the PH curve coefficients; and (b) through a certain polynomial divisibility condition. Although (a) is better suited to the formulation of constructive algorithms, (b) has the advantage of remaining valid for curves of any degree. A proof of the equivalence of these two different criteria is presented for PH quintics, together with comments on the generalization to higher-order curves. Although (a) and (b) are both sufficient and necessary criteria for a PH quintic to be an RRMF curve, the (non-obvious) proof presented here helps to clarify the subtle relationships between them.     

The Deutsch–Jozsa problem: de-quantisation and entanglement

The Deutsch–Jozsa problem is one of the most basic ways to demonstrate the power of quantum computation. Consider a Boolean function f : {0, 1} ⁿ → {0, 1} and suppose we have a black-box to compute f. The Deutsch–Jozsa problem is to determine if f is constant (i.e. f(x) = const, "x ? {0,1}ⁿf(x) = \hbox {const, } \forall x \in \{0,1\}^n) or if f is balanced (i.e. f(x) = 0 for exactly half the possible input strings x ? {0,1}ⁿx \in \{0,1\}^n) using as few calls to the black-box computing f as is possible, assuming f is guaranteed to be constant or balanced. Classically it appears that this requires at least 2 ⁿ⁻¹ + 1 black-box calls in the worst case, but the well known quantum solution solves the problem with probability one in exactly one black-box call. It has been found that in some cases the algorithm can be de-quantised into an equivalent classical, deterministic solution. We explore the ability to extend this de-quantisation to further cases, and examine with more detail when de-quantisation is possible, both with respect to the Deutsch–Jozsa problem, as well as in more general cases.     

Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits

We consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates. We define the entropy of an operator f:{0,1} ⁿ →{0,1} ^m as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Our main result is that every depth-2 circuit for f requires at least entropy(f) wires. This is reminiscent of a classical lower bound of Nechiporuk on the formula size, and gives an information-theoretic explanation of why some operators require many wires. We use this to prove a tight estimate Θ(n ³) of the smallest number of wires in any depth-2 circuit computing the product of two n by n matrices over any finite field. Previously known lower bound for this operator was Ω(n ²log n).     

Nonlinear eigenvalue problems for quasilinear systems

The paper deals with the existence of positive solutions for the quasilinear system (Φ(u'))' + λh(t)f(u) = 0,0 < t < 1 with the boundary condition u(0) = u(1) = 0. The vector-valued function Φ is defined by Φ(u) = (q(t)(p(t)u₁), …, q(t)(p(t)u_n)), where u = (u₁, …, u_n), andcovers the two important cases (u) = u and (u) = up > 1, h(t) = diag[h₁(t), …, h_n(t)] and f(u) = (f¹(u), …, fⁿ (u)). Assume that fⁱ and h_i are nonnegative continuous. For u = (u₁, …, u_n), let

, f₀ = maxf¹₀, …, fⁿ₀ and f_∞ = maxf¹_∞, …, fⁿ_∞. We prove that the boundary value problem has a positive solution, for certain finite intervals of λ, if one of f₀ and f_∞ is large enough and the other one is small enough. Our methods employ fixed-point theorem in a cone.     

Rational trigonometric approximations using Fourier series partial sums

A class of approximations {S _N,M } to a periodic functionf which uses the ideas of Padé, or rational function, approximations based on the Fourier series representation off, rather than on the Taylor series representation off, is introduced and studied. Each approximationS _N,M is the quotient of a trigonometric polynomial of degreeN and a trigonometric polynomial of degreeM. The coefficients in these polynomials are determined by requiring that an appropriate number of the Fourier coefficients ofS _N,M agree with those off. Explicit expressions are derived for these coefficients in terms of the Fourier coefficients off. It is proven that these Fourier-Padé approximations converge point-wise to (f(x ⁺) +f(x ^–))/2 more rapidly (in some cases by a factor of 1/k ^2M ) than the Fourier series partial sums on which they are based. The approximations are illustrated by several examples and an application to the solution of an initial, boundary value problem for the simple heat equation is presented.This research was supported by NASA contract NAS1-19480 while the author was in residence at ICASE, NASA Langley Research Center, Hampton, Virginia 23665.     

On the non-existence of stationary diffusions which satisfy the Bene condition

The one-dimensional diffusion x_t satisfying dx_t = f(x_t)dt + dw_t, where w_t is a standard Brownian motion and f(x) satisfies the Bene condition f′(x) + f²(x) = ax² + bx + c for all real x, is considered. It is shown that this diffusion does not admit a stationary probability measure except for the linear case f(x) = αx + β, α < 0.     

A practical algorithm for making filled graphs minimal

For an arbitrary filled graph G⁺ of a given original graph G, we consider the problem of removing fill edges from G⁺ in order to obtain a graph M that is both a minimal filled graph of G and a subgraph of G⁺. For G⁺ with f fill edges and e original edges, we give a simple O(f(e+f)) algorithm which solves the problem and computes a corresponding minimal elimination ordering of G. We report on experiments with an implementation of our algorithm, where we test graphs G corresponding to some real sparse matrix applications and apply well-known and widely used ordering heuristics to find G⁺. Our findings show the amount of fill that is commonly removed by a minimalization for each of these heuristics, and also indicate that the runtime of our algorithm on these practical graphs is better than the presented worst-case bound.     

Harmonic Analysis, Real Approximation, and the Communication Complexity of Boolean Functions

The two-party communication complexity of Boolean function f is known to be at least log rank (M _f ), i.e., the logarithm of the rank of the communication matrix of f [19]. Lovász and Saks [17] asked whether the communication complexity of f can be bounded from above by (log rank (M _f )) ^c , for some constant c . The question was answered affirmatively for a special class of functions f in [17], and Nisan and Wigderson proved nice results related to this problem [20], but, for arbitrary f , it remained a difficult open problem. We prove here an analogous polylogarithmic upper bound in the stronger multiparty communication model of Chandra et al. [6], which, instead of the rank of the communication matrix, depends on the L ₁ norm of function f , for arbitrary Boolean function f . Received August 24, 1996; revised October 15, 1997.     

When do extra majority gates help? Polylog (N) majority gates are equivalent to one

Suppose that a Boolean functionf is computed by a constant depth circuit with 2 ^m AND-, OR-, and NOT-gates—andm majority-gates. We prove thatf is computed by a constant depth circuit with AND-, OR-, and NOT-gates—and a single majority-gate, which is at the root.One consequence is that if a Boolean functionf is computed by an AC⁰ circuit plus polylog majority-gates, thenf is computed by a probabilistic perceptron having polylog order. Another consequence is that iff agrees with the parity function on three-fourths of all inputs, thenf cannot be computed by a constant depth circuit with AND-, OR-, and NOT-gates, and majority-gates.     

Diagonal polynomials for small dimensions

HereR andN denote respectively the real numbers and the nonnegative integers. Also 0 <n εN, ands(x) =x ₁+...+x _n when x = (x ₁,...,x _n) εR ⁿ. Adiagonal function of dimensionn is a mapf onN ⁿ (or any larger set) that takesN ⁿ bijectively ontoN and, for all x, y inN ⁿ, hasf(x) <f(y) whenevers(x) <s(y). We show that diagonalpolynomials f of dimensionn all have total degreen and have the same terms of that degree, so that the lower-degree terms characterize any suchf. We call two polynomialsequivalent if relabeling variables makes them identical. Then, up to equivalence, dimension two admits just one diagonal polynomial, and dimension three admits just two.     

A new quantum claw-finding algorithm for three functions

Fork functionsf ₁, ...f _k, ak-tuple (x ₁, ...x _k) such thatf ₁(x ₁)=...=f _k(x _k) is called a claw off ₁, ...,f _k. In this paper, we construct a new quantum claw-finding algorithm for three functions that is efficient when the numberM of intermediate solutions is small. The known quantum claw-finding algorithm for three functions requiresO(N ^7/8 logN) queries to find a claw, but our algorithm requiresO(N ^3/4 logN) queries ifM ≤ √N andO(N ^7/12 M ^1/3 logN) queries otherwise. Thus, our algorithm is more efficient ifM≤N ^7/8. Kazuo Iwama, Ph.D.: Professor of Informatics, Kyoto University, Kyoto 606-8501, Japan. Received BE, ME, and Ph.D. degrees in Electrical Engineering from Kyoto University in 1978, 1980 and 1985, respectively. His research interests include algorithms, complexity theory and quantum computation. Editorial board of Information Processing Letters and Parallel Computing. Council Member of European Association for Theoretical Computer Science (EATCS). Akinori Kawachi: Received B.Eng. and M.Info. from Kyoto University in 2000 and 2002, respectively. His research interests are quantum computation and distributed computation.     

Evaluating micas in petrologic and metallogenic aspect: I–definitions and structure of the computer program MICA

Micas are significant ferromagnesian minerals in felsic to mafic igneous, metamorphic, and hydrothermal rocks. Because of their considerable potential to reveal the physicochemical conditions of magmas in terms of petrologic and metallogenic aspects, mica chemistry is used extensively in the earth sciences. For example, the composition of phlogopite and biotite can be used to evaluate the intensive thermodynamic parameters of temperature (T, °C), oxygen fugacity (fO₂), and water fugacity (fH₂O) of magmatic rocks. The halogen contents of micas permit the estimation of the fluorine and chlorine fugacities that may be used in understanding the metal transportation and deposition processes in hydrothermal ore deposits. The Mica⁺ computer program has been written to edit and store electron-microprobe or wet-chemical mica analyses. This software calculates structural formulae and shares out the calculated anions into the I, M, T, and A sites. Mica⁺ classifies micas in terms of composition and octahedral site-occupancy. It also calculates the intensive parameters such as fO₂, T, and fH₂O from the composition of biotite in equilibrium with K-feldspar and magnetite. Using the calculated F–OH and Cl–OH exchange systematics and various log ratios (fH₂O/fHF, fH₂O/fHCl, fHCl/fHF, X_Cl/X_OH, X_F/X_OH, X_F/X_Cl) of mica analyses. Mica⁺ gives valuable determinations about the characteristics of hydrothermal fluids associated with alteration and mineralization processes. The program output is generally in the form of screen outputs. However, by using the “Grf” files that come up with this program they can be visualized under the Grapher software both as binary and ternary diagrams. Mica analyses subjected to the Mica⁺ program were calculated on the basis of 22+z positive charges taking into account the procedure by the Commission on New Mineral Names Mica Subcommittee of 1998.     

The Complexity of Deciding if a Boolean Function Can Be Computed by Circuits over a Restricted Basis

We study the complexity of the following algorithmic problem: Given a Boolean function f and a finite set of Boolean functions B, decide if there is a circuit with basis B that computes f. We show that if both f and all functions in B are given by their truth-table, the problem is in quasipolynomial-size AC⁰, and thus cannot be hard for AC⁰(2) or any superclass like NC¹, L, or NL. This answers an open question by Bergman and Slutzki (SIAM J. Comput., 2000). Furthermore we show that, if the input functions are not given by their truth-table but in a succinct way, i.e., by circuits (over any complete basis), the above problem becomes complete for the class coNP. Supported in part by DFG Grant Vo 630/5-2 and EPSRC Grant 531174.     

Local controllability of non-linear systems: An example

An example of a locally controllable nonlinear system on R³ is given. The system is of the type with f, g analytic vector fields and u bounded. The fields f and g are such that the dimension of the vector space spanned at x₀ by the Lie brackets which contain g an odd number of times is 2.     

One-way functions and circuit complexity

A finite function f is a mapping of {0, 1}ⁿ into {0, 1}^m{#}, where “#” is a symbol to be thought of as “undefined.” A family of finite functions is said to be one-way (in a circuit complexity sense) if it can be computed with polynomial-size circuits, but every family of inverses of these functions cannot. In this paper we show that, provided functions that are not one-to-one are allowed, one-way functions exist if and only if the satisfiability problem SAT does not have polynomial-size circuits. A family of functions f_i(x) can be checked if some family of polynomial-size circuits with inputs x and y can determine if f_i(x) = y. A family of functions f_i(x) can be evaluated if some family of polynomial-size circuits with input x can compute f_i(x). Can all families of total functions that can be checked also be evaluated? We show that this is true if and only if the nonuniform versions of the complexity classes P and UP co-UP are equal. A family of functions f_i is one-way for constant depth circuits if f_i can be computed with unbounded famin circuits of polynomial size and constant depth, but every family of inverses f_i⁻¹ cannot. We give two provably one-way functions (in fact permutaions) for constant-depth circuits. The second example has the stronger property that no bit of its inverse can be computed in polynomial size and constant depth.     

The privacy of dense symmetric functions

Ann argument function,f, is calledt-private if there exists a distributed protocol for computingf so that no coalition of at mostt processors can infer any additional information from the execution of the protocol. It is known that every function defined over a finite domain is [(n–1)/2]-private. The general question oft-privacy (fort[n/2]) is still unresolved.In this work, we relate the question of [n/2]-privacy for the class of symmetric functions of Boolean argumentsf: {0, 1} ⁿ {0, 1,...,n} to the structure of Hamming weights inf ^–1(b) (b{0, 1, ...,n}). We show that iff is [n/2]-private, then every set of Hamming weightsf ^–1(b) must be an arithmetic progression. For the class ofdense symmetric functions (defined in the sequel), we refine this to the following necessary and sufficient condition for [n/2]-privacy off: Every collection of such arithmetic progressions must yield non-identical remainders, when computed modulo the greatest common divisor of their differences. This condition is used to show that for dense symmetric functions, [n/2]-privacy impliesn-privacy.