Theory of Computation Group

Blackboard, Winslow Homer (1877)

Schedule

We meet every other Monday at Check Point 280 . Talks begin at 13:10pm and last 1-2 hours.

Past talks

• Tzvika Geft (March 28, 2022) ---Distance-Optimal Multi-Agent Path Finding: New Hardness and Positive Results--- In Multi-Robot Motion Planning (MRMP) we aim to plan collision-free motion of robots from given start to target positions. Multi-Agent Path Finding (MAPF) is a discretized version of MRMP, where the robots are agents moving on a graph. In this two-part talk we will focus on the Distance-Optimal variant (DO-MAPF), in which the goal is to minimize the total distance traveled by the agents. Part I: DO-MAPF is known to be hard for planar graphs. However, the input graph is commonly further restricted be a 2D grid, since grids can model well-structured environments, such as warehouses. Following this gap, Banfi et al. (2017) posed the tractability on 2D grids as an open question. We settle it by showing that this case remains NP-hard. Our reduction uses simple gadgets and is the first linear one for the planar case. The latter results in an exponential lower bound for the problem's running time, assuming the Exponential Time Hypothesis. If time permits, I will also present related hardness results for quite restricted MRMP problem variants that are tractability frontiers, i.e., variants that are slight deviations from known tractable problems. Part II: Inspired by intuition from the hardness proof, we devised an efficient near-optimal heuristic algorithm for DO-MAPF. Experiments show that we quickly find solutions better than 1.05-optimal for grids that have up to 25% of their vertices occupied by agents. In this part, I will focus on the connection between our hardness and positive results. This talk is based on joint works with Yonatan Nakar (Part I), Noam Geller, Michael Bilevich (Part II) and Dan Halperin (both parts).
• Inbar Ben Yaacov (March 21, 2022) ---Candidate Tree Codes via Pascal Determinant Cubes--- A tree code is a combinatorial structure, introduced by Schulman in the 90s as a key ingredient in interactive coding schemes. Since then, the construction of tree codes has remained an elusive open problem. In this talk we will present a candidate for an asymptotically good tree code. Based on joint work with Gil Cohen and Anand Kumar Narayanan.
• Oded Nir (March 7, 2022) A secret-sharing scheme allows to distribute a secret s among n parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about s. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size 2^n−o(n) and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to 2^0994n+o(n), and this was further improved by several follow-ups accumulating in an upper bound of 15^n+o(n) (Applebaum and Nir, CRYPTO 2021). Following these advances, it is natural to ask whether these new approaches can lead to a truly sub-exponential upper-bound of 2^{n^{\eps}} for some constant \eps<1, or even all the way down to polynomial upper-bounds. In this talk we will give this question a negative answer by relating secret-sharing schemes to two computational models. The first will be formulas over slices, where each formula-gate can compute some slice function, and the second will be monotone real circuits (first introduced by Pudlák in 1997), where each gate is allowed to compute some arbitrary real-valued operator g : R × R → R that is monotone over the reals. Based on joint work with Benny Applebaum, Amos Beimel, Naty Peter and Toniann Pitassi.
• Shir Peleg January 3, 2022) Consider the following question: Assume the vertices of an expander graph are labeled by ±1. What "test" functions f:{±1}^t -> {±1} can or cannot distinguish t independent samples from those obtained by a random walk? In this talk, we will show both positive and negative results. We prove that all symmetric functions are fooled by random walks on expanders with a constant spectral gap. Furthermore, we show that functions computable by AC0 circuits are fooled by expanders with vanishing spectral expansion. As for lower bounds, we prove that the bound we obtain is optimal (up to a multiplicative constant). Furthermore, we prove that a random walk on expanders with a constant spectral gap does not fool AC0. This is based on a work of Cohen, Peri, and Ta-Shnma, and a joint work with Cohen, Minzer, Potechin and Ta-Shma.
• Esty Kelman (December 13, 2021) A Boolean function over the n-dimensional binary hypercube is a function of the form f:{0,1}^n -> {0,1}. The Total Influence of a Boolean function is defined as the number of bits on an average input, which, if flipped, would change the output. A fundamental question in the analysis of Boolean functions is how to characterize functions with a relatively small Total Influence. Kahn-Kalai-Linial and Friedgut studied this issue for K = o(log n) and showed that a function whose Total Influence is k depends on 2^{O(k)} variables. The holy grail of this field is the Fourier-Entropy Conjecture of Friedgut and Kalai that suggests a strengthening of these results, which remains meaningful even for k >= log n. Informally, this conjecture states that the Fourier transform of a function with Total Influence k concentrates on at most 2^{O(K)} distinct characters. In this talk, we will discuss up-to-date progress towards this conjecture. We will show that the Fourier Transform of functions whose Total Influence is at most k are concentrated on at most 2^{O(k*log k)} distinct Fourier coefficients. We will also mention some applications to learning theory and sharp thresholds. Based on joint work with Guy Kindler, Noam Lifshitz, Dor Minzer and Muli Safra.
• Aviv Bick (November 29, 2021) ---Distributed Zero-Knowledge Proofs Over Networks--- We define and study the notion of distributed zero-knowledge proofs, reconciling the computational notion of zero-knowledge with the communication-based paradigm of distributed graph algorithms. In our setting, a network of verifiers interacts with an untrusted prover to decide some distributed language. As is usually the case in distributed graph algorithms, we assume that the verifiers have local views of the network, and each only knows its neighbors. On the other hand, the prover is assumed to know the entire network graph, as well as any input that the verifier may possess. As in the centralized computational setting, the protocol we design should protect this knowledge. In particular, our protocol must protect the graph itself due to the dual role of the underlying graph in distributed graph algorithms, serving as both the communication topology and the input to the problem. We construct communication-efficient distributed zero-knowledge proofs for the 3-coloring problem, one of the poster children of computational zero-knowledge. We also give a general scheme for converting proof labeling schemes to distributed zero-knowledge protocols with related parameters. Our protocols combine ideas from computational complexity, distributed computing, and cryptography.
• Gal Maor (November 15, 2021) Spectral expanders are graphs that have many pseudorandom properties that make them central in theoretical computer science, with applications in coding, derandomization and more. The best spectral expanders are called Ramanujan graphs. In this talk we will describe the basic definitions of spectral expanders, give motivations to these definitions, and discuss the state of the art results for proving the existence (and explicitly constructing) Ramanujan graphs and their relaxations.
• Uri Meir (November 8, 2021) In the field of distribution testing, the underlying input is a distribution D over [n], that is guaranteed to either: (i) have a property P: that is, D belongs to a predefined set of distributions P , or (ii) be \eps-far from having the property: that is, SD(D, D') >= \eps, for any D' \in P. In the parallelized version of the problem k players are each given q = q(n,k,\eps) samples from D. Each player is allowed to send a concise message (say, a single bit) to a referee, who then needs to distinguish case (i) from case (ii) with error probability at most 1/3. In this talk, we will discuss lower bounds for parallelized uniformity testing (where the property being tested is whether D is uniform over [n]), focusing on a new method that uses (discrete) Fourier analysis. Based on joint works with Orr Fischer, Dor Minzer, and Rotem Oshman.
• Noam Mazor (October 25, 2021) Simple Constructions from Regular One-Way Functions Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). In order to implement them in practice, the efficiency of such constructions must be considered. The three major efficiency measures are: the seed length, the call complexity to the one-way function, and the adaptivity of these calls. In this talk we will see how to construct PRGs and UOWHFs from restricted classes of one-way functions.


