Search

A plane tiling by the copies of a polyomino is called isohedral if every pair of copies in the tiling has a symmetry of the tiling that maps one copy to the other. We show that, for every [Formula: see text]-omino (i.e., polyomino consisting of [Formula: see text] cells), the number of non-equivalent isohedral tilings generated by 90 degree rotations, so called p4-tilings or quarter-turn tilings, is bounded by a constant (independent of [Formula: see text]). The proof relies on the analysis of the factorization of the boundary word of a polyomino. We also show an example of a polyomino that has three non-equivalent p4-tilings.

A multilinear polynomial p is said to sign-represent a Boolean function f : { − 1 , 1 } n → { − 1 , 1 } if f ( x ) = s g n ( p ( x ) ) for all x ∈ { − 1 , 1 } n . In this paper, we consider the length and weight of polynomials sign-representing Boolean functions of the form ⊕ k f , the XOR of k copies of f on disjoint sets of variables. Firstly, we show that for an infinite family of functions f, a naive construction does not yield a shortest polynomial sign-representing ⊕ k f . More precisely, we give a construction of polynomials sign-representing ⊕ k AND n whose length is strictly smaller than the k-th power of the minimum length of a polynomial sign-representing AND n , for every k ≥ 2 and n ≥ 2 except for k = n = 2 . Previously, such polynomials were known only for n = 2 (Sezener and Oztop, 2015). A similar result for the weight is also provided. Secondly, we introduce a parameter v f ⁎ of a Boolean function f and show that the k-th root of the minimum weight of a polynomial sign-representing ⊕ k f converges between v f ⁎ and ( v f ⁎ ) 2 as k goes to infinity.

An ordered biclique partition of the complete graph $K_n$ on $n$ vertices is a collection of bicliques (i.e., complete bipartite graphs) such that (i) every edge of $K_n$ is covered by at least one and at most two bicliques in the collection, and (ii) if an edge $e$ is covered by two bicliques then each endpoint of $e$ is in the first class in one of these bicliques and in the second class in other one. In this note, we give an explicit construction of such a collection of size $n^{1/2+o(1)}$, which improves the $O(n^{2/3})$ bound shown in the previous work [Disc. Appl. Math., 2014]. As the immediate consequences of this result, we show (i) a construction of $n \times n$ 0/1 matrices of rank $n^{1/2+o(1)}$ which have a fooling set of size $n$, i.e., the gap between rank and fooling set size can be at least almost quadratic, and (ii) an improved lower bound $(2-o(1)) \log N$ on the nondeterministic communication complexity of the clique vs. independent set problem, which matches the best known lower bound on the deterministic version of the problem shown by Kushilevitz, Linial and Ostrovsky [Combinatorica, 1999]., 8 pages; the version submitted to a journal

Secure sets and defensive alliances in graphs are studied. They are sets of vertices that are safe in some senses. In this paper, we first present a fixed-parameter algorithm for finding a small secure set, whose running time is much faster than the previously known one. We then present improved bound on the smallest sizes of defensive alliances and secure sets for hypercubes. These results settle some open problems paused recently.

An ordered biclique partition of the complete graph K n on n vertices is a collection of bicliques (i.e.,?complete bipartite graphs) such that (i) every edge of K n is covered by at least one and at most two bicliques in the collection, and (ii) if an edge e is covered by two bicliques then each endpoint of e is in the first class in one of these bicliques and in the second class in the other one. We show in this note that the minimum size of such a collection is O ( n 2 / 3 ) .This gives new results on two problems related to communication complexity. Namely, (i) a new separation between the size of a fooling set and the rank of a 0/1-matrix, and (ii) an improved lower bound on the nondeterministic communication complexity of the clique vs. independent set problem are given.

The average sensitivity of a Boolean function is the expectation, given a uniformly random input, of the number of input bits which when flipped change the output of the function. A k-CNF is a CNF in which every clause contains at most k literals. It has recently been shown by the author Amano (2011) [1] that the average sensitivity of a k-CNF is at most k. This bound is tight since the parity function on k variables has the average sensitivity k. In this paper, we consider the problem to determine the extremal formulas achieving this bound. We give a class of such formulas that contains a double exponential (in k) number of non-isomorphic ones. This class captures all formulas, with only one exception, that we have obtained so far. We also give the complete list for k=2 and 3 as well as several structural properties of such extremal formulas.

In this paper, we consider the following sliding puzzle called torus puzzle. In an m by n board, there are mn pieces numbered from 1 to mn. Initially, the pieces are placed in ascending order. Then they are scrambled by rotating the rows and columns without the player’s knowledge. The objective of the torus puzzle is to rearrange the pieces in ascending order by rotating the rows and columns. We provide a solution to this puzzle. In addition, we provide lower and upper bounds on the number of steps for solving the puzzle. Moreover, we consider a variant of the torus puzzle in which each piece is colored either black or white, and we present a hardness result for solving it.

The average sensitivity of a Boolean function is the expectation, given a uniformly random input, of the number of input bits which when flipped change the output of the function. A k-CNF is a CNF in which every clause contains at most k literals. It has recently been shown by the author [Amano, K., Tight Bounds on the Average Sensitivity of k-CNF, Theory of Computing, 7(4) (2011), 45–48] that the average sensitivity of a k-CNF is at most k. This bound is tight since the parity function on k variables has the average sensitivity k. In this paper, we consider the problem to determine the extremal formulas achieving this bound. We give a class of such formulas that contains a double exponential (in k) number of non-isomorphic ones. This class captures all formulas, with only one exception, that we have obtained so far. We also give the complete list for k = 2 and 3 as well as several structural properties of such extremal formulas.

In this note, we give an explicit construction of a minterm-transitive Boolean function with block sensitivity O(n^3^/^7). This removes a log-factor from the previously known bounds by Xiaoming Sun [Block sensitivity of weakly symmetric functions, Theoret. Comput. Sci. 384 (1) (2007) 87-91] and by Andrew Drucker [Block sensitivity of minterm-transitive functions, Theoret. Comput. Sci. 412 (41) (2011) 5796-5801]. Due to the matching lower bound by Drucker, it is shown that the minimum achievable block sensitivity for non-constant minterm-transitive function is @Q(n^3^/^7).

The average sensitivity of a Boolean function is the expectation, given a uniformly random input, of the number of input bits which when flipped change the output of the function. Answering a question by O'Donnell, we show that every Boolean function represented by a k-CNF (or a k-DNF) has average sensitivity at most k. This bound is tight since the parity function on k variables has average sensitivity k.

For an arbitrary set B of Boolean functions satisfying a certain condition, we give a general method of constructing a class CB of read-once Boolean formulas over the basis B that has the following property: For any F in CB, F can be transformed to an optimal formula (i.e., a simplest formula over the standard basis {AND, OR, NOT}) by replacing each occurrence of a basis function h ∈ B in F with an optimal formula for h. For a particular set of basis functions B* = {AND, OR, NOT, XOR, MUX}, we give a canonical form representation for CB* so that the set of canonical form formulas consists of only NPN-representatives in CB*.

We show that the middle bit of the multiplication of two n-bit integers can be computed by an ordered binary decision diagram (OBDD) of size less than 2.8.2^6^n^/^5. This improves the previously known upper bound of (73).2^4^n^/^3 by Woelfel (New Bounds on the OBDD-size of integer multiplication via Universal Hashing, J. Comput. System Sci. 71(4) (2005) 520-534). The experimental results suggest that our exponent of 6n/5 is optimal or at least very close to optimal. A general upper bound of O(2^3^n^/^2) on the OBDD size of each output bit of the multiplication is also presented.