Sunday, 30.12.2007, 10:30
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 previo...
[ Full version ]
Wednesday, 26.12.2007, 11:30
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 clo...
[ Full version ]
Tuesday, 25.12.2007, 11:30
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: und...
[ Full version ]
Sunday, 23.12.2007, 13:00
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 rota...
[ Full version ]
Sunday, 23.12.2007, 10:30
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 t...
[ Full version ]
Wednesday, 19.12.2007, 11:30
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 ...
[ Full version ]
Wednesday, 19.12.2007, 10:30
Room 527 Bloomfield Bld., Technion
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 pha...
[ Full version ]
Tuesday, 18.12.2007, 11:30
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 enabl...
[ Full version ]
Sunday, 16.12.2007, 13:00
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 int...
[ Full version ]
Sunday, 16.12.2007, 10:30
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...
[ Full version ]
Tuesday, 11.12.2007, 11:30
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 t...
[ Full version ]
Sunday, 09.12.2007, 13:00
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 Bruc...
[ Full version ]
Sunday, 02.12.2007, 10:30
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 measur...
[ Full version ]
Sunday, 25.11.2007, 14:30
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...
[ Full version ]
Sunday, 25.11.2007, 10:30
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 gene...
[ Full version ]
Thursday, 22.11.2007, 14:30
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, B...
[ Full version ]
Wednesday, 21.11.2007, 14:00
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 framewor...
[ Full version ]
Tuesday, 20.11.2007, 11:30
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 chan...
[ Full version ]
Sunday, 11.11.2007, 10:30
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
u...
[ Full version ]
Sunday, 04.11.2007, 10:30
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 s...
[ Full version ]
Tuesday, 30.10.2007, 11:30
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 motio...
[ Full version ]
Sunday, 28.10.2007, 10:30
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 po...
[ Full version ]
Tuesday, 21.08.2007, 11:30
Room 1061, EE Meyer Building
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...
[ Full version ]
Tuesday, 31.07.2007, 16:00
Room 861, EE Meyer Building
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 studi...
[ Full version ]
Wednesday, 25.07.2007, 15:00
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 pa...
[ Full version ]
Monday, 16.07.2007, 11:30
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 elimin...
[ Full version ]
Adi Shamir - in memory of Shimon Even
Thursday, 31.05.2007, 16:30
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....
[ Full version ]
Thursday, 31.05.2007, 14:30
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 recomme...
[ Full version ]
Monday, 12.02.2007, 15:30
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 ...
[ Full version ]