• Uri Meir (September 14, 2021) In the field of distribution testing, the underlying input is a distribution D over [n], that is guaranteed to either: (i) have a property P: that is, D belongs to a predefined set of distributions P , or (ii) be \eps-far from having the property: that is, SD(D, D') >= \eps, for any D' \in P. A machine is then given q=q(n,\eps) independent samples from D, and needs to decide whether D has the property or is far from having it (with error probability at most 1/3). In this talk, we will discuss distribution testing in different models, and in particular a parallelized version: k players are each given q samples from D. Each player is allowed to send a concise message to a referee, who then needs to distinguish case (i) from case (ii) with error probability at most 1/3. Based on joint works with Orr Fischer, Dor Minzer, and Rotem Oshman.
• Orr Fisher (August 31, 2021) In a distributed computing model we have a network of n nodes, where each node is only aware of its immediate surroundings, and their goal is to solve some common task (e.g. color the network's nodes, compute the diameter, or determine any other graph related property). Graph decompositions lie near the heart and soul of algorithmic design of distributed computing protocols, and there is a strong symbiotic relationship between the design of new graph decompositions and understanding the complexities of fundamental problems in distributed computing. In this introductory talk, I define the LOCAL and CONGEST distributed models, discuss three types of graph decompositions ((d,c)-decomposition, expander decomposition, and forest decomposition), and show applications for each decomposition.
• Danny Vainshtein (August 10, 2021) Hierarchical Clustering (HC) trees have been widely accepted as a useful form of clustering data, resulting in a prevalence of adopting fields including phylogenetics, image analysis, bioinformatics and more. Recently, Dasgupta (STOC 16') initiated the analysis of these types of algorithms through the lenses of approximation. Later, the dual problem was considered by Moseley and Wang (NIPS 17') dubbing it the Revenue goal function. In this problem, given a nonnegative weight w_ij for each pair i,j∈[n]={1,2,…,n}, the objective is to find a tree T whose set of leaves is [n] that maximizes the function sum_ij w_ij*(n−|T_ij|), where |T_ij| is the number of leaves in the subtree rooted at the least common ancestor of i and j. In our work we consider the revenue goal function and prove the following results. First, we prove the existence of a bisection (i.e., a tree of depth 2 in which the root has two children, each being a parent of n/2 leaves) which approximates the general optimal tree solution up to a factor of 1/2 (which is tight). We then apply this result in order to prove a 0.585 approximation algorithm for the revenue problem. Second, we will prove a structural lemma allowing us to convert any HC tree to a tree with constant number of internal nodes while incurring an arbitrarily small loss. We then apply the lemma to obtain approximations arbitrarily close to 1, if not all weights are small (i.e., there exist constants eps, δ such that the fraction of weights smaller than δ, is at most 1 − eps); such instances encompass many metric based similarity instances, thereby improving upon prior work. Finally, time admitting, we will describe and analyze a family of hyperplane-based algorithms that handle the case of metric data in R^d. Based on joint work with Noga Alon, Yossi Azar, Vaggos Chatziafratis, Gui Citovsky, Claudio Gentile, Mohammad Mahdian, Cecilia Procopiuc, Anand Rajagopalan and Fabio Vitale.
• Tzvika Geft (August 3, 2021) Assembly planning is a fundamental problem in robotics and automation where the goal is to find a sequence of motions to assemble a product from its parts. A common approach for solving the problem is assembly-by-disassembly, whereby a disassembly sequence is obtained and then reversed. In this work we study a natural special case of the connected assembly partitioning problem, which arises in assembly-by-disassembly: Given a connected set A of unit grid squares in the plane, find a connected subset S of A such that A\S is also connected and S can be rigidly translated to infinity along a prescribed direction without colliding with A\S. We show that this seemingly simple problem is NP-complete, settling an open question posed by Wilson et al. (1995) a quarter of a century ago. We complement the hardness result with two positive results. First, we show that the problem is fixed-parameter tractable and present an O(2^k n^2)-time algorithm, where n=|A| and k=|S|. Second, we describe a special case of this problem where a connected partition can always be found in O(n) time. The talk will also explore the effect of other parameters on the hardness of assembly planning. Based on joint work with Pankaj K. Agarwal, Boris Aronov, and Dan Halperin, which appeared in SODA21.
• Oded Nir (July 27, 2021) A secret-sharing scheme allows to distribute a secret S among n parties such that only some predefined “authorized” sets of parties can reconstruct the secret, and all other “unauthorized” sets learn nothing about S. The collection of authorized/unauthorized sets can be captured by a monotone function f : {0, 1}^n → {0, 1}. For over 30 years, it was known that any monotone function can be realized by a secret-sharing scheme whose shares are of size 2^{n−o(n)} and until recently no better scheme was known. In a breakthrough result Liu and Vaikuntanathan (STOC 2018) have reduced the share size to 2^{0.994n+o(n)}, and a following line of work showed how to bring the share size down to 1.5^{n+o(n)}=2^{0.585n+o(n)}. In this talk we will discuss the latest pieces of the puzzle which allow for a scheme with share size 1.5^{n+o(n)}. We will talk about schemes for some natural families of functions: slices functions, monotone k-DNFs and k-CNFs, and see how they can be composed together to create schemes for any function. Based on joint work with Benny Applebaum.
• Esty Kelman (July 20, 2021) A Boolean function over the n-dimensional hypercube is simply a function f:{0,1}^n->{0,1}. A fundamental result in the field is the KKL Theorem [STOC'88], named after Kahn, Kalai, and Linial. The theorem roughly states that every Boolean function f on n variables has a single variable with a non-trivial influence on the value of f. The theorem was originally proved using Fourier analysis and other novel techniques that are still in wide use today. One particular ingredient is the hypercontractive inequality, a tool that is sometimes considered a bit counter-intuitive and unfriendly to use. In this work we establish an alternative proof technique for the KKL Theorem, as well as other related results, using random restrictions (i.e., randomly fixing certain inputs) and the Log-Sobolev inequality. In the talk we will demonstrate our proof by proving a special case of the KKL Theorem. Based on a joint work with Subhash Khot, Guy Kindler, Dor Minzer and Muli Safra
• Tal Roth (July 13, 2021) Communication complexity has become an influential field in proving lower bounds in many applications, such as distributed computing, computational complexity, cryptography, streaming and many more. In communication complexity, using Information theory to prove lower bounds is becoming more and more popular. In this talk we will discuss why communication complexity is influential to other fields, why information theory is useful, and how the two intersect via the problem of Set disjointness. This talk is based on joint work with Nachum Dershowitz and Rotem Oshman.
• Ori Sberlo (June 29, 2021) The talk will review derandomization of log space algorithms, namely whether any randomized log space algorithm can be simulated with less randomness or ideally replaced with a deterministic one. We will survey the highlight results while putting emphasis on the ideas and techniques.