We conjecture that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2$, there exists a second perfect matching $M'$
such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove this conjecture in the case where there are
two dimensions ...
more >>>
It has been shown that for every perfect matching $M$ of the $d$-dimensional
$n$-vertex hypercube, $d\geq 2, n=2^d$, there exists a second perfect matching
$M'$ such that the union of $M$ and $M'$ forms a Hamiltonian circuit of the
$d$-dimensional hypercube. We prove a generalization of a special case of ...
more >>>
Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a $k$-transitive-closure-spanner ($k$-TC-spanner) of $G$ is a directed graph $H = (V, E_H)$ that has (1) the same transitive-closure as $G$ and (2) diameter at most $k$. Transitive-closure spanners were introduced in \cite{tc-spanners-soda} as a common abstraction ... more >>>
We study the problem of monotonicity testing over the hypercube. As
previously observed in several works, a positive answer to a natural question about routing
properties of the hypercube network would imply the existence of efficient
monotonicity testers. In particular, if any $\ell$ disjoint source-sink pairs
on the directed hypercube ...
more >>>
A Boolean function is called vertex-transitive, if the partition of the Boolean cube into the preimage of 0 and the preimage of 1 is invariant under a vertex-transitive group of isometric transformations of the Boolean cube. Several constructions of vertex-transitive functions and some of their properties are presented.
Rounding has proven to be a fundamental tool in theoretical computer science. By observing that rounding and partitioning of $\mathbb{R}^d$ are equivalent, we introduce the following natural partition problem which we call the secluded hypercube partition problem: Given $k\in\mathbb{N}$ (ideally small) and $\epsilon>0$ (ideally large), is there a partition of ... more >>>
