אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

I will describe an O(n) time algorithmic version of Szemerdi's regularity lemma. Unlike all the previous approaches for this problem, which proved the lemma "algorithmically", and only guaranteed to find partitions of tower-size, our algorithm will find a small regular partition in the graph in the case that one exists. The algorithm can be extended to an O(n) time algorithmic version of the hypergraph regularity lemma for k-uniform hypergraphs, improving over the previous O(n^{2k-1}) ...
[ לנוסח המלא ]

We present a new method for segmenting closed curves or surfaces from a single point. Our work builds on a variant of the Fast Marching algorithm and an implicit approach which solves a transport equation. The goal is to define the curve as a series of minimal paths linking successive keypoints. First, an initial point on the desired boundary is chosen by the user. Next, new keypoints are detected automatically using a front propagation approach. Since the desired object has a closed boundary, a...
[ לנוסח המלא ]

Development of technologies for agriculture is very complex. The products (fruits, vegetables, flowers, livestock etc) are non-uniform and susceptible, the sceneries (illumination, topography, geometry etc) are complex and vary with time, and the low cost of the products is a limiting factor to the cost effectiveness of the technology. When the technologies deal with live fish, the constraints, requirements and limitations are even more acute due to two main reasons: underwater conditi...
[ לנוסח המלא ]

Rotation minimizing frames are useful for various applications in geometric modeling and computer graphics. For instance, the sweeping of one (cross-section) curve along the another one (spine curve) is well-known technique of surface construction in 3D shape modeling. In many applications, namely in the construction of canal surfaces, the minimal twist of the cross- section curve along the spine curve is required. For a general spine curve, the computation of the exact rotation minimizing...
[ לנוסח המלא ]

Suppose you are a user with a weak computational device connected to a network, e.g. a cell phone, and you need to perform a computation beyond your abilities. A natural solution is for you to *delegate* the expensive computation to a stronger computational device on the same network, say a server. The problem is that you may not trust the answer of this server: it may be unreliable or malicious. Can the server give you the output of the computation and *prove* to you that the output is c...
[ לנוסח המלא ]

Non-parametric approaches to object recognition have received limited attention in the Computer Vision community due to the high dimensionality of visual data. With the advent of the Internet, billions of images are now freely available online and constitute a dense sampling of the visual world. We explore this world with the aid of a large dataset of 108 images collected from the Internet, using a variety of non-parametric methods. Motivated by psychophysical results showing the remarkable tole...
[ לנוסח המלא ]

We study the problem of testing an expert who is required to submit forecasts that have a learnable parametric representations. The class of stochastic processes with such representations, introduced by Jackson, Kalai and Smorodinsky (1999), include exchangeable and Markov process as special cases, and encompasses all processes used in Bayesian statistics. We define a simple test that screens experts whose forecasts belong to this class. The test stipulates an initial phase during which...
[ לנוסח המלא ]

The digital photography revolution has greatly facilitated the way in which we take and share pictures. However, it has mostly relied on a rigid imaging model inherited from traditional photography. Computational photography goes one step further and exploits digital technology to enable arbitrary computation between the light array and the final image or video. Such computation can overcome limitations of the imaging hardware and enable new applications. It can also enable new imaging s...
[ לנוסח המלא ]

Origami (or paper folding) is an ancient art, focused on the creation of figures by applying a series of folds on a paper, without cutting the paper or gluing it. Though Origami is known for more than a thousand years, the past 60 years have seen a renaissance in this art and an acceleration of its evolution, which might be realized both in the amount of published designs and in the increasing complexity of the models. The main reason for this evolution is the increasing interest of mathem...
[ לנוסח המלא ]

In many application areas, complex data sets are often represented by some metric space and metric embedding is used to provide a more structured representation of the data. In many of these applications much greater emphasis is put on the preserving the local structure of the original space than on maintaining its complete structure. In this paper we initiate the study of local embeddings of metric spaces and provide embeddings with distortion depending solely on the local structure of ...
[ לנוסח המלא ]

