Gilad Tsur

I'm a postdoc at Tel-Aviv University, hosted by Benny Appelbaum and Shai Avidan

Untill recently I was a postdoc at the Weizmann Institute of Science, hosted by Robert Krauthgamer.

Selected Publications

• Itai Benjamini, Igor Shinkar and Gilad Tsur Acquaintance Time of a Graph.
  2013.
  

  We define the following parameter of connected graphs. For a given graph $G = (V,E)$ we place one agent in each vertex $v \in V$. Every pair of agents sharing a common edge are declared to be acquainted. In each round we choose some matching of $G$ (not necessarily a maximal matching), and for each edge in the matching the agents on this edge swap places. After the swap, again, every pair of agents sharing a common edge are acquainted, and the process continues. We define the \emph{acquaintance time} of a graph $G$, denoted by $\AC(G)$, to be the minimal number of rounds required until every two agents are acquainted.
  We first study the acquaintance time for some natural families of graphs including the path, expanders, the binary tree, and the complete bipartite graph. We also show that for all functions $f : \N \to \N$ satisfying $1 \leq f(n) \leq n^{1.5}$ there is a family of graphs $\{G_n = (V_n,E_n)\}_{n \in \N}$ with $|V_n| = n$ such that $\AC(G_n) = \Theta(f(n))$. We also prove that for all $n$-vertex graphs $G$ we have $\AC(G) = O\left(\frac{n^2}{\log(n)/\log\log(n)}\right)$, thus improving the trivial upper bound of $O(n^2)$ achieved by sequentially letting each agent perform depth-first search along some spanning tree of $G$.
  Studying the computational complexity of this problem, we prove that for any constant $t \geq 1$ the problem of deciding that a given graph $G$ has $\AC(G) \leq t$ or $\AC(G) \geq 2t$ is $\NP$-complete. That is, $\AC(G)$ is $\NP$-hard to approximate within multiplicative factor of 2, as well as within any additive constant factor.
  On the algorithmic side, we give a deterministic polynomial time algorithm that given an $n$-vertex graph $G$ distinguishes between the cases $\AC(G)=1$ and $AC(G) \geq n-O(1)$. We also give a randomized polynomial time algorithm that distinguishes between the cases $\AC(G)=1$ and $AC(G) = \Omega(\log(n))$ with high probability.

  @misc{BST,
    author    = {Itai Benjamini and
  			Igor Shinkar  and
  			Gilad Tsur},
    title     = {Acquaintance Time of a Graph}
  }
  

  abstract bib for now
  
  
  

• Simon Korman, Daniel Reichman, Gilad Tsur and Shai Avidan. FAsT-Match: Fast Affine Template Matching. CVPR 2013. [Project web page, including article and code.]
  

  FAsT-Match is a fast algorithm for approximate template matching under 2D affine transformations that minimizes the Sum-of-Absolute-Differences (SAD) error measure. There is a huge number of transformations to consider but we prove that they can be sampled using a density that depends on the smoothness of the image. For each potential transformation, we approximate the SAD error using a sublinear algorithm that randomly examines only a small number of pixels. We further accelerate the algorithm using a branch-and-bound scheme. As images are known to be piecewise smooth, the result is a practical affine template matching algorithm with approximation guarantees, that takes a few seconds to run on a standard machine. We perform several experiments on three different datasets, and report very good results. To the best of our knowledge, this is the first template matching algorithm which is guaranteed to handle arbitrary 2D affine transformations.

  @inproceedings{cvpr2013Fast_Match,
  	title={Fast-Match: Fast Affine Template Matching},
  	author={Korman, Simon and Reichman, Daniel and Tsur, Gilad and Avidan, Shai},
  	booktitle={Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference on},
  	pages={1940--1947},
  	year={2013},
  	organization={IEEE}
  } 
  

  abstract bib for CVPR extended abstract
  
  
  

