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 >>>
We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as (3,3)-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting ... more >>>
We investigate the space complexity of refuting 3-CNFs in Resolution and algebraic systems. No lower bound for refuting any family of 3-CNFs was previously known for the total space in resolution or for the monomial space in algebraic systems. We prove that every Polynomial Calculus with Resolution refutation of a ... more >>>
