Author name cluster

Shlomo Hoory

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

TCS Journal 2005 Journal Article

Computing unsatisfiable k -SAT instances with few occurrences per variable

Shlomo Hoory
Stefan Szeider

( k, s ) -SAT is the propositional satisfiability problem restricted to instances where each clause has exactly k distinct literals and every variable occurs at most s times. It is known that there exists an exponential function f such that for s ⩽ f ( k ) all ( k, s ) -SAT instances are satisfiable, but ( k, f ( k ) + 1 ) -SAT is already NP-complete ( k ⩾ 3 ). Exact values of f are only known for k = 3 and 4, and it is open whether f is computable. We introduce a computable function f 1 which bounds f from above and determine the values of f 1 by means of a calculus of integer sequences. This new approach enables us to improve the best known upper bounds for f ( k ), generalizing the known constructions for unsatisfiable ( k, s ) -SAT instances for small k.

Details DOI

TCS Journal 2005 Journal Article

Simple permutations mix well

Shlomo Hoory
Avner Magen
Steven Myers
Charles Rackoff

We study the random composition of a small family of O ( n 3 ) simple permutations on { 0, 1 } n. Specifically, we ask what is the number of compositions needed to achieve a permutation that is close to k -wise independent. We improve on a result of Gowers [An almost m -wise independent random permutation of the cube, Combin. Probab. Comput. 5(2) (1996) 119–130] and show that up to a polylogarithmic factor, n 3 k 3 compositions of random permutations from this family suffice. We further show that the result applies to the stronger notion of k -wise independence against adaptive adversaries. This question is essentially about the rapid mixing of the random walk on a certain graph, and we approach it using a new technique to construct canonical paths. We also show that if we are willing to use a much larger family of simple permutations then we can guarantee closeness to k -wise independence with fewer compositions and fewer random bits.

Details DOI

SAT Conference 2004 Conference Paper

Computing Unsatisfiable k-SAT Instances with Few Occurrences per Variable

Shlomo Hoory
Stefan Szeider

(k, s)-SAT is the propositional satisfiability problem restricted to instances where each clause has exactly k distinct literals and every variable occurs at most s times. It is known that there exists an exponential function f such that for s ≤ f (k) all (k, s)-SAT instances are satisfiable, but (k, f (k) + 1)-SAT is already NP-complete (k ≥ 3). Exact values of f are only known for k = 3 and k = 4, and it is open whether f is computable. We introduce a computable function f1 which bounds f from above and determine the values of f1 by means of a calculus of integer sequences. This new approach enables us to improve the best known upper bounds for f (k), generalizing the known constructions for unsatisfiable (k, s)-SAT instances for small k.

Details

FOCS Conference 2003 Conference Paper

Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua

Joshua Buresh-Oppenheim
Nicola Galesi
Shlomo Hoory
Avner Magen
Toniann Pitassi

We present a new method for proving rank lower bounds for Cutting Planes (CP) and several procedures based on lifting due to Lovasz and Schrijver (LS), when viewed as proof systems for unsatisfiability. We apply this method to obtain the following new results: first, we prove near-optimal rank bounds for Cutting Planes and Lovasz-Schrijver proofs for several prominent unsatisfiable CNF examples, including random kCNF formulas and the Tseitin graph formulas. It follows from these lower bounds that a linear number of rounds of CP or LS procedures when applied to relaxations of integer linear programs is not sufficient for reducing the integrality gap. Secondly, we give unsatisfiable examples that have constant rank CP and LS proofs but that require linear rank resolution proofs. Thirdly, we give examples where the CP rank is O(log n) but the LS rank is linear. Finally, we address the question of size versus rank: we show that, for both proof systems, rank does not accurately reflect proof size. Specifically, there are examples with polynomial-size CP/LS proofs, but requiring linear rank.

Details