High dimensional expansion is an emerging field in computer science with growing number of applications. These objects encapsulate in them an inherent local-to-global behavior. In this talk I will explain what are high dimensional expanders and overview some of their notable applications. I will focus on the strong relation between high dimensional expansion and local testability of error correcting codes.

 There are a number of approximation algorithms for NP-hard versions of low rank approximation, such as finding a rank-k matrix minimizing the sum of absolute values of differences to a given n x n matrix A, or more generally finding a rank-k matrix which minimizes the sum of p-th powers of absolute values of differences to A. Many of these algorithms are linear time columns subset selection algorithms, returning a subset of columns whose cost is no more than a poly(k) factor larger than the cost of the best rank-k matrix. The above error measures are special cases of the following general entrywise low rank approximation problem: given an arbitrary function f, find a rank-k matrix B which minimizes |A-B|_F. A natural question is which functions admit efficient approximation algorithms? Indeed, this is a central question of recent work studying generalized low rank models. 
 
In this work we give approximation algorithms for every function which is approximately monotone and satisfies an approximate triangle inequality, and we show both of these conditions are necessary. Further, our algorithm is efficient if the function admits an efficient approximate regression algorithm. Our approximation algorithms handle functions which are not even scaleinvariant, such as the Huber loss function, which we show have very different structural properties than norms, e.g., one can show the lack of scale-invariance causes any column subset selection algorithm to provably require a  factor sqrt{log n} larger number of columns than p-norms; nevertheless we design the first efficient column subset selection algorithms for such error measures.
 
Joint work with Zhao Song and Peilin Zhong

In the process of software development and maintenance, much efforts are invested in order to ensure that the product is as bug free as possible. Automating the repair process is highly desired. In this talk we present two approaches to automated program repair.
 
The first approach automatically repairs an erroneous program  using a predefined set of mutations to the code (e.g., replacing ‘+’ with ‘-‘ ;  ‘>’ with ‘<’, etc.).  The repair algorithm goes through generate-validate iterations, which involve fault localization mechanism in order to disregard sets of unsuccessful repairs. The approach guarantees soundness and completeness with respect to a bounded notion of correctness. 
 
The second approach intertwines compositional Assume-Guarantee verification with repair. Automata learning is used to verify the program or find an erroneous behavior. In the latter case, abduction assists in repairing the system by inferring new constraints that eliminate the error. Then, the verification proceeds for the repaired system.
 
This is a joint work with: Hadar Frenkel, Corina Pasareanu, Bat-chen Rothenberg and Sarai Sheinvald  
 

According to the law in Israel and US, you can use a drone inside the city or indoors only if its weight is less than 250 gram. Practically, this means that it can carry only a weak micro-computer and an RGB camera for autonomous navigation. This requires efficient real-time algorithms that do not exist today.
 
I will formalize some of these problems and suggest the first provably optimal and practical algorithms for some of them. This is by using modern optimization techniques such as core-sets, sketches, and Sum-Of-Squares (SOS). 
 
Demos on toy-drones inside and outside the lab will also be presented.
 
Based on papers in NeurIPS'19 and ICRA'19.

A tree cover of a metric space (X,d) is a collection of trees, so that every pair x,y ∈ X has a low distortion path in one of the trees. If it has the stronger property that every point x ∈ X has a single tree with low distortion paths to all other points, we call this a Ramsey tree cover. 
 We devise efficient algorithms to construct tree covers and Ramsey tree covers for general, planar and doubling metrics. We pay particular attention to the desirable case of distortion close to 1, and study what can be achieved when the number of trees is small.  In particular, our work shows a large separation between what can be achieved by tree covers vs. Ramsey tree covers. 
 This is joint work with Yair Bartal and Nova Fandina

The Gilbert-Varshamov bound tells us there are binary error correcting codes with distance 1/2-eps and relative rate O(eps^2). It has been long open to match these codes with explicit constructions. Recently, a construction with rate close to O(eps^2) and explicit encoding was found, but no explicit decoding is known to the code. 
 
One common technique for constructing such codes is using approximate error correction. In the talk I will explain what approximate error correction is, and survey several attempts at encoding and decoding such codes. As it turns out, many constructions use "double samplers" or variants of this object, and I will explain what double-samplers are, how they are related to the problem and what is known (and not known) about them.
 
The talk surveys many papers in the area and is also based on a recent paper with Dinur, Harsha, Kaufmann and Livni.