bluma@TECHSEL.BITNET (Bluma Roth) (01/18/90)
Here is the final program, including revised titles and abstracts
for the SEMINAR ARTZI. It will take place, as usual, in the Schriver
Building (Math Dept), Tel Aviv University on Friday, Jan 19.
9:30 Uri feige, Weizmann
10:15 Amos Israeli, Technion
11:00 Break
11:30 Mario Szegedy, Hebrew U.
12:15 Adi Shamir, Weizmann
Here are the details:
Speaker: Uri Feige, Weizmann Institute
Title: Sorting With Noisy Comparisons
Consider comparison based algorithms for sorting, where each
comparison independently has probability 1/3 of giving the wrong
answer. Sorting with confidence 1 - 1/poly(n) can be achieved in
O(n log^2(n)) noisy comparisons, simply by repeating each comparison
O(log n) times and taking a majority vote. But can one do better?
In this talk, we fully characterize the "Noisy Comparison Complexity"
of sorting, merging, element distinctness, finding the maximum and
finding the median.
Joint work with David Peleg, Prabhakar Raghavan and Eli Upfal.
Speaker: Amos Israeli, Dept. of Electrical Engineering, Technion
Title: Token Management Schemes and Random Walks Yield
Self Stabilizing Mutual Exclusion
Abstract:
A self-stabilizing system is a system which starting from
any ARBITRARY configuration reaches a LEGAL
configuration by itself, without any kind of an outside
intervention. Hence a self-stabilizing system
accommodates any possible initial configuration.
This fact contributes most of the extra difficulty
of devising self-stabilizing systems. On the other hand, the same
fact makes self-stabilizing systems so appealing as no initialization
of the system is required.
In this work we present a novel modular method for constructing
uniform self stabilizing mutual exclusion (or in short UMESS)
protocols is presented. The viability of the method is
demonstrated by constructing for the first time a randomized UMESS
protocol for any arbitrary graph and another one for dynamic rings.
The correctness and complexity of both protocols
will be discussed. The analysis of the new protocols involves
the introduction of a new kind of single player token games
which are of an independent interest.
(Joint work with Marc Jalfon, Dept. of Computer Science Technion)
Speaker: Mario Szegedy, Hebrew University
Title: Functions with bounded symmetric communication complexity
The branch of circuit complexity theory most studied in the recent past is
the theory of circuits with bounded depth. Ajtai and independently
Furst, Saxe and Sipser were the first ones who
gave a superpolynomial lower bound on the size of bounded depth
circuits that compute the parity function (or the majority function).
Later by improving the method of Razborov, Smolensky
proved that bounded depth circuits with AND, OR and MODm gates must
have exponential size if they compute the majority function assuming
m is a prime power.
The difference between m being a prime power or an arbitrary
natural number may seem insignificant, but as a number of
attempts show the behavior of circuits with
MODm gates for a composite number m is much less understood.
We speculate that the reason why circuits with such gates may be
unable to compute the majority function is the poor
ability of the gates to collect the data necessary
for the computation.
We consider Boolean functions which have bounded symmetric
communication complexity, i.e. bounded communication complexity
under all partitions of the input. We give an explicit characterization
of these classes of functions by showing that they can be represented in a
natural way by commutative semigroups of bounded size.
As a consequence we deduce that unbounded fanin circuits
with gates with bounded symmetric communication complexity
can be simulated by circuits with AND, OR and MODm gates
for bounded m, with only linear increase in size and depth.
This shows the robustness of the concept of bouned depth, poly
size circuits with such gates suggesting a possible new
approach to lower bounds for such circuits.
Speaker: Adi Shamir, Weizmann Institute
Title: IP = PSPACE
Abstract: The class IP of languages which have efficient interactive
proofs of membership was introduced by Goldwasser, Micali and Rackoff
and independently by Babai. Goldreich, Micali and Wigderson showed
that IP contains some languages beleived not to be in NP.
Very recently, Fortnow, Karloff, Lund and Nisan showed that IP
contained the polynomial hierarchy, but its
exact characterization remained open.
In this talk we settle this question by showing that the proofs which
can be interactively verified in polynomial time are exactly those
proofs which can be generated in polynomial space.