We describe a spectral graph algorithm for reconstructing the three-dimensional structure of molecules from their Cryo-EM images taken at random unknown orientations. The key idea of the algorithm is designing a sparse operator defined on the projection data, whose eigenvectors reveal the orientation of each projection. Such an operator is constructed by utilizing the geometry induced on Fourier space by the projection-slice theorem. The presented algorithm is direct (as opposed to iterative ref...
[ לנוסח המלא ]

I was introduced into 3D modeling as an artist back in 1993 using Amiga 4000a and a software name "Real-3d". The modeling tools I had were of B-spline type. The following year I was modeling with Alias Power Animator and later to MAYA which offers tools for NURBS, Polygons, and Sub-D. Using those tools I created many complex modeling works of the human body and organic objects as well as still objects. Among my works were the character of Pillsbury Doughboy and Bruce willis in NU...
[ לנוסח המלא ]

Multi-prover games have played a tremendous role in theoretical computer science over the last two decades. A lot of research effort went into determining how hard it is to approximate the value of such games, culminating in the celebrated PCP Theorem. When considering multi-prover games in the quantum world, the laws of quantum mechanics allow for a fascinating new effect: namely, the provers can share an arbitrary entangled state, on which they may perform any local measurements they lik...
[ לנוסח המלא ]

Effective resizing of images should not only use geometric constraints, but consider the image content as well. We present a simple image operator called seam carving that supports content-aware image resizing for both reduction and expansion. A seam is an optimal 8-connected path of pixels on a single image from top to bottom, or left to right, where optimality is defined by an image energy function. By repeatedly carving out or inserting seams in one direction we can change the aspect ratio o...
[ לנוסח המלא ]

We give an explicit construction of pseudorandom generators against low degree polynomials over finite fields. We show that the sum of 2^d small-biased generators with error epsilon^{2^{O(d)} is a pseudorandom generator against degree d polynomials with error epsilon. This gives a generator with seed length 2^O(d)*.log{(n/epsilon)}. Our construction follows the recent breakthrough result of Bogadnov and Viola \cite{BV}. Their work shows that the sum of $d$ small-biased generators is a ps...
[ לנוסח המלא ]

Data discretization is defined as a process of converting continuous data attribute values into a finite set of intervals with minimal loss of information. In this talk, we prove that discretization methods based on informational theoretical complexity and the methods based on statistical measures of data dependency are asymptotically equivalent. Furthermore, we define a notion of generalized entropy and prove that discretization methods based on MDLP, Gini Index, AIC, BIC, Pearson's X...
[ לנוסח המלא ]

Object tracking is one of the basic and difficult aspects of computer vision. It is generally a prerequisite for other computer vision tasks such as object recognition, as well as a goal by itself in applications such as video surveillance. We address the problem of visual tracking in a general context using two approaches. Our first approach is the combination of multiple trackers that use different features and thus have different failure modes. We propose a general framework for combining...
[ לנוסח המלא ]

Effective resizing of images should not only use geometric constraints, but consider the image content as well. We present a simple image operator called seam carving that supports content-aware image resizing for both reduction and expansion. A seam is an optimal 8-connected path of pixels on a single image from top to bottom, or left to right, where optimality is defined by an image energy function. By repeatedly carving out or inserting seams in one direction we can change the aspect r...
[ לנוסח המלא ]

In 1998, Impagliazzo and Wigderson proved a hardness vs. randomness tradeoff for BPP in the /uniform setting/, which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions by Trevisan and Vadhan (in a slightly weaker setting). In 2003, Gutfreund, Shaltiel and Ta-Shma proved a uniform hardness vs. randomness tradeoff for AM, but that result only worked on the "high-end" of possible hardness assumptions. In this work, we give uniform hardness...
[ לנוסח המלא ]

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme due to Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). As a corollary, we derive similar tight lower bounds for several other cr...
[ לנוסח המלא ]

The image of a curved, specular (mirror-like) surface is a distorted reflection of the environment. Although the recovery of such specular shape from its image appears futile without some knowledge of the environment, the goal of this work is to develop a theoretical and practical framework for solving this shape inference problem when the environment is completely unknown. We show that although this general problem is severely ill-posed, allowing relative object-environment motion induces a den...
[ לנוסח המלא ]

The number of k-vertex colorings of a graph is a polynomial in k, the chromatic polynomial. Many other graph invariants (Tutte polynomial, matching polynomial, interlace polynomial, cover polynomial) are also polynomials (possibly in several variables). We show that this is no accident. The speaker introduced the notion of graph polynomials definable in Monadic Second Order Logic, and showed that the Tutte polynomial and its generalization, the matching polynomial, the cover polynomial and th...
[ לנוסח המלא ]

Traditional image and video processing algorithms are centralized. They rely on an implementation on a large server for efficient processing. However, with the emergence of large camera networks, we must design distributed algorithms that can scale with the size of the network and number of targets. In this talk, we present a general methodology to the design of distributed image and video processing systems. The premise of our approach to distributed processing is the graphic...
[ לנוסח המלא ]

Cross-modal analysis offers information beyond that extracted from individual modalities. Consider a camcorder having a single microphone in a cocktail-party: it captures several moving visual objects which emit sounds. A task for audio-visual analysis is to identify the number of independent audio-associated visual objects (AVOs), pinpoint the AVOs' spatial locations in the video and isolate each corresponding audio component. Part of these problems were considered by prior studies, which were ...
[ לנוסח המלא ]

We study the computational complexity and effectiveness of a concept we term "N-hub Shortest-Path Routing" in IP networks. N-hub Shortest-Path Routing allows the ingress node of a routing domain to determine up to N intermediate nodes ("hubs") through which a packet will pass before reaching its final destination. This facilitates better utilization of the network resources, while allowing the network routers to continue to employ the simple and well-known shortest-path routing paradigm. Our res...
[ לנוסח המלא ]

In this talk, I will present a novel approach to computational modeling of spatial activation patterns observed through fMRI. Functional connectivity analysis is widely used in fMRI studies for detection and analysis of large networks that co-activate with a user-selected `seed' region of interest. In contrast, our method is based on clustering; it simultaneously identifies interesting seed time courses and associates voxels with the respective networks. This generalization eliminates the sensit...
[ לנוסח המלא ]

My personal involvement in Cryptography started exactly 30 years ago, with the invention of the RSA cryptosystem in 1977. In this talk I will describe some of the major trends in academic cryptographic research over this period, Prof. Shimon Even's early contributions to the field, and some of the most interesting recent results. The talk will be quite general, and accessible to non-experts....
[ לנוסח המלא ]

The security of the RSA cryptosystem is based on the difficulty of solving a single algebraic equation in one variable over a large domain. The security of multivariate cryptosystems is based on the difficulty of solving many algebraic equations in many variables over a small domain. The best known such scheme is SFLASH, which is basically an obfuscated variant of RSA with many variables. It was selected in 2003 by the European NESSIE project as one of only three recommended signature ...
[ לנוסח המלא ]

To support the growing need for Internet bandwidth, contemporary backbone routers and switches operate with an external rate of 20 GB/s and hundreds of ports. At the same time, applications with stringent quality of service (QoS) requirements demand powerful control mechanisms, such as packet scheduling and queue management algorithms. In this talk we discuss an analytic methodology for evaluating such switches by a worst-case comparison of the switch performance relative to an ideal out...
[ לנוסח המלא ]