• Simon Korman, Daniel Reichman and Gilad Tsur. Tight Approximation of Image Matching .
  2011.
  

  In this work we consider the image matching problem for two grayscale n × n images, M₁ and M₂ (where pixel values range from 0 to 1). Our goal is to find an affine transformation T that maps pixels from M₁ to pixels in M₂ so that the differences over pixels p between M₁(p) and M₂(T(p)) is minimized. Our focus here is on sublinear algorithms that give an approximate result for this problem, that is, we wish to perform this task while querying as few pixels from both images as possible, and give a transformation that comes close to minimizing the difference. We give an algorithm for the image matching problem that returns a transformation T which minimizes the sum of differences (normalized by n2) up to an additive error of ε and performs Õ(n/ε ²) queries. We give a corresponding lower bound of (n) queries showing that this is the best possible result in the general case (with respect to n and up to low order terms). In addition, we give a signiffcantly better algorithm for a natural family of images, namely, smooth images. We consider an image smooth when the total difference between neighboring pixels is O(n). For such images we provide an approximation of the distance between the images to within an additive error of ε using a number of queries depending polynomially on 1/ε and not on n. To do this we first consider the image matching problem for 2 and 3-dimensional binary images, and then reduce the grayscale image matching problem to the 3-dimensional binary case.

  @misc{KRT,
    author    = {Simon Korman and
  			Daniel Reichman  and
  			Gilad Tsur},
    title     = {Tight Approximation of Image Matching}
  }
  

  abstract bib for now
  
  
  

• Dana Ron and Gilad Tsur. On Approximating the Number of Relevant Variables in a Function .
  Random 2011.
  

  In this work we consider the problem of approximating the number of relevant variables in a function given query access to the function. Since obtaining a multiplicative factor approximation is hard in general, we consider several relaxations of the problem. In particular, we consider relaxations in which we have a promise that the function belongs to a certain family of functions (e.g., linear functions), and we consider a relaxation of the property testing variant of the problem. In the latter relaxation the task is to distinguish between the case that the number of relevant variables is at most k, and the case in which it is far from any function in which the number of relevant variable is more than (1 + γ)k for a parameter γ. We give both upper bounds and almost matching lower bounds for the relaxations we study.

  @inproceedings{DBLP:conf/approx/RonT11,
    author    = {Dana Ron and
                 Gilad Tsur},
    title     = {On Approximating the Number of Relevant Variables in a Function},
    booktitle = {APPROX-RANDOM},
    year      = {2011},
    pages     = {676-687}
  }
  

  abstract bib for Random extended abstract
  
  
  

• Dana Ron and Gilad Tsur. Testing Properties of Sparse Images .
  FOCS 2010.
  

  We initiate the study of testing properties of images that correspond to sparse 0/1-valued matrices of size n × n. Our study is related to but different from the study initiated by Raskhodnikova (Proceedings of RANDOM, 2003 ), where the images correspond to dense 0/1-valued matrices. Speciffically, while distance between images in the model studied by Raskhodnikova is the fraction of entries on which the images differ taken with respect to all n² entries, the distance measure in our model is defined by the fraction of such entries taken with respect to the actual number of 1's in the matrix. We study several natural properties: connectivity, convexity, monotonicity, and being a line. In all cases we give testing algorithms with sublinear complexity, and in some of the cases we also provide corresponding lower bounds.

  @inproceedings{{DBLP:conf/focs/TsurR10,
    author    = {Dana Ron and
                 Gilad Tsur},
    title     = {Testing Properties of Sparse Images},
    booktitle = {FOCS},
    year      = {2010},
    pages     = {468-477}
  }
  

  abstract bib for FOCS extended abstract
  
  
  

• Dana Ron and Gilad Tsur. Testing Computability by Width-Two OBDD.
  Some of the work was presented in Random 2009.
  

  Property testing is concerned with deciding whether an object (e.g. a graph or a function) has a certain property or is "far" (for a prespecified distance measure) from every object with that property. In this work we consider the property of being computable by a read-once width-2 Ordered Binary Decision Diagram (OBDD), also known as a branching program, in two settings. In the first setting the order of the variables is fixed and given to the algorithm, while in the second setting it is not fixed. That is, while in the first setting we should accept a function f if it is computable by a width-2 OBDD with a given order of the variables, in the second setting we should accept a function f if there exists an order of the variables according to which a width-2 OBDD can compute f. Width-2 OBDDs generalize two classes of functions that have been studied in the context of property testing - linear functions (over GF(2) ⁿ) and monomials. In both these cases membership can be tested by performing a number of queries that is independent of the number of variables, n (and is linear in 1/ε, where ε is the distance parameter). In contrast, we show that testing computability by width-2 OBDDs when the order of variables is fixed and known requires a number of queries that grows logarithmically with n (for a constant ε), and we provide an algorithm that performs Õ(log (n)/ε) queries. For the case where the order is not fixed, we show that there is no testing algorithm that performs a number of queries that is sublinear in n.

  @inproceedings{{DBLP:conf/approx/RonT09,
    author    = {Dana Ron and
                 Gilad Tsur},
    title     = {Testing Computability by Width Two OBDDs},
    booktitle = {APPROX-RANDOM},
    year      = {2009},
    pages     = {686-699}
  }
  

  abstract bib for Random extended abstract