Omer Berkman

SODA Conference 2000 Conference Paper

Efficient dynamic traitor tracing

• Omer Berkman
• Michal Parnas
• Jirí Sgall

SODA Conference 1994 Conference Paper

The Subtree Max Gap Problem with Application to Parallel String Covering

• Amir M. Ben-Amram
• Omer Berkman
• Costas S. Iliopoulos
• Kunsoo Park

FOCS Conference 1990 Conference Paper

Some Triply-Logarithmic Parallel Algorithms (Extended Abstract)

• Omer Berkman
• Joseph F. JáJá
• Sridhar Krishnamurthy
• Ramakrishna Thurimella
• Uzi Vishkin

It is established that several natural problems have triply logarithmic, or even faster, optimal parallel algorithms. These problems include: merging two sorted lists, where the values are drawn from a large, but restricted, domain on a CREW PRAM; finding all prefix minima, where the values are drawn from a restricted domain; and top-bottom global routing around a rectangle, a well-investigated problem in VLSI routing for which only highly involved serial algorithms were known. >

STOC Conference 1989 Conference Paper

Highly Parallelizable Problems (Extended Abstract)

• Omer Berkman
• Dany Breslauer
• Zvi Galil
• Baruch Schieber
• Uzi Vishkin

FOCS Conference 1989 Conference Paper

Recursive *-Tree Parallel Data-Structure (Extended Abstract)

• Omer Berkman
• Uzi Vishkin

The authors introduce a fundamentally novel parallel data structure, called recursive *-tree (star tree). For its definition, they use a generalization of this * functional and apply it to functions other than log. Using recursion in the spirit of the inverse-Akermann function, they derive recursive *-trees. The recursive *-tree data structure leads to a new design paradigm for parallel algorithms. The paradigm allows for unusually fast parallel computations that need only constant time, using an optimal number of processors under the assumption that a very small number of processors can write simultaneously, each into different bits of the same word. >