Claudson F. Bornstein, Ami Litman, Bruce M. Maggs, Ramesh K. Sitaraman
wraparound. The former result is surprising, since it contradicts the prior "folklore " belief that the bisection width is n. We also show that every set of k nodes has at least k 2 log k...
Ami Litman, Shiri Moran-schein
Abstract This paper studies evenly distributed sets of natural numbers and their applications to schedulingin a distributed environment. Such sets, called smooth sets, have the property that their...
Ami Litman, Shiri Moran-schein
Abstract This paper studies evenly distributed sets of natural numbers and their applications to schedulingin a centralized environment. Such sets, called smooth sets, have the property that their...
Ami Litman, Shiri Moran-schein
Abstract This work studies evenly distributed sets of integers-- sets whose quantity within each intervalis proportional to the size of the interval, up to a bounded additive deviation. Namely, for!,...
Shimon Even, Ami Litman, Peter Winkler
We consider directed, strongly connected networks of identical finite-state automata, of bounded in- and out-degree but unknown topology and unbounded size n. Protocols which are quadratic or linear...
Optimal Conclusive Sets for Comparator Networks (2007)
Guy Even, Tamir Levi, Ami Litman
A set of input vectors S is conclusive if correct functionality for all input vectors is implied by correct functionality over vectors in S. We consider four functionalities of comparator networks:...
On centralized smooth scheduling (2005)
Ami Litman, Shiri Moran-schein
This paper studies evenly distributed sets of natural numbers and their applications to scheduling in a distributed environment. Such sets, called smooth sets, have the property that their quantity...
Roy Mader, Eby G. Friedman, Ami Litman, Ivan S. Kourtev
tbstract--This paper compares several methods for determining an optimal non-zero clock skew schedule for synchronous digital VLSI circuits. The optimality of a given dock skew schedule which...
Combinatorial Variability of Vapnik Chervonenkis Classes (1998)
We define embeddings between concept classes that are meant to reflect certain aspects of their combinatorial structure. Furthermore, we introduce a notion of universal concept classes-- classes into...
On the Bisection Width and Expansion of Butterfly Networks (1997)
Claudson Bornstein Ami, Ami Litman, Bruce M. Maggs, Ramesh K. Sitaraman, Tal Yatzkar
This paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. Previously it was known that the bisection width of an n-input butterfly with...
On the Bisection Width and Expansion of Butterfly Networks (1997)
Claudson F. Bornstein, Ami Litman, Bruce M. Maggs, Ramesh K. Sitaraman, Tal Yatzkar
This paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. We show that the bisection width of an n-input butterfly network is 2( p 2...
Monochromatic Paths and Triangulated Graphs (1995)
Shimon Even, Ami Litman, Arnold L. Rosenberg
This paper considers two properties of graphs, one geometrical and one topological, and shows that they are strongly related. Let G be a graph with four distinguished and distinct vertices, w 1 ; w 2...
Computing with Snakes in Directed Networks of Automata (1990)
Shimon Even, Ami Litman, Peter Winkler
We consider unidirectional, strongly connected networks of identical finite-state automata, of bounded in- and out-degree but unknown topology and unbounded size n. Protocols which are quadratic or...