A note on regular resolution

Tseitin [3] and Galil [1] have proven that for infinitely manyn there is a set of clausesS(n) of the propositional calculus of lengthn such that any regular resolution proof ofS(n) produces at least 2 ^cn distinct new clauses for somec>0. We show that it is possible to obtain a much weaker but still non-polynomial bound of 2 ^{clog 2} n by a simpler argument.     

Economy of description by parsers,DPDA's,and PDA's

It is shown that there is a sequence of languages E₁, E₂,… such that every correct prefix parser (one which detects errors at the earliest possible moment, e.g., LR or LL parsers) for E_n has size 2^cn, yet a deterministic PDA recognizing E_n exists and has size O(n²). There is another easily described sequence of languages N₁, N₂,… for which N has a nondeterministic PDA of size O(n²), but no deterministic PDA of size less than 2^cn. It is shown moreover, that this latter gap can be made arbitrarily large for different sequences of languages.     

A time-luck tradeoff in relativized cryptography

New definitions are proposed for the security of Transient-Key Cryptography (a variant on Public-Key Cryptography) that account for the possibility of super-polynomial-time Monte Carlo cryptanalytical attacks. Weaker definitions no longer appear to be satisfactory in the light of Adleman's recent algorithm capable of breaking the Diffie-Hellman scheme in RTIME(O(2^{0(√n log n)})) for keys of length n. The basic question we address is: How can one relate the amount of time a cryptanalyst is willing to spend decoding cryptograms to his likelihood of success? What more can one say than the obvious “The more time he uses, the less lucky he needs to be?” These questions and others are partially answered in a relativized model of computation in which there exists a transient-key cryptosystem such that even a cryptanalyst willing to spend as much as (almost) O(2^{n/log n}) steps on length n cryptograms cannot hope to break but an exponentially small fraction of them, even if he is allowed to make use of a true random number generator. This is rather tight because the same cryptosystem falls immediately if the cryptanalyst is willing to spend O(2^cn) steps for any constant c > 0.     

Maximum number of edges joining vertices on a cube

Let E_d(n) be the number of edges joining vertices from a set of n vertices on a d-dimensional cube, maximized over all such sets. We show that E_d(n)=∑_i=0^r−1(l_i/2+i)2^l_i, where r and l₀>l₁>?>l_r−1 are nonnegative integers defined by n=∑_i=0^r−12^l_i.     

Lower Bounds for the Weak Pigeonhole Principle and Random Formulas beyond Resolution

We work with an extension of Resolution, called Res(2), that allows clauses with conjunctions of two literals. In this system there are rules to introduce and eliminate such conjunctions. We prove that the weak pigeonhole principle PHP^cn_n and random unsatisfiable CNF formulas require exponential-size proofs in this system. This is the strongest system beyond Resolution for which such lower bounds are known. As a consequence to the result about the weak pigeonhole principle, Res(log) is exponentially more powerful than Res(2). Also we prove that Resolution cannot polynomially simulate Res(2) and that Res(2) does not have feasible monotone interpolation solving an open problem posed by Krají ek.     

On counting pairs of intersecting segments and off-line triangle range searching

We describe a method for decomposing planar sets of segments and points. Using this method we obtain new efficientdeterministic algorithms for counting pairs of intersecting segments, and for answering off-line triangle range queries. In particular we obtain the following results:

1. Givenn segments in the plane, the number of pairs of intersecting segments is counted in timeO(n ^1+?+K ^1/3 n ^2/3+?), whereK is the number of intersection points among the segments, and ?>0 is an arbitrarily small constant.
2. Givenn segments in the plane which are colored with two colors, the number of pairs ofbichromatic intersecting segments is counted in timeO(n ^1+?+K _m ^1/3 n ^2/3+?), whereK _m is the number ofmonochromatic intersection points, and ?>0 is an arbitrarily small constant.
3. Givenn weighted points andn triangles on a plane, the sum of weights of points in each triangle is computed in timeO(n ^1+ε+?^1/3 n ^2/3+ε), where ? is the number of vertices in the arrangement of the triangles, and ?>0 is an arbitrarily small constant.

The above bounds depend sublinearly on the number of intersections among input segmentsK (resp.K _m , ?), which is desirable sinceK (resp.K _m , ?) can range from zero toO(n ²). All of the above algorithms use optimal Θ(n) storage. The constants of proportionality in the big-Oh notation increase as ? decreases. These results are based on properties of the sparse nets introduced by Chazelle [Cha3].     

