Speaker: Yaniv Sabo

M.Sc. student under the supervision of Prof. Dana Ron

Wednesday, January 11^th 2017 at 15:30

Room 011, Kitot Bldg., Faculty of Engineering

On finding small subgraphs in bounded-degree graphs

Abstract

We study the problem of finding a copy of a subgraph H in a graph G that is far from being free of having copies of H. We consider this problem in the bounded-degree graphs model. In this model, each of the n vertices has at most d neighbors, and an algorithm is allowed to make queries regarding the neighbors of vertices in the graph. The graph is said to be $\epsilon$-far from being H-free if more than $\epsilon$dn of its edges must be deleted to make the graph free from having copies of H.

We present an algorithm for finding a copy of H in graphs that are e-far from being H-free and have bounded (constant) treewidth. This algorithm makes a number of queries that is polynomial in 1/$\epsilon$, the size of H and the degree bound d. The complexity of the algorithm is independent of the number of vertices, n.

We also present an algorithm for the special case in which H is a path of length k. Our algorithm uses specific properties of graphs that are far from having k-paths. Finding k-paths was previously studied by Reznik (Master's thesis, Weizmann Institute of Science, 2011). Reznik gave an algorithm for the case in which G is cycle-free, where the query complexity of the algorithm is polynomial in k, d and 1/$\epsilon$. We propose a conjecture that, if proven to be true, implies that our algorithm works for any graph that is $\epsilon$-far from being k-path free with query complexity polynomial in k, d, and 1/$\epsilon$. As a sanity check, we establish the conjecture for cycle-free graphs.

(The talk will be given in English)

Speaker: Dr. Ron Rothblum

Weizmann Institute

Monday, January 2nd, 2017 15:00 - 16:00

Room 011, Kitot Bldg., Faculty of Engineering

How to prove the correctness of computations

Abstract

Efficient proof verification is at the heart of the study of computation. Seminal results such as the IP=PSPACE Theorem [LFKN92,Shamir92] and the PCP theorem [AS92,ALMSS92] show that even highly complicated statements can be verified extremely efficiently. We study the complexity of proving statements using interactive protocols. Specifically, what statements can be proved by a polynomial-time prover to a super-efficient verifier. Our main results show that these proof-system are remarkably powerful: it is possible to prove the correctness of general computations such that (1) the prover runs in polynomial-time, (2) the verifier runs in linear-time (and in some conditions in sublinear-time) and (3) the interaction consists of only a constant number of communication rounds (and in some settings just a single round). These proof-systems are motivated by, and have applications for, delegating computations in a cloud computing environment, and guaranteeing that they were performed correctly.

(The talk will be given in English)

Speaker:     Dr. Daniel Soudry
                    Department of Statistics, Columbia University

Wednesday, January 18^th, 2017
15:00 - 16:00

Room 011, Kitot Bldg., Faculty of Engineering

Resource Efficient deep Learning

Abstract

Background: The recent success of deep neural networks (DNNs) relies on large computational resources (memory, energy, area and processing power). These resources pose a major bottleneck in our ability to train better models, and to use these models on low power devices (e.g., mobile phones). However, current generation DNNs seem tremendously wasteful, especially in comparison to the brain (which consumes only 12W). For example, typical DNNs use 32bit floating point operations, while the brain typically operates using binary spikes and with limited synaptic precision. Achieving such low precision in DNNs can significantly improve memory, speed and energy. However, until recently, 8 bits appeared to be the lowest possible limit.

Results: We show that it is possible to significantly quantize (even down to 1 bit) the activations and weights of DNNs trained by a variant of the backpropagation algorithm, while preserving good performance on various benchmarks (e.g., MNIST, ImageNet). Interestingly, the algorithm originated from first principles: we developed a closed form analytical approximation to the Bayes rule update of the posterior distribution of the binary DNN weights. At run-time, such a binarized DNN requires 32-fold less memory, is 7 times faster (using dedicated GPU kernels), and is at least 10-fold more energy efficient (using dedicated hardware). This can enable the use of trained DNNs in low power devices. Additional benefits are expected at train-time by further quantizing the gradients, potentially allowing larger and more sophisticated models to be trained.