Shlomo Hoory

most citedSimple Permutations Mix Even Better

6 citations · 7 across the 3 of their papers we have counts for

collaborators

3 papers

math.CO2004★ 1 cited

Families of unsatisfiable k-CNF formulas with few occurrences per variable

Shlomo Hoory, Stefan Szeider

(k,s)-SAT is the satisfiability problem restricted to instances where each clause has exactly k literals and every variable occurs at most s times. It is known that there exists a…

math.CO2004★ 6 cited

Simple Permutations Mix Even Better

Shlomo Hoory, Alex Brodsky

We study the random composition of a small family of O(n^3) simple permutations on {0,1}^n. Specifically we ask how many randomly selected simple permutations need be composed to y…

math.CO2004

A counterexample to a conjecture of Björner and Lovász on the $χ$ -coloring complex

Shlomo Hoory, Nathan Linial

Associated with every graph $G$ of chromatic number $χ$ is another graph $G^{'}$ . The vertex set of $G^{'}$ consists of all $χ$ -colorings of $G$ , and two $χ$ -colorings are adjacent when…

Families of unsatisfiable k-CNF formulas with few occurrences per variable

Simple Permutations Mix Even Better

A counterexample to a conjecture of Björner and Lovász on the χ-coloring complex

A counterexample to a conjecture of Björner and Lovász on the $χ$ -coloring complex