Numerical algorithms for undamped gyroscopic systems

The solutions of a gyroscopic vibrating system oscillating about an equilibrium position, with no external applied forces and no damping forces, are completely determined by the quadratic eigenvalue problem (−λ²_iM + λ_iG + K)x_i = 0, for i = 1, …, 2n, where M, G, and K are real n × n matrices, and M is symmetric positive definite (denoted by M > 0), G is skew symmetric, and either K > 0 or − K > 0. Gyroscopic system in motion about a stable equilibrium position (with − K > 0) are well understood. Two Lanczos-type algorithms, the pseudo skew symmetric Lanczos algorithm and the J-Lanczos algorithm, are studied for computing some extreme eigenpairs for solving gyroscopic systems in motion about an unstable equilibrium position (with K > 0). Shift and invert strategies, error bounds, implementation issues, and numerical results for both algorithms are presented in details.     

Maximum induced subgraph of a recursive circulant

The recursive circulant RC(n²,4) enjoys several attractive topological properties. Let max_?G(m) denote the maximum number of edges in a subgraph of graph G induced by m nodes. In this paper, we show that , where p₀>p₁>?>pr are nonnegative integers defined by . We then apply this formula to find the bisection width of RC(n²,4). The conclusion shows that, as n-dimensional cube, RC(n²,4) enjoys a linear bisection width.     

Large dicliques in a directed inhomogeneous random graph

Our main interest in this paper is the large dicliques in a directed inhomogeneous random graph model G(n,α, Φ) on n vertices, which has power-law out/in-degree distributions with scaling exponent α>0 and community structures involved in the homophyly matrix Φ. We show that there is a major difference in the size of the largest diclique ω ^d (G(n,α, Φ)) between the case α<2 and α>2 with an intermediate result for α=2. In addition, we show that a simple algorithm with high probability finds a large diclique of size ω ^d (G(n,α, Φ)) in a polynomial time. Our simulation results reveal that the connections between different subcommunities are essential for the formation of large clusters in the networks.     

Fast enumeration algorithm for words with given constraints on run lengths of ones

We propose an algorithm for enumeration and denumeration of words with given constraints on run lengths of ones (dklr-sequences). For large n, operation time of the algorithm (per symbol of a sequence) is at most O(log³ n log log n), where n is the length of enumerated words, whereas for the best known methods it is at least cn, c > 0.     

A satisfiability algorithm and average-case hardness for formulas over the full binary basis

We present a moderately exponential time algorithm for the satisfiability of Boolean formulas over the full binary basis. For formulas of size at most cn, our algorithm runs in time ${2^{(1-\mu_{c})n}}$ for some constant μ _c  > 0. As a byproduct of the running time analysis of our algorithm, we obtain strong average-case hardness of affine extractors for linear-sized formulas over the full binary basis.     

Embedding meshes into locally twisted cubes

As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, mesh embeddings in locally twisted cubes are studied. Let LTQ_n(V, E) denote the n-dimensional locally twisted cube. We present three major results in this paper: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded in LTQ_n with dilation 1 and expansion 1. (2) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded in LTQ_n with dilation 1 and expansion 2. (3) For any integer n ? 3, a 4  × (2ⁿ⁻² − 1) mesh can be embedded in LTQ_n with dilation 2. The first two results are optimal in the sense that the dilations of all embeddings are 1. The embedding of the 2 × 2ⁿ⁻¹ mesh is also optimal in terms of expansion. We also present the analysis of 2p × 2q mesh embedding in locally twisted cubes.     

Multiplicity of positive solutions of a class of nonlinear fractional differential equations

This paper is concerned with the nonlinear fractional differential equation L(D)u=f(x,u), u(0)=0, 0<x<1,where L(D) = Dsn − an−1Dsn−1 − … − a1Ds11 < s2 < … < sn < 1, and aj > 0, j = 1,2,…, n − 1. Some results are obtained for the existence, nonexistence, and multiplicity of positive solutions of the above equation by using Krasnoselskii's fixed-point theorem in a cone. In particular, it is proved that the above equation has N positive solutions under suitable conditions, where N is an arbitrary positive integer.     

Computing sparse permanents faster

