^April May – 2005 ^June

Consider the following simple technique for combating spam:

If I don't know you, and you want your e-mail to appear in my inbox, then you must attach to your message an easily verified "proof of computational effort", just for me and just for this message.

To apply this approach one needs to be able to come up with computational problems where solving them requires significant expenditure of resources while verifying a solution can be done easily. In this talk I will introduce this approach and concentrate on the choice of computational problems for which most of the work is in retrieving information from memory. In particular I will describe the connection to pebbling problems.

The talk is based on two papers:

Cynthia Dwork, Andrew Goldberg and Moni Naor: On Memory-Bound Functions for Fighting Spam.

Cynthia Dwork, Moni Naor and Hoeteck Wee: Pebbling and Proofs of Work

Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the `learning from parity with error' problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a _quantum_ algorithm for SVP and SIVP.

A main open question is whether this reduction can be made classical.

Using the main result, we obtain a public-key cryptosystem whose hardness is based on the worst-case quantum hardness of SVP and SIVP. Previous lattice-based public-key cryptosystems such as the one by Ajtai and Dwork were only based on unique-SVP, a special case of SVP. The new cryptosystem is much more efficient than previous cryptosystems: the public key is of size $\tilde{O}(n)$ and encrypting a message increases its size by $\tilde{O}(n)$ (in previous cryptosystems these values are $\tilde{O}(n^4)$ and $\tilde{O}(n^2)$, respectively).

Oded Regev is a senior lecturer in Tel Aviv University. He received his Ph.D. from Tel Aviv University in 2001, and was a postdoc at the Institute for Advanced Study, Princeton and U.C. Berkeley.

In this talk we examine the dissemination of information about resources in mobile peer-to-peer networks. In such networks, moving objects and sensors communicate with each other via short-range wireless transmission. The disseminated information represents spatial-temporal resources. Such a resource is available at a particular time and location, and is relevant to clients in the geographic vicinity, possibly for a limited period of time. Applications involving these types of networks and resources occur in transportation, battlefield and emergency response situations, and social networks.

We discuss the research issues involved in these applications. We also propose an opportunistic dissemination paradigm, in which a moving object exchanges resource information with encountered moving objects. We analyze several variants of this paradigm, and incentive economic models for collaboration. The subject is related to peer-to-peer networks, resource discovery in mobile ad hoc networks, epidemic replication and routing, and publish/subscribe literature. However, significant differences exist, and we will discuss them.

Biographical sketch:

Ouri Wolfson's main research interests are in database systems, distributed systems, transaction processing, and mobile/pervasive computing. He received his B.A. degree in mathematics, and his Ph.D. degree in computer science from Courant Institute of Mathematical Sciences, New York University. He is currently the Richard and Loan Hill Professor in the Department of Computer Science at the University of Illinois at Chicago, where he directs the Databases and Mobile Computing Laboratory, and the newly established Mobile Information Systems Research Center. He served as a consultant to Argonne National Laboratory, to the US Army Research Laboratories, to the Center of Excellence in Space Data and Information Sciences at NASA, and to the High Performance Database Research Center at Florida International University. He is also the founder of Mobitrac, a high-tech startup company specializing in infrastructure software for location based services and products. Before joining the University of Illinois he has been on the computer science faculty at the Technion and Columbia University, and he has been a Member of Technical Staff at Bell Laboratories.

Ouri Wolfson authored close to 120 publications, and holds two patents. He is a Fellow of the Association of Computing Machinery, an editor of the ACM/URSI/Baltzer Wireless Networks Journal, a Member of the ACM SIGMOD Digital Review Editorial Board and a guest editor of the ACM/Baltzer Journal on Special Topics in Mobile Networks. He received the best paper award for "Opportunistic Resource Exchange in Inter-vehicle Ad Hoc Networks", at the 2004 Mobile Data Management Conference. He is also the 2001 recipient of the UIC College of Engineering Faculty Research Award, and served as a Distinguished Lecturer for the Association of Computing Machinery during 2001-2003. He participated in numerous conferences (including ACM-SIGMOD, VLDB, PODS, ICDE, NGITS, ICDCS, MOBIDATA, DOOD, SSD, GIS, PDIS, CIKM), as a program committee member, session chairman, and panelist. Most recently he was the keynote speaker at the Second International Conference on Mobile Data Management (MDM 2001), the 2004 IEEE International Conference on Networking, Sensing and Control (ICNSC 2004), and The Second International Workshop On Databases, Information Systems and Peer-to-Peer Computing (DBISP2P 2004). He was the program committee co-chair of the Third International Conference on Mobile Data Management (MDM 2002), the Second ACM International Workshop on Mobile Commerce (2002), and the Sixth International Conference on Mobile Data Management (MDM 2005). His research has been funded at a level close to ten million dollars by the National Science Foundation, Air Force Office of Scientific Research, Defense Advanced Research Projects Agency, NATO, US Army, the New York State Science and Technology Foundation, Hughes Research Laboratories, and Informix Co.

The nervous system analyses sensory information and orchestrates motor commands.Many artificially engineered systems face similar challenges. Following the notion of cybernetics we strive to boost both scientific and technological research by exploring the differences between artificial control theory and the biological motor control.

The brain contains internal representation of our limbs and our external environment and can flexibly modify these internal mapping. With psychophysical experiments (that expose subjects to altered feedback or force perturbations) and computational modeling we try to explore the structure of this internal representation its capabilities and limitations.

In this talk I will review my previous studies and my current ongoing studies that employ tools from control theory (In particular bang-bang optimal control and adaptive control) and explore trajectory formation and representation of time, of delay and of rhythmic movements.

Finally I will discuss our future research plans to employ these models to extend our hands by direct brain interfaces and by the tele-presence technologies of the future.

Biosketch:

Amir Karniel received the B.Sc. degree (Cum Laude) in 1993, the M.Sc. degree in 1996, and the Ph.D. degree in 2000, all in Electrical Engineering from the Technion-Israel Institute of Technology, Haifa, Israel. He received the award for consistent distinguished instructor, the E. I. Jury award for excellent students in the area of systems theory, and the Wolf Scholarship award for excellent research students. For two years he had been a post doctoral fellow at the department of physiology, Northwestern University Medicl School.

Parts of his studies were performed at the Robotics Lab of the Rehabilitation Institute of Chicago. Dr. Karniel returned to the Faculty of Electrical Engineering on March 2002 and served as research associate and as the academic supervisor of the Physiological Signal Processing Laboratory. Since October 2003 he is with the Department of Biomedical Engineering at Ben-Gurion University of the Negev, Beer-Sheva, Israel. He established the Computational Motor Control Laboratory to study the brain using computational models as well as human machine interfacing techniques such as tracking systems and augmenter reality with haptics.

Dr. Kariel is the head of the organizing committee of the upcoming first international workshop on Computational Motor Control at the Negev, to be held on May 25, 2005 at Ben Gurion University of the Negev.

A distribution $X$ over binary strings of length $n$ is a $\delta$-source if every string has probability at most $2^{-\delta n}$. We give the following new explicit constructions (namely, poly(n)-time computable functions) of deterministic extractors, dispersers and related objects. All work for any fixed rate $\delta >0$. No previous explicit construction was known for either of these, for any $\delta<1/2$. The first two constitute major progress to very long-standing open problems.

1. (Bipartite Ramsey) $f_1: ({0,1}^n)2 \rightarrow {0,1}$, such that for any two independent $\delta$-sources $X_1, X_2$ we have $f_1(X_1,X_2) = {0,1}$. This implies a new explicit construction of $2N$-vertex bipartite graphs where no induced $N^{\delta}$ by $N^{\delta}$ subgraph is complete or empty.
2. (Multiple source extraction) $f_2: ({0,1}^n)3 \rightarrow {0,1}$, such that for any three independent $\delta$-sources $X_1,X_2,X_3$ we have that $f_2(X_1,X_2,X_3)$ is ($o(1)$-close to being) an unbiased random bit.
3. (Constant seed condenser) $f_3: {0,1}^n \rightarrow ({0,1}^m))^c$, such that for any $\delta$-source $X$, one of the $c$ output distributions $f_3(X)_i$, is a $0.9$-source over ${0,1}^m$. Here $c$ is a constant depending only on $\delta$.
4. (Subspace Ramsey) $f_4: {0,1}^n \rightarrow {0,1}$, such that for any affine subspace $X$ of dimension at least $\delta n$, $f_4(X)={0,1}$.

The constructions are quite involved and use as building blocks other new and known gadgets. But we can point out two important themes which recur in these constructions. One is that gadgets which were designed to work with independent inputs, sometimes perform well enough with correlated, high entropy inputs. The second is using the input to (introspectively) find high entropy regions within itself.

Joint work with Boaz Barak, Guy Kindler, Benny Sudakov and Avi Wigderson.

Bio:
My PhD is from Hebrew University, advisor: Avi Wigderson. The thesis is on "Explicit constructions of pseudorandom generators and extractors". During my PhD studies I stayed for two years at the IAS at Princeton. Following my PhD I did 3 years of Postdoc in the Weizmann Institute under Oded Goldreich and Moni Naor. I now have a faculty position at Haifa.

Detection of Regions of Interest (ROI) in still and video sequences is highly task dependent, and involves one of the fundamental problems in Computer Vision - should we use Top Down, context based methods, or Bottom up ones. We describe several methods for context free detection of ROIs, and demonstrate their applicability for face detection tasks.