Author name cluster

Gene Itkis

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.

3 papers

2 author rows

TCS Journal 1998 Journal Article

On mixed connectivity certificates

Shimon Even
Gene Itkis
Sergio Rajsbaum

Vertex and edge connectivity are special cases of mixed connectivity, in which all edges and a specified set of vertices play a similar role. Certificates of k-connectivity for a graph are obtained by removing a subset of its edges, while preserving its connectivity up to k. We unify the previous work on connectivity certificates and extend it to handle mixed connectivity and multigraphs. Our treatment contributes a new insight of the pertinent structures, yielding more general results and simpler proofs. Also, we present the first communicationoptimal distributed algorithm for finding mixed connectivity certificates.

Details DOI

FOCS Conference 1994 Conference Paper

Fast and Lean Self-Stabilizing Asynchronous Protocols

Gene Itkis
Leonid A. Levin

We consider asynchronous general topology dynamic networks of identical nameless nodes with worst-case transient faults. Starting from any faulty configuration, our protocols self-stabilize any computation in time polynomial in the (unknown) network diameter. This version sacrifices some diversity of tasks and efficiency for simplicity and clarity of details. Appendix gives more efficient procedures in less detail. >

Details

FOCS Conference 1989 Conference Paper

Power of Fast VLSI Models Is Insensitive to Wires' Thinness

Gene Itkis
Leonid A. Levin

VLSI f-models which allow the switching time to decrease to f(D) when the length of all wires is restricted by D are called 'fast' if the decrease is slightly superlinear. The fast models are so strong and robust that their computational power cannot be increased by and combination of the following: (1) making zero the width of each wire of length d, except for its log d segment, thus eliminating layout and area considerations; (2) allowing wires to transmit log d bits simultaneously; (3) making the switching time f(d) of each node depend only on the length d of its own input wires, thus enabling small subcircuits to run faster; (4) changing f while preserving Sigma /sub k/ 1/f(k); (5) enabling the nodes to change connections arbitrarily in the run time. The authors construct a kind of operating system link server (linx, for short) that simulates all these powers online. The condition of superlinearity cannot be weakened. >

Details