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.

more >>>

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 >>>