A novel weighting scheme for random k-SAT关于随机 k-SAT 的新加权方法

Consider a random k-conjunctive normal form F_k(n, rn) with n variables and rn clauses. We prove that if the probability that the formula F_k(n, rn) is satisfiable tends to 0 as n→∞, then r ? 2.83, 8.09, 18.91, 40.81, and 84.87, for k = 3, 4, 5, 6, and 7, respectively.     

On transitive partitions of an <Emphasis Type="Italic">n</Emphasis>-cube into codes

We present methods to construct transitive partitions of the set E ⁿ of all binary vectors of length n into codes. In particular, we show that for all n = 2 ^k ? 1, k ≥ 3, there exist transitive partitions of E ⁿ into perfect transitive codes of length n.     

Linear Time Algorithms for Generalizations of the Longest Common Substring Problem

In its simplest form, the longest common substring problem is to find a longest substring common to two or multiple strings. Using (generalized) suffix trees, this problem can be solved in linear time and space. A first generalization is the k -common substring problem: Given m strings of total length n, for all k with 2≤k≤m simultaneously find a longest substring common to at least k of the strings. It is known that the k-common substring problem can also be solved in O(n) time (Hui in Proc. 3rd Annual Symposium on Combinatorial Pattern Matching, volume 644 of Lecture Notes in Computer Science, pp. 230–243, Springer, Berlin, 1992). A further generalization is the k -common repeated substring problem: Given m strings T ⁽¹⁾,T ⁽²⁾,…,T ^(m) of total length n and m positive integers x ₁,…,x _m , for all k with 1≤k≤m simultaneously find a longest string ω for which there are at least k strings \(T^{(i_{1})},T^{(i_{2})},\ldots,T^{(i_{k})}\) (1≤i ₁<i ₂<???<i _k ≤m) such that ω occurs at least \(x_{i_{j}}\) times in \(T^{(i_{j})}\) for each j with 1≤j≤k. (For x ₁=???=x _m =1, we have the k-common substring problem.) In this paper, we present the first O(n) time algorithm for the k-common repeated substring problem. Our solution is based on a new linear time algorithm for the k-common substring problem.     

Testing Convexity Properties of Tree Colorings

A coloring of a graph is convex if it induces a partition of the vertices into connected subgraphs. Besides being an interesting property from a theoretical point of view, tests for convexity have applications in various areas involving large graphs. We study the important subcase of testing for convexity in trees. This problem is linked, among other possible applications, with the study of phylogenetic trees, which are central in genetic research, and are used in linguistics and other areas. We give a 1-sided, non-adaptive, distribution-free ε-test for the convexity of tree colorings. The query complexity of our test is O(k/ε), where k is the number of colors, and the additional computational complexity is O(n). On the other hand, we prove a lower bound of \(\Omega(\sqrt{k/\epsilon})\) on the query complexity of tests for convexity in the standard model, which applies even for (unweighted) paths. We also consider whether the dependency on k can be reduced in some cases, and provide an alternative testing algorithm for the case of paths. Then we investigate a variant of convexity, namely quasi-convexity, in which all but one of the colors are required to induce connected components. For this problem we provide a 1-sided, non-adaptive ε-test with query complexity O(k/ε ²) and time complexity O(kn/ε). For both our convexity and quasi-convexity tests, we show that, assuming that a query takes constant time, the time complexity can be reduced to a constant independent of n if we allow a preprocessing stage of time O(n) and O(n ²), respectively. Finally, we show how to test for a variation of convexity and quasi-convexity where the maximum number of connectivity classes of each color is allowed to be a constant value other than 1.     

Mutually independent Hamiltonian cycles in dual-cubes

The hypercube family Q _n is one of the most well-known interconnection networks in parallel computers. With Q _n , dual-cube networks, denoted by DC _n , was introduced and shown to be a (n+1)-regular, vertex symmetric graph with some fault-tolerant Hamiltonian properties. In addition, DC _n ’s are shown to be superior to Q _n ’s in many aspects. In this article, we will prove that the n-dimensional dual-cube DC _n contains n+1 mutually independent Hamiltonian cycles for n≥2. More specifically, let v _i ∈V(DC _n ) for 0≤i≤|V(DC _n )|?1 and let \(\langle v_{0},v_{1},\ldots ,v_{|V(\mathit{DC}_{n})|-1},v_{0}\rangle\) be a Hamiltonian cycle of DC _n . We prove that DC _n contains n+1 Hamiltonian cycles of the form \(\langle v_{0},v_{1}^{k},\ldots,v_{|V(\mathit{DC}_{n})|-1}^{k},v_{0}\rangle\) for 0≤k≤n, in which v _i ^k ≠v _i ^k′ whenever k≠k′. The result is optimal since each vertex of DC _n has only n+1 neighbors.     

Tilings of nonorientable surfaces by Steiner triple systems