Bax and Franklin (2002) gave a randomized algorithm for exactly computing the permanent of any n×n zero-one matrix in expected time exp[−Ω(n1/3/(2lnn))]n². Building on their work, we show that for any constant C>0 there is a constant ?>0 such that the permanent of any n×n (real or complex) matrix with at most Cn nonzero entries can be computed in deterministic time n(2−?) and space O(n). This improves on the Ω(n²) runtime of Ryser's algorithm for computing the permanent of an arbitrary real or complex matrix.     

Constant-time hough transform on the processor arrays with reconfigurable bus systems

We develop constant-time algorithms to compute the Hough transform on a processor array with a reconfigurable bus system (abbreviated to PARBS). The PARBS is a comptuation model which consists of a processor array and a reconfigurable bus system. It is a very powerful computation model in that many problems can be solved efficiently. In this paper, we introduce the concept of iterative-PARBS which is similar to the FOR-loop construct in sequential programming languages. The iterative-PARBS is a building block in which the processing data can be routed through it several times. We can think it as a “hardware subroutine”. Based on this scheme, we are able to explore constant-time Hough transform algorithms on PARBS. The following new results are derived in this study:

1. The sum ofn bits can be computed in O(1) times on a PARBS with O(n ^1+?) processors for any fixed ?>0.
2. The weights of each simple path of ann*n image can be computed in O(1) time on a 3-D PARBS with O(n ^2+?) processors for any fixed ?>0.
3. Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n ^2+?) processors for any fixed ?>0 withp copies of the image pretiled.
4. Thep angle Hough transform of ann*n image can be computed in O(1) time on a PARBS with O(p*n ³) processors.

     

Geometric pattern matching for point sets in the plane under similarity transformations

We consider the following geometric pattern matching problem: Given two sets of points in the plane, P and Q, and some (arbitrary) δ>0, find a similarity transformation T (translation, rotation and scale) such that h(T(P),Q)<δ, where h(⋅,⋅) is the directional Hausdorff distance with L_∞ as the underlying metric; or report that none exists. We are only interested in the decision problem, not in minimizing the Hausdorff distance, since in the real world, where our applications come from, δ is determined by the practical uncertainty in the position of the points (pixels). Similarity transformations have not been dealt with in the context of the Hausdorff distance and we fill the gap here. We present efficient algorithms for this problem imposing a reasonable separation restriction on the points in the set Q. If the L_∞ distance between every pair of points in Q is at least 8δ, then the problem can be solved in O(mn²logn) time, where m and n are the numbers of points in P and Q respectively. If the L_∞ distance between every pair of points in Q is at least cδ, for some c, 0<c<1, we present a randomized approximate solution with expected runtime O(n²c−4ε−8log⁴mn), where ε>0 controls the approximation. Our approximation is on the size of the subset, B⊆P, such that h(T(B),Q)<δ and |B|>(1−ε)|P| with high probability.     

A simple factor-3 approximation for labeling points with circles

In this paper we present a simple factor-(3+ε), 0<ε<1, approximation algorithm, which runs in O(nlogn+n(1/ε)^O(1/ε2)log(D₃/εD₂)) time, for the problem of labeling a set P of n distinct points with uniform circles. (D₂ is the closest pair of P and D₃ is the minimum diameter of all subsets of P with size three.) This problem is known to be NP-hard. Our bound improves the previous factor of 3.6+ε.     

Embedding meshes into twisted-cubes

The n-dimensional twisted-cube, TN_n, is a variation of the hypercube. In this paper, we study embedding of meshes into TN_n. We prove three major results in this paper: (1) For any integer n ? 1, a 2 × 2ⁿ⁻¹ mesh can be embedded into TN_n with dilation 1 and expansion 1. (2) For any integer n ? 4, an m × k(m ? 3, k ? 3) mesh cannot be embedded into TN_n with dilation 1. (3) For any integer n ? 4, two node-disjoint 4 × 2ⁿ⁻³ meshes can be embedded into TN_n with dilation 2 and expansion 1.     

Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. In this paper, we investigate the edge-bipancyclicity of k-ary n-cubes with faulty nodes and edges. It is proved that every healthy edge of the faulty k-ary n-cube with f_v faulty nodes and f_e faulty edges lies in a fault-free cycle of every even length from 4 to kⁿ − 2f_v (resp. kⁿ − f_v) if k ? 4 is even (resp. k ? 3 is odd) and f_v + f_e ? 2n − 3. The results are optimal with respect to the number of node and edge faults tolerated.