דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

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

Colloq Seminar: New Algorithms for Ranking and Dimension Reduction
event speaker icon
ניר אילון (גוגל)
event date icon
יום שלישי, 30.12.2008, 14:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
New Algorithms for Ranking and Dimension Reduction The study of ranking crosses many disciplines. Social choice theoreticians have been interested for centuries in finding a good way to rank a set of candidates. Econometricians have been asking for decades how people choose from (and more generally rank) alternative sets. More recently, information retrieval theoreticians and practitioners have been interested in ranking search query results. In verification, practitioners have been interested in ordering variable sets so ...
[לנוסח המלא]
Pixel Club Seminar: Not only size matters: regularized partial matching of shapes
event speaker icon
מיכאל ברונשטיין (.Novafora Inc(
event date icon
יום שלישי, 30.12.2008, 11:30
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
Partial matching is probably one of the most challenging problems in shape analysis. The problem consists of matching similar parts of shapes that are dissimilar on the whole. Conceptually, two shapes can be considered partially matching if they have significant similar parts, with the simplest definition of significance being the size of the parts. Thus, partial matching can be defined as a multcriterion optimization problem trying to simultaneously maximize the similarity and the significance of ...
[לנוסח המלא]
Theory Seminar: Derandomizing Algorithms on Product Distributions and Improved Implicit Probe Search using Same-source Extractors for very
event speaker icon
אבינתן חסידים (.M.I.T)
event date icon
יום ראשון, 28.12.2008, 12:00
event location icon
חדר 601, בניין טאוב למדעי המחשב
An important goal in algorithms and communication protocols is getting the deterministic time complexity, respectively communication complexity, closer to the best known randomized complexity. In this work, we investigate the case where instead of one input, the algorithm \ protocol is given multiple \emph{independent} samples from an \emph{arbitrary unknown} distribution. We show that in this case a strong derandomization result can be obtained by a simple argument. Our method involved extracting randomness from `same-source'-distributions - ...
[לנוסח המלא]
Simulation and Control of Quantum Systems
event speaker icon
Ilan Degani
event date icon
יום חמישי, 25.12.2008, 14:30
event location icon
חדר 337-8 טאוב.
Bioinformatics Forum: Discovery of Mechanisms from Mathematical Modeling of DNA Microarray Data: Computational Prediction and Experimental Verification
event speaker icon
אורלי אלתר (הנדסה ביו-רפואית, אונ' טקסס)
event date icon
יום חמישי, 25.12.2008, 13:30
event location icon
חדר 601, בניין טאוב
DNA microarrays make it possible to record the complete molecular biological signals that guide the progression of cellular processes on genomic scales. I will describe the ability of mathematical models, that were created from these data using matrix and tensor computations, to predict previously unknown biological as well as physical principles, which govern the activities of DNA and RNA. First, I will describe the use of singular value decomposition to uncover "asymmetric Hermite functions," a ...
[לנוסח המלא]
Theory Seminar: Hypergraph Ramsey Numbers
event speaker icon
בני סודקוב (UCLA)
event date icon
יום רביעי, 24.12.2008, 13:30
event location icon
בניין אמדו 719
Abstract: The Ramsey number $r_k(s,n)$ is the minimum $N$ such that every red-blue coloring of the $k$-tuples of an $N$-element set contains either a red set of size $s$ or a blue set of size $n$, where a set is called red (blue) if all $k$-tuples from this set are red (blue). The problem of estimating Ramsey numbers is one of the central problems in modern Combinatorics and it has received a considerable amount of ...
[לנוסח המלא]
Pixel Club Seminar: Organizing Visual Data
event speaker icon
שי אבידן (אדובה מערכות בע"מ)
event date icon
יום רביעי, 24.12.2008, 11:30
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
The growth in the number of digital photographs calls for new and improved image editing tools to help users view, navigate and manipulate them. Many of these tasks can be reduced to instances of organizing visual data to satisfy user constraints. In this talk I will present three such tools that help organize visual data at the pixel, patch and image level: Seam Carving, The Patch Transform, and Infinite Images. Seam Carving attempts to retarget ...
[לנוסח המלא]
Pixel Club Seminar: Generalized Newton Method for Energy Formulations in Image Processing
event speaker icon
לאה בר (הנדסת חשמל, אונ' מינסוטה)
event date icon
יום שלישי, 23.12.2008, 11:30
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
Many problems in image processing are addressed via the minimization of a cost functional. The most prominent optimization technique is the gradient descent, often used due to its simplicity and applicability where other techniques, e.g., those coming from discrete optimization, can not be used. Yet, gradient descent suffers from a slow convergence, and often to just local minima which highly depends on the condition number of the functional Hessian. Newton-type methods, on the other hand, ...
[לנוסח המלא]
Haifux, Linux Haifa Club: Breaking the ice with SELinux (part II)
event speaker icon
אלי בילואר
event date icon
יום שני, 22.12.2008, 18:30
event location icon
טאוב 6
We will continue from "Policy syntax" this meeting (after a quick review of the previous one). We will also see how to write an SELinux module to keep a certain application under control. SELinux is an access permission system, which is running in many recent distributions (with or without the computer owner's awareness). Understanding how this system works seems to become a necessity for a smooth administration of an updated Linux machine. Abstract and slides
[לנוסח המלא]
CGGC Seminar: Generating surfaces and animation by refinement of curves and frames
event speaker icon
אורי איתי (מדעי המחשב, הטכניון)
event date icon
יום ראשון, 21.12.2008, 12:40
event location icon
חדר 337, בניין טאוב למדעי המחשב
Subdivision schemes became popular in recent years in applications such as computer graphics and CAGD (computer aided geometric design). Their implementation is rather simple, yet there is a rich mathematical theory behind them. We will introduce two basic subdivision schemes, (corner cutting and the 4-point) and present implementation of them in computer graphics and in animation.
[לנוסח המלא]
Colloq Seminar: Building on Conflicts: Computational Studies of Codes
event speaker icon
טלי קאופמן (.M.I.T)
event date icon
יום חמישי, 18.12.2008, 14:30
event location icon
חדר 337-8 טאוב.
Many interesting questions in coding theory revolve around conflicts (tradeoffs). Among them are a conflict between structure and randomness, and a conflict between density and symmetry. In some of the cases the conflicts are helpful in understanding solutions for questions (e.g. using the structure and randomness conflict we obtain improved analysis of Reed Muller codes), while in other cases these conflicts shed light on the inherent difficulty of the questions. In the talk, I'll explain ...
[לנוסח המלא]
Bioinformatics Forum: MicroRNAs: from Targets to Function
event speaker icon
דורון בטל (מרכז הסרטן סלואן-קטרינג, ניו-יורק)
event date icon
יום רביעי, 17.12.2008, 13:30
event location icon
חדר 701, בניין טאוב למדעי המחשב
Small regulatory RNAs are a class of non-coding RNAs that are primarily involved in post-transcriptional gene silencing. The principle members of this growing class are microRNAs and small interfering RNAs (siRNAs) which guide a silencing complex to an mRNA target by base pairing at the 3 untranslated region (3UTR). In recent years, microRNAs have emerged as a major class of regulatory genes central to a wide range of cellular activities, and their importance is underscored ...
[לנוסח המלא]
Small-size $eps$-Nets for Geometric Range Spaces.
event speaker icon
Esther Ezra
event date icon
יום שלישי, 16.12.2008, 14:30
event location icon
חדר 337-8 טאוב.
Gradient descent and fast artificial time integration
event speaker icon
Uri Ascher
event date icon
יום ראשון, 14.12.2008, 14:30
event location icon
חדר 337-8 טאוב.
Theory Seminar: Approximation and calculation of low-degree polynomials
event speaker icon
שחר לווט (מכון ויצמן למדע)
event date icon
יום ראשון, 14.12.2008, 12:00
event location icon
חדר 601, בניין טאוב למדעי המחשב
We consider private data analysis in the setting in which a trusted and trustworthy curator, having obtained a large data set containing private information, releases to the public a "sanitization'' of the data set that simultaneously protects the privacy of the individual contributors of data and offers utility to the data analyst. We focus on the case where the process is non-interactive; once the sanitization has been released the original data and the curator play ...
[לנוסח המלא]
Pixel Club Seminar: Descriptor Based Methods in the Wild
event speaker icon
טל הסנר (מ"מ, האונ' הפתוחה)
event date icon
יום שלישי, 9.12.2008, 11:30
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
Recent methods for learning the similarities between images have presented impressive results on the problem of pair-matching (same/not-same classification) of face images. In this talk we present pair-matching results comparing the performance of image descriptor based methods to the state of the art in same/not-same classification, obtained on the Labeled Faces in the Wild (LFW) image set. We propose various contributions, spanning several aspects of automatic face analysis: (i) We present a family of novel ...
[לנוסח המלא]
Theory Seminar: Hardness amplification proofs require majority
event speaker icon
רונן שאלתיאל (אונ' חיפה)
event date icon
יום ראשון, 7.12.2008, 12:00
event location icon
חדר 601, בניין טאוב למדעי המחשב
A function $f$ is $\delta$-hard for some class of circuits if every circuit in the class errs on a $\delta$-fraction of the inputs. For various classes of constant depth small size circuits there are explicit functions that are $\delta$-hard for ``small'' values of $\delta$. For stronger circuit classes there are many ``hardness amplification theorems'' that show how to transform any $\delta$-hard function $f$ into a ``harder'' function $g$ that is $(1/2-\epsilon)$-hard (for very small $\epsilon$). ...
[לנוסח המלא]
Parallel Repetition Theorem Reading Group: Parallel Repetition, Unique Games and Foams?
event speaker icon
פרלד הרשה (אונ' טקסס)
event date icon
יום רביעי, 3.12.2008, 12:00
event location icon
חדר 201, בניין טאוב למדעי המחשב
In this reading group, we will study the parallel repetition theorem, its connection to unique games and tiling in high dimensional spaces. The parallel repetition theorem [Raz 1998] has been extremely useful to compute the exact inapproximability of several optimization problems. Two years ago, Holenstein gave a simplified proof of Raz's theorem. Since then, there has been a flurry of activity in this area: understanding the behavior for special type of 2-prover games (projection, unique); ...
[לנוסח המלא]
Portably preventing file race attacks with user-mode path resolution
event speaker icon
Dan Tsafrir
event date icon
יום שלישי, 2.12.2008, 14:30
event location icon
חדר 337-8 טאוב.
Theory Seminar: Partition Arguments in Multiparty Communication Complexity
event speaker icon
ענב ויינרב (מדעי המחשב, הטכניון)
event date icon
יום ראשון, 30.11.2008, 12:00
event location icon
חדר 601, בניין טאוב למדעי המחשב
Consider the ``plain'' multiparty communication complexity model, where k players $P_1,\dots,P_k$ holding inputs $x_1,\dots,x_k\in\bit^n$ (respectively) communicate in order to compute the value $f(x_1,\dots,x_k)$. The main lower bound technique for such communication problems is that of {\em partition arguments}: partition the $k$-players into two disjoint sets of players and find a lower bound for the induced two-party communication complexity problem. In this paper, we study the power of the partition arguments method. Our two main results ...
[לנוסח המלא]
Theory Seminar: Using classical topology in combinatorial problems
event speaker icon
אלי ברגר (אונ' חיפה)
event date icon
יום רביעי, 26.11.2008, 13:30
event location icon
בניין אמדו 719
The idea of using topology in order to solve combinatorial problems has been known for several decades, but only recently it started to become an organized theory. In my talk I will introduce several classical topological theorems such as Brouwer's fixed point theorem and Sperner's Lemma and give the basic methods for using them in combinatorial settings. I will also describe a new approach that may enable us to use the Borsuk Ulam theorem in ...
[לנוסח המלא]
The Netflix Prize: Quest for $1,000,000
event speaker icon
Yehuda Koren
event date icon
יום שלישי, 25.11.2008, 14:30
event location icon
חדר 337-8 טאוב.
Theory Seminar: Lower Bounds for Satisfiability and Related Problems
event speaker icon
דיטר ואן מלקיבי (אונ. ויסקונסין)
event date icon
יום ראשון, 23.11.2008, 12:00
event location icon
חדר 601, בניין טאוב למדעי המחשב
Ever since the work of Cook and Levin, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a linear-time logarithmic-space algorithm was not ruled out. The last few years have seen considerable progress in time-space lower bounds for satisfiability and closely related problems on various models of computation. This talk will describe the state-of-the-art on deterministic, randomized, and quantum machines, survey ...
[לנוסח המלא]
Church's thesis proof
event speaker icon
Yuri Gurevich
event date icon
יום רביעי, 19.11.2008, 14:30
event location icon
חדר 337-8 טאוב.
Regular Specifications of Resource Requirements for Embedded Control Software
event speaker icon
Gera Weiss
event date icon
יום שלישי, 11.11.2008, 14:30
event location icon
חדר 337-8 טאוב.
Computer (and Human) Perfection at Checkers
event speaker icon
Jonathan Schaeffer
event date icon
יום חמישי, 6.11.2008, 14:30
event location icon
חדר 337-8 טאוב.
Refactoring using Type Constraints (previously presented at SAS'07)
event speaker icon
Frank Tip
event date icon
יום שלישי, 4.11.2008, 14:30
event location icon
חדר 337-8 טאוב.
Pixel Club Seminar: Modeling Evolutionary Processes Using Quasispecies Theory
event speaker icon
Emmanuel Tannenbaum (Ben Gurion University)
event date icon
יום שלישי, 4.11.2008, 11:30
event location icon
חדר 4, בניין טאוב למדעי המחשב
This talk provides an introduction to quasispecies theory, a framework for modeling evolutionary dynamics that was originally introduced to study problems related to the origin of life. Since the original formulation of the theory by Manfred Eigen in 1971, quasispecies theory has been used to study evolutionary processes in a variety of other contexts, but with a focus on molecular and viral evolution. In recent years, we have worked to steadily develop quasispecies theory into ...
[לנוסח המלא]
Cuts and Flows in Directed Graphs
event speaker icon
Julia Chuzhoy RESCHEDULED
event date icon
יום שלישי, 7.10.2008, 14:30
event location icon
חדר 337-8 טאוב.
Equilibria in Online Games
event speaker icon
רועי אנגלברג
event date icon
יום שני, 6.10.2008, 14:00
event location icon
טאוב 601
We initiate the study of scenarios that combine both online decision making and interaction between non-cooperative agents. To this end we introduce the notion of online games that model such scenarios as non-cooperative games, and lay out the foundations for studying this model. Roughly speaking, an online game captures systems in which independent agents serve requests in a common environment. The requests arrive in an online fashion and each is designated to be served by ...
[לנוסח המלא]
Pixel Club Seminar: Compressed Sensing Meets Information Theory
event speaker icon
דרור ברון
event date icon
יום חמישי, 18.9.2008, 11:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
Sensors, signal processing hardware, and algorithms are under increasing pressure to accommodate ever larger data sets; ever faster sampling and processing rates; ever lower power consumption; and radically new sensing modalities. Fortunately, there have been enormous increases in computational power. This progress has motivated Compressed Sensing (CS), an emerging field based on the revelation that a sparse signal can be reconstructed from a small number of linear measurements. The implications of CS are promising, and ...
[לנוסח המלא]
סמינר CGGC:
Approximate Greatest Common Divisors and Polynomials Roots
9:30-11:30, 13:00-15:00, חדר 337, בניין טאוב למדעי המחשב
event speaker icon
יואב וינקלר, אונ' שפילד, אנגליה
event date icon
יום שלישי, 19.8.2008, 09:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
The discussion of the structured condition number and Gauss' method for computing the roots of a polynomial shows that a sequence of greatest common divisor (GCD) computations of two polynomials must be performed. This is a classical problem in mathematics that is often solved by Euclid's algorithm. This algorithm is satisfactory for symbolic computations with exact polynomials, but the computation of the GCD of inexact polynomials is not trivial because it is ill-posed (not ill-conditioned) ...
[לנוסח המלא]
An Efficient Reduction of Ranking to Classification
event speaker icon
Nir Ailon
event date icon
יום שני, 11.8.2008, 14:30
event location icon
חדר 601 טאוב.
Query Understanding using Web Relevance Feedback
event speaker icon
Andrei Broder
event date icon
יום ראשון, 10.8.2008, 14:30
event location icon
חדר 337-8 טאוב.
סמינר פיקסל קלאב: הצגת פרוייקטים שנתית - SIPL, טכניון
event speaker icon
SIPL, טכניון
event date icon
יום חמישי, 7.8.2008, 13:30
event location icon
חדר 1003, בניין מאייר, הפקולטה להנדסת חשמל
See program and invitation להלן הזמנה ותוכנית הכנס
[לנוסח המלא]
סמינר CGGC: An interface for drawing and searching mathematical figures
event speaker icon
יונג-ג'ון קים (אונ' סאול)
event date icon
יום ראשון, 3.8.2008, 12:40
event location icon
חדר 337, בניין טאוב למדעי המחשב
In this talk, I would like to present a user interface for drawing mathematical figures which can be quite complex. The system is based on a sketch interface especially designed for drawing mathematical figures. I would also like to present a search interface that finds figures similar to the one drawn by the user. Given a sketch by the user, the system searches a database of pre-drawn figures, automatically finds similar figures, and shows them ...
[לנוסח המלא]
Theory Seminar: Pseudorandom graphs - what if distinguishers where first order
event speaker icon
אסף נוסבאום (מכון ויצמן למדע)
event date icon
יום ראשון, 3.8.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
We study the limits of efficient computation in the context of constructing random-looking graph distributions that can be used to emulate huge random graphs over N=2^n vertices. We suggest and analyze a new criterion of faithful emulation, inspired by the famous 0/1-law of random graphs. This 0/1-law states that any graph property T holds with probability converging either to 0 or to 1, whenever T is expressible by a single formula on graphs. We consider ...
[לנוסח המלא]
פיקסל קלאב: CT Denoising by K-SVD on the Cell processor
event speaker icon
דומיניק ברטושט (אונ' אלנגן, גרמניה)
event date icon
יום רביעי, 30.7.2008
event location icon
חדר 601, בניין טאוב למדעי המחשב
The K-SVD algorithm is a powerful tool for image denoising but computationally quite intensive. In order to accelerate it we implement the most time consuming parts like sparse coding and assembling the final denoised image vectorized and in parallel on the Cell processor. The Cell processor is a heterogeneous multicore system consisting of a general purpose Power-PC processor unit (PPU) and several fast co-processors, the synergistic processor elements (SPEs). We present runtime results comparing a ...
[לנוסח המלא]
פורום ביואינפורמטיקה: Whole Population, Genomewide Mapping of Hidden Relatedness
event speaker icon
סשה גוסב (אונ' קולומביה)
event date icon
יום חמישי, 24.7.2008, 13:30
event location icon
חדר 601, בניין טאוב למדעי המחשב
Identifying and quantifying the sharing of genetic material between individuals within a population is an important step in accurately using genealogical relationships for disease analysis as well as improving our understanding of demography. However, exhaustive pairwise analysis which has been successful in small cohorts cannot keep up with the current torrent of genotype data. We present GERMLINE, a robust algorithm for identifying pairwise segmental sharing which scales linearly with the number of input individuals. Our ...
[לנוסח המלא]
מועדון מתמטי: Probabilistic Reasoning
event speaker icon
פרופ' נגה אלון (אונ' ת"א, זוכה פרס ישראל 2008)
event date icon
יום רביעי, 23.7.2008, 16:30
event location icon
טאוב 1, מדעי המחשב
Abstract: The discovery that deterministic statements can be proved by probabilistic reasoning, led already more than fifty years ago to several striking results in various mathematical disciplines. It soon became clear that the method, which is now called the probabilistic method, is a very powerful tool for proving results in Discrete Mathematics. After some light examples that illustrate the fact that probabilistic arguments may be counter-intuitive, I will sketch some recent applications of probabilistic ideas ...
[לנוסח המלא]
An optimal coin toss protocol
event speaker icon
Professor Moni Naor
event date icon
יום שני, 21.7.2008, 14:30
event location icon
חדר 337-8 טאוב.
Real Time Java
event speaker icon
הרצאה מטעם סאן מיקרוסיסטמס
event date icon
יום ראשון, 20.7.2008, 14:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
The lecture topics are: 1) Real Time programming in a nutshell. 2) Programming languages comparison (Real Time related). 3) Java vs. C/C++ with relevant benchmarks. 4) Why Java, Why Java for Real Time? 5) What is the Real Time Java Standard? 6) Sun Real Time Java technology 7) Customers and case studies 6) Real Time Java competitive landscape For more information please contact David: David.Roitman at Sun.com
[לנוסח המלא]
Theory Seminar: Two Query PCP with Sub-Constant Error
event speaker icon
דנה מושקוביץ', מכון ויצמן למדע
event date icon
יום ראשון, 20.7.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
We show that the NP-Complete language 3Sat has a PCP verifier that makes two queries to a proof of almost-linear size and achieves sub-constant probability of error o(1). The verifier performs only projection tests, meaning that the answer to the first query determines at most one accepting answer to the second query. Previously, by the parallel repetition theorem, there were PCP Theorems with two-query projection tests, but only (arbitrarily small) constant error and polynomial size. ...
[לנוסח המלא]
An Efficient Reduction of Ranking to Classification
event speaker icon
Nir Ailon (POSTPONED FROM 3/7/08)
event date icon
יום חמישי, 17.7.2008, 14:30
event location icon
חדר 337-8 טאוב.
The finite harmonic oscillator with applications to radar and communication
event speaker icon
Ronny Hadani
event date icon
יום שלישי, 15.7.2008, 14:30
event location icon
חדר 337-8 טאוב.
Theory Seminar: The Constant-Depth Complexity of k-Clique
event speaker icon
בנג'מין רוסמן (M.I.T.)
event date icon
יום ראשון, 13.7.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
will discuss a recent lower bound of Omega(n^(k/4)) on the size of depth-d circuits for the k-clique problem on n-node graphs. This improves previous lower bounds (e.g. Omega(n^(k/89d2)) [P. Beame '90]) by removing dependence on d from the exponent of n. This result has an interesting corollary in logic: it implies that the "bounded variable logics" FO1, FO2, ..., FO^k, ... (where FO^k consists of first-order sentences in which no subformula has no more than ...
[לנוסח המלא]
Bioinformatics Forum: Systems Macro-Biology: Less is More in Disease Biomarkers
event speaker icon
פרופ' שמעון כסיף (אוניברסיטת בוסטון, ובי"ח לילדים, בוסטון)
event date icon
יום חמישי, 10.7.2008, 13:30
event location icon
חדר 601, בניין טאוב למדעי המחשב
We describe several new methodologies for developing and evaluating novel diagnostics for diabetes and cancer. In the first part of the talk we describe the Gene Network Enrichment Analysis (GNEA) methodology for identifying molecular markers for diabetes. This approach suggests that network based techniques might be more sensitive and accurate at identifying disease progression than single genes. At the same time we should pay significant attention to both the biological interpretation of results and the ...
[לנוסח המלא]
Pixel Club Seminar: Active learning in dynamical systems – from robotics to computational biology
event speaker icon
פרופ' הוד ליפסון ( מתמטיקה וחלל, אוניב' קורנל)
event date icon
יום חמישי, 10.7.2008, 11:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
This talk will describe new active learning processes for automated modeling of dynamical systems across a number of disciplines. One of the long-standing challenges in robotics is achieving robust and adaptive performance under uncertainty. One approach to adaptive behavior is based on self-modeling, where a system continuously evolves multiple simulators of itself in order to make useful predictions. The robot is rewarded for actions that cause disagreement among predictions of different candidate simulators, thereby elucidating ...
[לנוסח המלא]
CGGC Seminar: Smooth Surface Fitting (Tutorial)
event speaker icon
סטפני ההמן (אונ' גרונובל)
event date icon
יום שני, 7.7.2008, 10:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
The recent ability to measure quickly and inexpensively dense sets of points on physical objects has deeply influenced the way engineers represent shapes in CAD systems, animation software or in the game industry. Many researchers advocated to completely bypass smooth surface representations, and to stick to a dense mesh model throughout the design process. Yet smooth analytic representations are still required in standard CAD systems and animation software, for reasons of compactness, control, appearance and ...
[לנוסח המלא]
Theory Seminar: Combinatorial Construction of Locally Testable Codes
event speaker icon
אור מאיר (מכון ויצמן למדע)
event date icon
יום ראשון, 6.7.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
An error correcting code is said to be locally testable if there is a test that can check whether a given string is a codeword of the code, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first explicitly studied by Goldreich and Sudan (J. ACM 53(4)) and since then several constructions of LTCs were suggested. While the best known construction of ...
[לנוסח המלא]
On the Hardness of Being Truthful
event speaker icon
Michael Schapira
event date icon
יום חמישי, 3.7.2008, 14:30
event location icon
חדר 337-8 טאוב.
The central problem in computational mechanism design is the tension between incentive compatibility and computational efficiency. We address this question in the context of a novel mechanism design problem which we call the combinatorial public project problem. We show that, even though this problem is easily solvable from a computational viewpoint, and from an economic perspective, no algorithm which is simultaneously truthful and runs in polynomial-time can obtain any reasonable approximation ratio. We prove our ...
[לנוסח המלא]
Pixel Club Seminar: "Cognitive" Memory and its Applications
event speaker icon
פרופ' ברנרד וידרו (הנדסת חשמל, אונ' סטנפורד)
event date icon
יום רביעי, 2.7.2008, 11:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
Regarding the workings of the human mind, memory and pattern recognition seem to be intertwined. You generally do not have one without the other. Taking inspiration from life experience, a new form of computer memory has been devised. Certain conjectures about human memory are keys to the central idea. The design of a practical and useful "cognitive" memory system is contemplated, a memory system that may also serve as a model for many aspects of ...
[לנוסח המלא]
Property Testing and Combinatorial Approximation
event speaker icon
אריה מצליח
event date icon
יום רביעי, 25.6.2008, 16:00
event location icon
טאוב 601
With the recent advances in technology, we are faced with the need to process increasingly larger amounts of data increasingly faster. Originally, a problem was considered computable if there was an algorithm that could decide it in finite time given any input instance. Later came the notion of polynomial time computation, and then the possibility of making computations faster through use of parallel machines. However, the algorithms involved still face the obvious obstacle of reading ...
[לנוסח המלא]
List error-correction: New constructions, algorithms, and applications
event speaker icon
Venkatesan Guruswami
event date icon
יום שלישי, 24.6.2008, 14:30
event location icon
חדר 337-8 טאוב.
Pixel Club Seminar: Fenchel Duality with Applications to Inference
event speaker icon
אמנון שעשוע (ביה"ס להנדסה ומדעי המחשב, האונ' העברית)
event date icon
יום שלישי, 24.6.2008, 14:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
Quite a number of problems involving inference from data, whether visual data or otherwise, fall into the category of optimization. I will describe a general scheme for sequential and parallel (message passing) update rules based on the framework of Fenchel duality. The presentation will be done in the context of two applications (i) distributed (parallel) Support-Vector-Machines (SVM) for handling large scale problems (to be presented at CVPR'08), (ii) Graphical Model inference over "convex free energies" ...
[לנוסח המלא]
Pixel Club Seminar: Theoretical Results on Robot Localization, Mapping and Goal-Directed Navigation in Unknown Terrain
event speaker icon
סוון קוניג (אוניברסיטת דרום קליפורניה)
event date icon
יום שלישי, 24.6.2008, 11:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
Path planning for robots in unknown terrain has been studied in both theoretical robotics and theoretical computer science. However, empirical robotics researchers have often developed their own planning methods. These planning methods have been demonstrated on mobile robots that solve complex real-world tasks and perform well in practice. I will discuss some of these planning methods (namely, Planning with the Freespace Assumption, Greedy Mapping and Greedy Localization) and show how to use tools from graph ...
[לנוסח המלא]
Pixel Club Seminar: Simple, Fast Simulation and Artistic Control of Cloth and Thin Shells
event speaker icon
איתן גרינשפון ( מדעי המחשב, אונ' קולומביה)
event date icon
יום ראשון, 22.6.2008, 14:00
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
What does it take to build fast simulators for cloth and thin shells—in particular to do so with code that is simple to implement, debug, and maintain? Our group's belief is that simple geometric observations help to address all these goals. I will survey my students' recent work on the discrete differential geometry of thin, flexible surfaces, and focus on a couple simple geometric observations that lead to efficient and simple models for bending, stretching, ...
[לנוסח המלא]
Theory Seminar: Quantum Multi Prover Interactive Proofs with Communicating Provers
event speaker icon
אבינתן חסידים (האוניברסיטה העברית בירושלים)
event date icon
יום ראשון, 22.6.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
We introduce a variant of Quantum Multi Prover Interactive Proofs (QMIP), where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case - we show that any language ...
[לנוסח המלא]
Beyond Bandlimited Sampling: Nonideal Sampling, Smoothness and Sparsity
event speaker icon
Yonina Eldar
event date icon
יום שלישי, 17.6.2008, 14:30
event location icon
חדר 337-8 טאוב.
אלן אופנהיים ( מכון טכנולוגי, מסצ'וסטס)
event speaker icon
Alan Oppenheim (Massachusetts Institute of Technology)
event date icon
יום ראשון, 15.6.2008, 16:00
event location icon
חדר 1003, בניין מאייר, הפקולטה להנדסת חשמל
Digital processing of analog signals naturally requires a representation of continuous time signals as a discrete-time sequence. The most common representation of this type is based on the Shannon-Nyquist sampling theorem which provides an exact representation for band limited signals sampled at a sufficiently high rate but leads to aliasing error when the signal is under sampled. In this talk a number of other approaches are discussed to obtaining discrete-time representations that avoid or mitigate ...
[לנוסח המלא]
Bioinformatics Forum: Alternative Splicing Events of Arbitrary Dimension in Splicing Graphs
event speaker icon
מיכה סמט (מעבדת ביואינפו', ברצלונה, ספרד)
event date icon
יום ראשון, 15.6.2008, 13:30
event location icon
טאוב 701
Eukaryotic splicing structures are known to involve a high degree of alternative forms derived from a premature transcript by alternative splicing (AS). With the advent of new sequencing technologies, evidence for new splice forms becomes more and more easily availablebit by bit revealing that the true splicing diversity of "AS events often comprises more than two alternatives and therefore cannot be sufficiently described by pairwise comparisons as conducted in analyzes hitherto. Further challenges emerge from ...
[לנוסח המלא]
Theory Seminar: Expander codes, Euclidean Sections, and Compressed Sensing
event speaker icon
Venkatesan Guruswami, (Washington University)
event date icon
יום ראשון, 15.6.2008, 13:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
Classical results in high-dimensional geometry from the 1970's state that a random subspace of R^N of dimension N/2 has "distortion" O(1) w.h.p where the distortion is measured by sqrt{N} times the largest ratio of the L_2 to L_1 norms of a vector in the subspace. (So each vector in the subspace has its mass spread nearly evenly over a constant fraction of the coordinates.) This result is a particular example of the use of the ...
[לנוסח המלא]
CGGC Seminar: Formulae and Growth Rates of High-Dimensional Polycubes
event speaker icon
גיל ברקת (מדעי המחשב, הטכניון)
event date icon
יום ראשון, 15.6.2008, 13:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
An Algebraic Approach to Rule-Based Information Extraction
event speaker icon
Frederick R. Reiss
event date icon
יום חמישי, 12.6.2008, 14:30
event location icon
חדר 337-8 טאוב.
Math-Club Seminar: On the Security of GSM Cellular Phones
event speaker icon
אלי ביהם (מדעי המחשב, הטכניון)
event date icon
יום רביעי, 11.6.2008, 16:30
event location icon
טאוב 1
Abstarct:In this talk we describe the ciphers and protocols used for the GSM cellular phone network, and discuss the (in)security of the system. We describe several techniques to attack the ciphers A5/2 and A5/1, and how they can be applied as a ciphertext-only attack. We also show that active attacks on the protocols can recover keys of ciphers that are not used during that transmission. As a result, it is possible to listen in to ...
[לנוסח המלא]
Approximate median selection
event speaker icon
Micha Hofri (NEW DATE instead 5/6)
event date icon
יום רביעי, 11.6.2008, 11:30
event location icon
חדר 337-8 טאוב.
Pixel Club Seminar: 3D Objects Description and Classification by Implicit Polynomials
event speaker icon
הילה בן-יעקב (הנדסת חשמל, הטכניון)
event date icon
יום שלישי, 10.6.2008, 11:30
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
3D Objects Description and Classification by Implicit Polynomials
[לנוסח המלא]
Theory Seminar: The finite field Kakeya conjecture
event speaker icon
זאב דביר (מכון וייצמן למדע)
event date icon
יום ראשון, 8.6.2008, 11:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
A Kakeya set in F^n, where F is a finite field, is a set containing a line in every direction. The finite field Kakeya conjecture states that the size of such sets is bounded from below by C_n*|F|^n, where C_n depends only on the dimension n. I will talk about the recent proof of this conjecture and its connection to problems in theoretical computer science.
[לנוסח המלא]
Approximate median selection
event speaker icon
Micha Hofri
event date icon
יום חמישי, 5.6.2008, 14:30
event location icon
חדר 337-8 טאוב.
Maximum Degree-Bounded Connected Subgraph: Hardness and Approximation
event speaker icon
Ignasi sau
event date icon
יום רביעי, 4.6.2008, 15:30
event location icon
חדר 337-8 טאוב.
On the Nature of Progress
event speaker icon
Nir Shavit
event date icon
יום שלישי, 3.6.2008, 14:30
event location icon
חדר 337-8 טאוב.
Agnostically Learning Decision Trees
event speaker icon
Adam Kalai
event date icon
יום ראשון, 1.6.2008, 14:30
event location icon
חדר 337-8 טאוב.
TBA
event speaker icon
Oded Goldreich - in memory of Shimon Even
event date icon
יום רביעי, 28.5.2008, 16:30
event location icon
חדר 337-8 טאוב.
Lower Bounds in the Noisy Networks using Sampling Algorithms
event speaker icon
Jaikumar Radhakrishnan
event date icon
יום שלישי, 27.5.2008, 14:30
event location icon
חדר 337-8 טאוב.
Logic in Access Control
event speaker icon
Yuri Gurevich
event date icon
יום ראשון, 18.5.2008, 14:30
event location icon
חדר 337-8 טאוב.
Formulae and growth rates of high-dimensional polycubes
event speaker icon
גיל ברקת (מדעי המחשב, הטכניון)
event date icon
יום ראשון, 18.5.2008, 14:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
A $d$-dimensional polycube is a connected set of $d$-dimensional cubes on an orthogonal lattice, where connectivity is through $(d-1)$-dimensional faces. A polycube is said to be proper in $d$ dimensions if it spans all the $d$ dimensions, that is, the convex hull of the centers of all its cubes is $d$-dimensional. We prove a few new formulae for the numbers of (proper and total) polycubes, and show that (2d-3)e + O(1/d) is the asymptotic growth ...
[לנוסח המלא]
Abstraction-Refinement and Modularity in mu-Calculus Model Checking
event speaker icon
שרון שוהם בוכבינדר
event date icon
יום רביעי, 14.5.2008, 16:00
event location icon
טאוב 601
Model checking is an automated technique for checking whether or not a given system model fulfills a desired property, described as a temporal logic formula. Yet, as real models tend to be very big, model checking encounters the state-explosion problem, which refers to its high space requirements. Two of the most successful approaches to fighting the state-explosion problem in model checking are abstraction and compositional model checking. Abstractions hide certain details of the system in ...
[לנוסח המלא]
Natural history and evolutionary principles of gene duplication in fungi
event speaker icon
Nir Friedman
event date icon
יום שלישי, 13.5.2008, 14:30
event location icon
חדר 337-8 טאוב.
CGGC Seminar: Interactive Rendering of Dynamic Geometry
event speaker icon
Kai Hormann (Clausthal Institute of Technology)
event date icon
יום שלישי, 13.5.2008, 11:00
event location icon
חדר 601, בניין טאוב למדעי המחשב
Fluid simulations typically produce complex three-dimensional iso-surfaces whose geometry and topology change over time. The standard way of representing such dynamic geometry is by a set of iso-surfaces that are extracted individually at certain time steps. An alternative strategy is to represent the whole sequence as a four-dimensional tetrahedral mesh. The iso-surface at a specific time step can then be computed by intersecting the tetrahedral mesh with a three-dimensional hyperplane. This not only allows to ...
[לנוסח המלא]
Counting polycubes without the dimensionality curse
event speaker icon
גדי אלכסנדרוביץ' (מדעי המחשב, הטכניון)
event date icon
יום ראשון, 11.5.2008, 13:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
$d$-dimensional polycubes are the generalization of planar polyominoes to higher dimensions. That is, a $d$-D polycube of size $n$ is a connected set of $n$ cells (hypercubes) of an orthogonal $d$-dimensional lattice, where connectivity is through $(d-1)$-dimensional faces of the cells. Computing $A_d(n)$, the number of distinct $d$-dimensional polycubes of size $n$, is a long-standing elusive problem in discrete geometry. In a previous work we described the generalization from two to higher dimensions of a ...
[לנוסח המלא]
Pixel Club Seminar: Fast acquisition and reconstruction in imaging enabled by sampling theory
event speaker icon
יורם ברסלר (אונ' אילינוי)
event date icon
יום שלישי, 6.5.2008, 11:30
event location icon
חדר 701, בניין טאוב למדעי המחשב
We survey applications of classical and of time-sequential sampling theory and some of its recent extensions, respectively, in two complementary areas. First to reduce the computation for tomographic reconstruction from $O(N^3)$ to $O(N^2\log N)$ for an $N \times N$ image, with similar acceleration for 3D images. And second, to reduce acquisition requirements for dynamic imaging below those predicted by classical theory. In both areas, the savings demonstrated in practical examples exceed an order-of-magnitude.
[לנוסח המלא]
Theory Seminar: Developments in the Area of Communication Complexity
event speaker icon
עדי שרייבמן (מתמטיקה ומ"מ, מכון ויצמן)
event date icon
יום שלישי, 6.5.2008, 10:30
event location icon
חדר 401, בניין טאוב למדעי המחשב
We will describe the results from a series of papers, starting from papers of Forster, Ben-David and others to more recent works of Sherstov and Chattopadhyay. The topics of these papers are learning, communication and computational complexity. Examples of some contributions of these papers are 1. The first lower bound on unbounded error probabilistic communication complexity. 2. Definition and study of learning theoretic quantities such as margin complexity which eventually led to the solution of ...
[לנוסח המלא]
Designing Competitive Online Algorithms via a Primal-Dual Approach
event speaker icon
ניב בוכבינדר
event date icon
יום רביעי, 16.4.2008, 16:30
event location icon
טאוב 601
In this work we study a wide range of online covering and packing problems with various objectives. We provide a unified approach, based on a clean primal-dual method, for the design and analysis of online algorithms for this large class of problems. In particular, our analysis uses weak duality rather than a tailor made (i.e., problem specific) potential function. We show how to apply the primal-dual approach to many interesting problems. Examples consist of the ...
[לנוסח המלא]
Pixel Club Seminar: The Importance of Being Earnest...about Optimality
event speaker icon
אלפרד ברוקשטיין
event date icon
יום ראשון, 13.4.2008, 14:30
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
I shall discuss the many ways one can do optimal image or signal denoising, and the difficulties in selecting between the various optimal solutions.
[לנוסח המלא]
A Geometric Approach to Detecting Global Properties over Distributed Data
event speaker icon
יצחק צחי שרפמן
event date icon
יום רביעי, 9.4.2008, 16:30
event location icon
טאוב 601
A basic construct in many distributed systems is the detection of global properties over distributed data. Examples include a wireless sensor network, where we would like to receive an alert every time the average of the temperature readings taken by the sensors exceeds a given threshold, or a distributed search engine, where we would like to determine the set of search terms whose frequency of use exceeds a given threshold. Until recently, research has focus ...
[לנוסח המלא]
Recent advances in online convex optimization
event speaker icon
Elad Hazan
event date icon
יום שלישי, 8.4.2008, 14:30
event location icon
חדר 337-8 טאוב.
Pixel Club Seminar: Fast Block Motion Estimation Using Gray‐Code Kernels
event speaker icon
יאיר משה (מדעי המחשב, אונ' חיפה)
event date icon
יום שלישי, 8.4.2008, 11:30
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
Motion estimation plays an important role in modern video coders. In such coders, motion is estimated using a block matching algorithm that estimates the amount of motion on a block‐by‐block basis. A full search technique for finding the best matching blocks delivers good accuracy but is usually not practical because of its high computational complexity. In this talk, a novel fast block‐based motion estimation algorithm is presented. This algorithm uses an efficient projection framework which ...
[לנוסח המלא]
Painting Rectilinear Pictures Without Picasso
event speaker icon
Howard Karloff
event date icon
יום ראשון, 6.4.2008, 14:30
event location icon
חדר 337-8 טאוב.
Theory Seminar: A combinatorial construction of almost-Ramanujan graphs using the zig-zag product
event speaker icon
אברהם בן-ארויה (אונ' ת"א)
event date icon
יום ראשון, 6.4.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
Reingold, Vadhan and Wigderson [FOCS'00] introduced the graph zig-zag product. This product combines a large graph and a small graph into one graph, such that the resulting graph inherits its size from the large graph, its degree from the small graph and its spectral gap from both. Using this product they gave the first fully-explicit combinatorial construction of expander graphs. They showed how to construct $D$-regular graphs having spectral gap $1-O(D^{-\frac{1}{3}})$. In the same paper, ...
[לנוסח המלא]
Windows Core Architecture: compare and contrast
event speaker icon
Dave Probert
event date icon
יום חמישי, 3.4.2008, 14:30
event location icon
טאוב 2
On the complexity of graph polynomials
event speaker icon
Markus Blaeser
event date icon
יום שלישי, 1.4.2008, 14:30
event location icon
חדר 337-8 טאוב.
Geometric deformations
event speaker icon
Yaron Lipman (Computer Science, Tel Aviv Univ.)
event date icon
יום ראשון, 30.3.2008, 13:00
event location icon
חדר 337-8 טאוב.
CGGC Seminar: Deforming objects in a "shape preserving" manner is a challenging problem with various applications in geometric modeling and computer graphics. In this talk I will examine two geometric-driven approaches to the problem. First, reformulating the problem using the notion of Cartan's moving frames reveals an intriguing relationship between harmonic maps into the group of rotations and shape preserving deformations. The moving frames are known in differential geometry for their ability to simplify some ...
[לנוסח המלא]
Theory Seminar: Secure Internet Path Quality Monitoring: Tradeoffs in Security and Efficiency
event speaker icon
דוד שיאו (אונ' פרינסטון)
event date icon
יום ראשון, 30.3.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
The basic foundations of the Internet are surprisingly vulnerable to simple attacks that could be mounted by rogue hackers or result from simple misconfiguration. One area that remains particularly exposed to attacks is routing: packets usually traverse many intermediate routers on their way from a source to their destination. Since these routers may belong to other (possibly malicious) organizations, how do we guarantee that our packets arrive as intended at their destination and are not ...
[לנוסח המלא]
Towards Universal Semantic Communication
event speaker icon
Madhu Sudan
event date icon
יום שלישי, 25.3.2008, 14:30
event location icon
חדר 337-8 טאוב.
Computational Awareness
event speaker icon
Lance Fortnow
event date icon
יום חמישי, 20.3.2008, 14:30
event location icon
חדר 337-8 טאוב.
Pixel Club Seminar: Aspects of invariant shape processing
event speaker icon
אלכסנדר ברוק, מדעי המחשב, הטכניון
event date icon
יום שני, 17.3.2008, 10:30
event location icon
חדר 601, בניין טאוב למדעי המחשב
The lecture deals with invariance in image processing, with emphasis on invariance of shapes and curves. There are two main topics. First, we consider scale invariance, review existing scale invariant measures and discuss the different ways in which an algorithm can be scale invariant. We then point out some dangers inherent in fully scale invariant algorithms. Second, we present an equi-affine invariant shape matching mathod, which is also invariant to resampling, robust to pixelisation noise ...
[לנוסח המלא]
Datacenter of the future
event speaker icon
Tilak Agerwala
event date icon
יום חמישי, 13.3.2008, 11:00
event location icon
חדר 337-8 טאוב.
The Cloning Method for Combinatorial Optimization, Countingand Rare Events Using Gibbs Sampler
event speaker icon
Reuven Rubinstein and Andrey Dolgin
event date icon
יום שלישי, 11.3.2008, 14:30
event location icon
חדר 337-8 טאוב.
Object and Reference Immutability using Java Generics
event speaker icon
Yoav Zibin
event date icon
יום שלישי, 4.3.2008, 14:30
event location icon
חדר 337-8 טאוב.
Theory Seminar: Lower Bounds for Edit Distance Estimation
event speaker icon
רוברט קראוטגאמר (מכון וייצמן וי.ב.מ אלמדן)
event date icon
יום ראשון, 2.3.2008, 16:30
event location icon
חדר 337, בניין טאוב למדעי המחשב
The edit distance between two strings is defined as the number of insertions/deletions/substitutions needed to transform one string into the other. This distance plays a key role in several fields like computational biology and text processing. Edit distance appears to be notoriously difficult to deal with algorithmically (both theoretically and in practice). However, no nontrivial computational lower bounds for it are known, and the only negative evidence known is that edit distance does not embed ...
[לנוסח המלא]
Moadon Matemati: The longest proof
event speaker icon
דוד צילג, מתמטיקה, הטכניון
event date icon
יום רביעי, 27.2.2008, 16:30
event location icon
טאוב 1, מדעי המחשב
The mathematical theorem having the longest proof is the classification of the finite simple groups. In this talk we will try to understand the statement of the theorem and its importance. The lecture will be in Hebrew. ההרצאה תינתן בעברית.
[לנוסח המלא]
Pixel Club Seminar: Multi-sensor human action analysis
event speaker icon
כריסטיאן קנטון-פרר, עיבוד תמונה, UPC, ברצלונה
event date icon
יום שלישי, 26.2.2008, 11:00
event location icon
חדר 815, בניין מאייר, הפק' להנדסת חשמל
Multi-camera environments allow exploiting spatial redundancy that might be used by analysis algorithms to produce more robust results. These algorithms may be applied for a variety of tasks ranging from human 3D scene volume reconstruction, human motion capture, gesture analysis or focus of attention tracking. Combining this multi-camera information with audio information would allow defining multimodal data analysis systems. This talk will present two research lines within this scope. First, a Particle Filtering based algorithm ...
[לנוסח המלא]
Theory Seminar: Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
event speaker icon
זאב דביר, מכון וייצמן למדע
event date icon
יום ראשון, 24.2.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
We show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f(x_1,...,x_m) that cannot be computed by a depth d arithmetic circuit of small size then there exists an efficient deterministic algorithm to test whether a given depth d-8 circuit is identically zero or not (assuming the individual degrees of the tested circuit are not too high). ...
[לנוסח המלא]
Static Specification Mining Using Automata-Based Abstractions
event speaker icon
Eran Yahav
event date icon
יום שלישי, 19.2.2008, 14:30
event location icon
חדר 337-8 טאוב.
Pixel Club Seminar: On Isometry, Self-Symmetry, and Biometry
event speaker icon
רון קימל, מדעי המחשב
event date icon
יום ראשון, 17.2.2008, 14:30
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
Our world is filled with nonrigid objects that can deform and bend. Nonrigid shapes appear at all scales - from our body, its organs and tissues, to tiny bacteria and microscopic protein molecules. When trying to analyze nonrigid shapes the richness of the possible deformations poses a challenge due to the large number of degrees of freedom. Thus, generally speaking, explicit analysis of nonrigid objects has so far been avoided. Today, there is a comprehension ...
[לנוסח המלא]
Pixel Club Seminar: On texture and image interpolation using Markov models
event speaker icon
שירה נמירובסקי, הנדסת חשמל, הטכניון
event date icon
יום שלישי, 12.2.2008, 11:30
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
Random field models characterize the correlation among neighboring pixels in an image. Specifically, a wide-sense Markov model is obtained by assuming a separable correlation function for a 2D auto-regressive (AR) model. This model is applicable to image restoration, image compression, and texture classification and segmentation. In this work we explore the effect of sampling on statistical features of an image such as histogram and the autocorrelation function. We show that the Markovian property is preserved ...
[לנוסח המלא]
CGGC Seminar: SolidWorks as geometry engine for engineers
event speaker icon
אודי בהט, סיסטמטיקס בע"מ
event date icon
יום ראשון, 10.2.2008, 13:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
"The Challenge", Definitions, GUI, basic and smart geometry in 2D and 3D, basic model, "styled" model, shape manipulations, hybrid design, develop challenge.
[לנוסח המלא]
Theory Seminar: Local testing of direct products
event speaker icon
עירית דינור, מכון וייצמן למדע
event date icon
יום ראשון, 10.2.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
Given a function f:[n]-->{0,1}, its k-wise direct product encoding is the function F:[n]^k --> {0,1}^k defined by F(x_1,..x_k) = (f(x_1),...,f(x_k)) This simple "encoding" is useful in PCP-like settings, when we want to simulate reading k arbitrary values of f by accessing only a constant number of inputs of the encoding F. The main challenge is to test that a given F is indeed a "correct" encoding of some f by reading only few (ultimately 2) ...
[לנוסח המלא]
On the complexity of infinite computations
event speaker icon
Damian Niwinski
event date icon
יום חמישי, 7.2.2008, 14:30
event location icon
חדר 337-8 טאוב.
Using coupling between residues based on evolutionary data for protein structure analysis
event speaker icon
ערן איל (ביולוגיה חישובית, בי"ס לרפואה, אונ' פיטסבורג)
event date icon
יום חמישי, 7.2.2008, 13:30
event location icon
חדר 601, בניין טאוב למדעי המחשב
Multiple sequence alignments possess important information, not only about functionally and structurally important conserved regions, but also about coupling between residues. Recently we have developed a unique method to detect such coupling based on substitution matrices of residue pairs. I will describe the method and show how it performs at structural analysis tasks as contact prediction and discrimination of decoy sets. I will then show recent results that demonstrate how correlated mutations can be used ...
[לנוסח המלא]
Theory Seminar: The Power of VCG: On Algorithms that are Maximal In Range
event speaker icon
שחר דובזינסקי, מדעי המחשב , האונ' העברית, י-ם
event date icon
יום ראשון, 3.2.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
Consider the following simple type of approximation algorithms: limit the set of possible outcomes, and completely optimize over the restricted subrange. In this talk we will study the power of this type of algorithms in two settings: multi-unit auctions, and combinatorial auctions with subadditive bidders. From a game-theoretic point of view, our results provide a characterization of the power of the main positive result of mechanism design the VCG mechanism. Another motivation is that our ...
[לנוסח המלא]
CGGC Seminar: Coupling surface and tetrahedral mesh generation with the restricted Delaunay triangulation
event speaker icon
פייר אליעז, מדעי המחשב, אינרייה סופיה אנטיפוליס
event date icon
יום רביעי, 30.1.2008, 15:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
A Delaunay triangulation restricted to a surface is obtained by filtering a 3D Delaunay triangulation. Filtering herein consists of selecting a subset of the 3D Delaunay facets whose dual edges intersect the surface. In this talk I will explain how the restricted Delaunay triangulation paradigm can be used to simultaneously mesh a surface together with its interior. I will then describe two mesh generation algorithms along these lines and show a demo made with components ...
[לנוסח המלא]
Generating Programs from Specifications (with some observations on the modularity of object oriented systems)
event speaker icon
David Feitelson
event date icon
יום שלישי, 29.1.2008, 14:30
event location icon
חדר 337-8 טאוב.
Pixel Club Seminar: Image Processing using Diffusion with Schrödinger's Potential
event speaker icon
אורי הוניגמן, הפקולטה להנדסת חשמל, הטכניון
event date icon
יום שלישי, 29.1.2008, 11:30
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
The complex diffusion process, recently introduced in image processing and computer vision by combining the linear diffusion equation and the 'free-particle' Schrödinger equation, is further generalized by incorporating the Schrödinger potential. We incorporate the potential into the complex diffusion equation, introducing some kind of 'dynamic boundary conditions' that serve as a filtering or even enhancing mechanism for textures. The Schrödinger potential is self-adopting to the specific properties of an image at hand, in that it ...
[לנוסח המלא]
CGGC Seminar: A decade of CGAL arrangements and applications
event speaker icon
דן הלפרין, מדעי המחשב , אוניברסיטת תל-אביב
event date icon
יום ראשון, 27.1.2008, 13:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
The Computational Geometry Algorithms Library, CGAL, is the largest software collection of algorithms and data structures in Computational Geometry available today. It started a little over a decade ago as a European research project with a small number of partners and has grown over the years to be a huge open source project. The arrangement package of CGAL, developed at Tel Aviv University, constructs, maintains, traverses, and answers queries on two-dimensional arrangements (subdivisions) of general ...
[לנוסח המלא]
Theory Seminar: Trapdoors for Hard Lattices, and New Lattice-based Cryptography
event speaker icon
Vinod Vaikuntanathan, MIT
event date icon
יום ראשון, 27.1.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
We show that disjointness requires randomized communication Omega(n^{1/2k} / (k-1)2^{k-1}2^{2^{k-1}}) in the general k-party number-on-the-forehead model of complexity. The previous best lower bound was Omega (\log n / k-1). By results of Beame, Pitassi, and Segerlind, this implies 2^{n^{Omega(1)}} lower bounds on the size of tree-like Lovasz-Schrijver proof systems needed to refute certain unsatisfiable CNFs, and super-polynomial lower bounds on the size of any tree-like proof system whose terms are degree-d polynomial inequalities for d ...
[לנוסח המלא]
Theory Seminar: Disjointness is hard in the multi-party number-on-the-forehead model
event speaker icon
עדי שרייבמן, מכון וייצמן למדע
event date icon
יום ראשון, 20.1.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
We show that disjointness requires randomized communication Omega(n^{1/2k}/{(k-1)2^{k-1}2^{2^{k-1}}) in the general k-party number-on-the-forehead model of complexity. The previous best lower bound was Omega((log n)/k-1). By results of Beame, Pitassi, and Segerlind, this implies 2^{n^{Omega(1)} lower bounds on the size of tree-like Lovasz-Schrijver proof systems needed to refute certain unsatisfiable CNFs, and super-polynomial lower bounds on the size of any tree-like proof system whose terms are degree-d polynomial inequalities for d = loglog n -O(logloglog n). ...
[לנוסח המלא]
Learning From Related Sources
event speaker icon
Koby Crammer
event date icon
יום שלישי, 15.1.2008, 14:30
event location icon
חדר 337-8 טאוב.
Recovering detailed 3D models of human shape and pose from images
event speaker icon
מיכאל בלאק
event date icon
יום שני, 14.1.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
Algorithms for video-based human motion capture typically assume the body shape is known a priori and is represented coarsely (e.g. using cylinders to model body parts). These body models stand in sharp contrast to the richly detailed 3D body models used by by animators. In this talk we describe a method for recovering detailed body shape models directly from images. Specifically, we represent the body using a recently proposed triangulated mesh model called SCAPE which ...
[לנוסח המלא]
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extra
event speaker icon
אמיר יהודיוף
event date icon
יום ראשון, 13.1.2008, 11:00
event location icon
חדר 337, בניין טאוב למדעי המחשב
In this paper we study multilinear formulas, monotone arithmetic circuits, maximal partition discrepancy, best partition communication complexity and mixed two source extractors. We will first define maximal partition discrepancy, and construct a function f that has exponentially small maximal partition discrepancy. We will then review several application of this construction: 1. The best partition communication complexity of f is \Theta(n). 2. It can be used to extract a linear number of almost perfect random bits ...
[לנוסח המלא]
Making large problems seem small: Convex duality in learning and inference
event speaker icon
Amir Globerson
event date icon
יום חמישי, 10.1.2008, 14:30
event location icon
חדר 337-8 טאוב.
Variational Image Restoration
event speaker icon
לאה בר
event date icon
יום חמישי, 10.1.2008, 11:00
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
This research concerns the image deblurring and noise removal problem in a variational framework. Energy functionals in this study consist of a fidelity term and a regularizer that is based on Mumford-Shah segmentation, such that the recovered image and its discontinuities set are simultaneously extracted in the course of the deblurring process. We first consider the image deblurring problem in the presence of Gaussian/impulsive noise and present a convergence result for the numerical scheme. Then, ...
[לנוסח המלא]
Worst-case complexity vs. average-case complexity
event speaker icon
Dan Gutfreund
event date icon
יום שלישי, 8.1.2008, 14:30
event location icon
חדר 337-8 טאוב.
The Role of Exemplars Comparison in Category Learning: The Emergence of Expertise
event speaker icon
רובי המר
event date icon
יום שלישי, 8.1.2008, 11:30
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
Recent studies stressed the importance of objects comparison for category learning. Recently we compared adults' capacity to learn new categorization principle in a condition in which few exemplars were identified as belong to the same category, versus a condition in which exemplars were identified as belong to different categories. We found that almost all participants learned the categorization rule quite efficiently in the Same-Class Exemplars condition. In contrast, when not provided with explicit directions, many ...
[לנוסח המלא]
Integrative Biology and System-wide analyses in Tumor Formation
event speaker icon
Sol Efroni
event date icon
יום ראשון, 6.1.2008, 14:30
event location icon
חדר 337-8 טאוב.
3D Virtual Colonoscopy with Computer-Aided Polyp Detection
event speaker icon
אריה קאופמן
event date icon
יום ראשון, 6.1.2008, 11:30
event location icon
חדר 1061, בניין מאייר, הפקולטה להנדסת חשמל
This talk describes 3D virtual colonoscopy (VC), a combination of computed tomography (CT) scanning and volume visualization technology, and is poised to become the procedure of choice in lieu of the conventional optical colonoscopy for mass screening for colon cancer. The talk further discusses a novel pipeline of computer-aided detection (CAD) of colonic polyps – the precursor of colorectal cancer – complementing VC. In VC, the patient abdomen is imaged by a helical CT scanner ...
[לנוסח המלא]
Cellular Developmental Decisions: From Single Cell Dynamics to Population Strategies
event speaker icon
Iftach Nachman
event date icon
יום רביעי, 2.1.2008, 14:30
event location icon
חדר 337-8 טאוב.
Sufficient conditions for local-to-global computations
event speaker icon
Tali Kaufman
event date icon
יום שלישי, 1.1.2008, 14:30
event location icon
חדר 337-8 טאוב.