A Steiner triple system of order n (for short, STS(n)) is a system of three-element blocks (triples) of elements of an n-set such that each unordered pair of elements occurs in precisely one triple. Assign to each triple (i,j,k) ? STS(n) a topological triangle with vertices i, j, and k. Gluing together like sides of the triangles that correspond to a pair of disjoint STS(n) of a special form yields a black-and-white tiling of some closed surface. For each n ≡ 3 (mod 6) we prove that there exist nonisomorphic tilings of nonorientable surfaces by pairs of Steiner triple systems of order n. We also show that for half of the values n ≡ 1 (mod 6) there are nonisomorphic tilings of nonorientable closed surfaces.     

On Fixed Cost k-Flow Problems

In the Fixed Cost k-Flow problem, we are given a graph G = (V, E) with edge-capacities {u _e ∣e ∈ E} and edge-costs {c _e ∣e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = (A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ? A ∪ B of minimum size |S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an \(O(\sqrt {k\log k})\) approximation for this problem. We also show that we can compute a solution of optimum size with Ω(k/polylog(n)) paths, where n = |A| + |B|. In the Generalized-P2P problem we are given an undirected graph G = (V, E) with edge-costs and integer charges {b _v : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design [11]. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log^3+?? n approximation scheme for it using Group Steiner Tree techniques.     

Ambiguity and Communication

The ambiguity of a nondeterministic finite automaton (NFA) N for input size n is the maximal number of accepting computations of N for inputs of size n. For every natural number k we construct a family \((L_{r}^{k}\;|\;r\in \mathbb{N})\) of languages which can be recognized by NFA’s with size k?poly(r) and ambiguity O(n ^k ), but \(L_{r}^{k}\) has only NFA’s with size exponential in r, if ambiguity o(n ^k ) is required. In particular, a hierarchy for polynomial ambiguity is obtained, solving a long standing open problem (Ravikumar and Ibarra, SIAM J. Comput. 19:1263–1282, 1989, Leung, SIAM J. Comput. 27:1073–1082, 1998).     

Locally adaptive <Emphasis Type="Italic">k</Emphasis> parameter selection for nearest neighbor classifier: one nearest cluster

The k nearest neighbors (k-NN) classification technique has a worldly wide fame due to its simplicity, effectiveness, and robustness. As a lazy learner, k-NN is a versatile algorithm and is used in many fields. In this classifier, the k parameter is generally chosen by the user, and the optimal k value is found by experiments. The chosen constant k value is used during the whole classification phase. The same k value used for each test sample can decrease the overall prediction performance. The optimal k value for each test sample should vary from others in order to have more accurate predictions. In this study, a dynamic k value selection method for each instance is proposed. This improved classification method employs a simple clustering procedure. In the experiments, more accurate results are found. The reasons of success have also been understood and presented.     

On partitions of an <Emphasis Type="Italic">n</Emphasis>-cube into nonequivalent perfect codes

We prove that for all n = 2^k ? 1, k ≥ 5, there exists a partition of the set of all binary vectors of length n into pairwise nonequivalent perfect binary codes of length n with distance 3.     

On the Advice Complexity of the k-server Problem Under Sparse Metrics

We consider the k-Server problem under the advice model of computation when the underlying metric space is sparse. On one side, we introduce Θ(1)-competitive algorithms for a wide range of sparse graphs. These algorithms require advice of (almost) linear size. We show that for graphs of size N and treewidth α, there is an online algorithm that receives O (n(log α + log log N))^* bits of advice and optimally serves any sequence of length n. We also prove that if a graph admits a system of μ collective tree (q, r)-spanners, then there is a (q + r)-competitive algorithm which requires O (n(log μ + log log N)) bits of advice. Among other results, this gives a 3-competitive algorithm for planar graphs, when provided with O (n log log N) bits of advice. On the other side, we prove that advice of size Ω(n) is required to obtain a 1-competitive algorithm for sequences of length n even for the 2-server problem on a path metric of size N ≥ 3. Through another lower bound argument, we show that at least \(\frac {n}{2}(\log \alpha - 1.22)\) bits of advice is required to obtain an optimal solution for metric spaces of treewidth α, where 4 ≤ α < 2k.     

The Outer-connected Domination Number of Sierpiński-like Graphs

An outer-connected dominating set in a graph G = (V, E) is a set of vertices D ? V satisfying the condition that, for each vertex v ? D, vertex v is adjacent to some vertex in D and the subgraph induced by V?D is connected. The outer-connected dominating set problem is to find an outer-connected dominating set with the minimum number of vertices which is denoted by \(\tilde {\gamma }_{c}(G)\). In this paper, we determine \(\tilde {\gamma }_{c}(S(n,k))\), \(\tilde {\gamma }_{c}(S^{+}(n,k))\), \(\tilde {\gamma }_{c}(S^{++}(n,k))\), and \(\tilde {\gamma }_{c}(S_{n})\), where S(n, k), S ⁺(n, k), S ⁺⁺(n, k), and S _n are Sierpi\(\acute {\mathrm {n}}\)ski-like graphs.     

Chromatic Numbers of Distance Graphs with Several Forbidden Distances and without Cliques of a Given Size

We consider distance graphs with k forbidden distances in an n-dimensional space with the p-norm that do not contain cliques of a fixed size. Using a probabilistic construction, we present graphs of this kind with chromatic number at least (Bk) ^Cn , where B and C are constants.     

On fractional faces of the metric polytope

The integrality recognition problem is considered on a sequence M _{n, k} of nested relaxations of a Boolean quadric polytope, including the rooted semimetric M _n and metric M _{n, 3} polytopes. The constraints of the metric polytope cut off all faces of the rooted semimetric polytope that contain only fractional vertices. This makes it possible to solve the integrality recognition problem on M _n in polynomial time. To solve the integrality recognition problem on the metric polytope, we consider the possibility of cutting off all fractional faces of M _{n, 3} by a certain relaxation M _{n, k} . The coordinates of points of the metric polytope are represented in homogeneous form as a three-dimensional block matrix. We show that in studying the question of cutting off the fractional faces of the metric polytope, it is sufficient to consider only constraints in the form of triangle inequalities.     

Star reduction among minimal length addition chains

An addition chain for a natural number n is a sequence \({1=a_0 < a_1 < \cdots < a_r=n}\) of numbers such that for each 0 < i ≤ r, a _i  = a _j  + a _k for some 0 ≤ k ≤ j < i. The minimal length of an addition chain for n is denoted by ?(n). If j = i ? 1, then step i is called a star step. We show that there is a minimal length addition chain for n such that the last four steps are stars. Then we conjecture that there is a minimal length addition chain for n such that the last \({\lfloor\frac{\ell(n)}{2}\rfloor}\)-steps are stars. We verify that the conjecture is true for all numbers up to 2¹⁸. An application of the result and the conjecture to generate a minimal length addition chain reduce the average CPU time by 23–29% and 38–58% respectively, and memory storage by 16–18% and 26–45% respectively for m-bit numbers with 14 ≤ m ≤ 22.     

On the Number of Edges of a Uniform Hypergraph with a Range of Allowed Intersections

We study the quantity p(n, k, t₁, t₂) equal to the maximum number of edges in a k-uniform hypergraph having the property that all cardinalities of pairwise intersections of edges lie in the interval [t₁, t₂]. We present previously known upper and lower bounds on this quantity and analyze their interrelations. We obtain new bounds on p(n, k, t₁, t₂) and consider their possible applications in combinatorial geometry problems. For some values of the parameters we explicitly evaluate the quantity in question. We also give a new bound on the size of a constant-weight error-correcting code.     

On the Construction of Transitive Codes

Application of some known methods of code construction (such as the Vasil'ev, Plotkin, and Mollard methods) to transitive codes satisfying certain auxiliary conditions yields infinite classes of large-length transitive codes, in particular, at least ?k/2?² nonequivalent perfect transitive codes of length n = 2 ^k ? 1, k > 4. A similar result is valid for extended perfect transitive codes.     

Using dynamic pixel value mapping method to construct visible and reversible image watermarking scheme

A reversible and visible image watermarking scheme extracts a visibly embedded binary watermark image and recovers the original cover image. This paper presents a reversible and visible image watermarking scheme that embeds visible watermarks into a part of the cover image, called the embedded region R, and embeds required binary strings into the whole image through the conventional difference-expansion method. The size of the embedded visible watermark is determined by the coefficient k; a large k value leads to a large embedded region for the visible watermark. The embedded region R is first segmented to non-overlapped k×k blocks, and each block is related to one bit of the watermark image. For those blocks that are related to the logo bits of the watermark image, these k×k blocks are adjusted by the proposed dynamic pixel value mapping method for highly visual detection. The binary bit string S, composed of the binary watermark image and LSB bits of the logo watermark bits’ corresponding k×k blocks, is embedded into the cover image using the conventional difference-expansion method. Experimental results show that the watermark is clearly embedded into the embedded region R and that the distortion of the reversible embedding is limited.     

Restricted (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-threshold quantum secret sharing scheme based on local distinguishability of orthogonal multiqudit entangled states

In this work, we study a restricted (k, n)-threshold access structure. According to this structure, we construct a group of orthogonal multipartite entangled states in d-dimensional system and investigate the distinguishability of these entangled states under restricted local operations and classical communication. Based on these properties, we propose a restricted (k, n)-threshold quantum secret sharing scheme (called LOCC-QSS scheme). The k cooperating players in the restricted threshold scheme come from all disjoint groups. In the proposed protocol, the participants distinguish these orthogonal states by the computational basis measurement and classical communication to reconstruct the original secret. Furthermore, we also analyze the security of our scheme in three primary quantum attacks and give a simple encoding method in order to better prevent the participant conspiracy attack.