2. Communication complexity and Secure Function Evaluation Kobbi Nissim A secure function evaluation protocol allows two parties to jointly compute a function f(x,y) of their inputs in a manner not leaking more information than necessary. A major result in this field is: "any function f that can be computed using polynomial resources can be computed securely using polynomial resources" (where `resources' refers to communication and computation). This result follows by a general transformation from any Boolean circuit for f to a secure protocol that evaluates f. We suggest new methodologies for the design of efficient secure protocols that differ with respect to their underlying computational models. One methodology utilizes the communication complexity tree (or branching program) representation of f. We start with an efficient (insecure) protocol for f and transform it into a secure protocol in a communication preserving manner. The second methodology uses a circuit computing f, enhanced with look-up tables. It is possible to simulate any RAM machine in this model with polylogarithmic blowup. Hence it is possible to start with a computation of $f$ on a RAM machine and transform it into a secure protocol. There are many applications of these new methodologies resulting n protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the "millionaires problem", where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation. The talk will focus on the computational models underlying our results, and on some of the open questions. Joint work with Moni Naor.
3. Speaker: Carl Pomerance, Bell Labs - Lucent Technologies Title: Carmichael's Function Abstract: Carmichael's function of $n$ is the order of the largest cyclic subgroup of the multiplicative group of integers modulo $n$. What could be simpler? Actually, a lot could! Related to factoring, primality testing, Artin's conjecture, and Euler's function, there is still much that we don't know, and in some of the problems it is even hard to find the right conjecture.
4. Venkatesh Srinivasan, DIMACS/IAS On the advantage over a random assignment We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the "random assignment" algorithm. Since the random assignment algorithm is known to give the best approximation algorithm for many optimization problems, we believe that this measure is fundamentally interesting. We study this measure for the optimization problem, Max-Lin-2, in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2. The main ideas we use in our results are from Fourier analysis and derandomization. We will also mention some algorithmic applications of our results for Max-Lin-2. This is joint work with Johan Hastad.
5. Mario Szegedy, Rutgers University Computing Boolean Functions from Multiple Faulty Copies of Input Bits Abstract. Suppose, we want to compute a Boolean function f, but instead of receiving the input, we only get some epsilon-faulty copies of each input bit. A typical solution in this case is to take the majority value of the faulty bits for each individual input bit and apply f on the majority values. We show that if f:{0,1}^{n} -> {0,1} and epsilon are known, the best construction function, F, is often not the trivial. In particular, in many cases the best F cannot be written as a composition of some functions with f, and in addition it is better to use a randomized F than a deterministic one. Our investigations have lead to a new result about the Static Noisy Decision tree complexity, introduced by Reischuk at. al. We fully characterize this complexity measure using a lemma that gives a necessary and sufficient condition for the value of a Boolean function to remain constant under independent random changes of its input bits. This lemma may be interesting on its own right.
6.
TITLE:
Informational Complexity and the Direct Sum Problem
for Simultaneous Message Complexity
AUTHORS:
Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Yao
SPEAKER:
Anthony Wirth
ABSTRACT:
Given $m$ copies of the same problem, does it take $m$ times
the amount of resources to solve these $m$ problems? This is the direct
sum problem, a fundamental question that has been studied in many
computational models. We study this question in the simultaneous message
(SM) model of communication introduced by Yao.
The equality problem for $n$-bit strings is well known to have SM
complexity $\Theta(\sqrt n)$. We prove that solving $m$ copies of the
problem has complexity $\Omega(m\sqrt n)$; the best lower bound provable
using previously known techniques is $\Omega(\sqrt{mn})$. We also prove
similar lower bounds on certain Boolean combinations of multiple copies
of the equality function. These results can be generalized to a broader
class of functions.
We introduce a new notion of {\em informational complexity} which is
related to SM complexity and has nice direct sum properties. This notion
is used as a tool to prove the above results; it appears to be quite
powerful and may be of independent interest.
KEYWORDS:
Communication Complexity, Direct Sum Problem,
Simultaneous Message Complexity, Probabilistic Method
Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on October 8, 2001.