{"id":130,"date":"2017-12-04T13:45:14","date_gmt":"2017-12-04T11:45:14","guid":{"rendered":"http:\/\/www.eng.biu.ac.il\/gellesr\/?page_id=130"},"modified":"2020-10-11T20:34:46","modified_gmt":"2020-10-11T17:34:46","slug":"theory-group","status":"publish","type":"page","link":"https:\/\/www.eng.biu.ac.il\/gellesr\/theory-group\/","title":{"rendered":"Theory Group"},"content":{"rendered":"<p>Starting 2017 I've been running the CE TheoryGroup meetings.<br \/>\nThe main scope is Cryptography, Coding, and Algorithms, but we are always happy to learn about other tangential topics.<\/p>\n<h4>2020-2021<\/h4>\n<p>The seminar this year is run by Dr. Manuj Mukherjee (<span class=\" aw5Odc\">mukherm<\/span><span class=\" aw5Odc\">@biu.ac.il)<\/span>. See the new <a href=\"https:\/\/sites.google.com\/view\/bar-ilan-theory-seminar\/fall-2020-2021\">Seminar's webpage<\/a>.<\/p>\n<h4>2018-2019<\/h4>\n<p>We meet every other Monday, <del datetime=\"2019-03-15T19:59:44+00:00\">12:00-13:00<\/del>\u2192<strong>12:30-13:30<\/strong>, room 431 (Engineering Building, Bar-Ilan campus, Ramat-Gan).<\/p>\n<p><!-- End Of Title --><\/p>\n<table>\n<tbody>\n<tr>\n<td><strong>Date<\/strong><\/td>\n<td><strong>Speaker<\/strong><\/td>\n<td><strong>Topic<\/strong> (hover for an abstract)<\/td>\n<\/tr>\n<tr>\n<td>27\/5\/2019<\/td>\n<td>Ouri Poupko (Weizmann)<\/td>\n<td><span title=\"Bringing democracy into the digital realm, or more precisely, using digital foundations for building better democracies, the first question we ask is the identification of individuals and communities. We choose to answer this question using graph connectivity. Next, we look at the rise of distributed ledger technologies and ask whether, and to what extent, we can use these technologies for implementing democracy on the digital media (e-Democracy). We propose a variant of the Byzantine Fault Tolerance protocol, based on a social web of trust, as a foundation for a democratic and distributed community governance mechanism that allows a new community to define itself from root grass, without any centralized authority gaining control over the process, not even the founders.\">A distributed ledger protocol for e-Democracy<\/span><\/td>\n<\/tr>\n<tr>\n<td>13\/5\/2019<\/td>\n<td>Amir Leshem<\/td>\n<td><span title=\"in this talk i will review some results on channel allocation techniques in wireless channels. \">Matching in wireless communication :<br \/>\nFrom stabe marriage to Game of Thrones dynamics. <\/span><\/td>\n<\/tr>\n<tr>\n<td>29\/4\/2019<\/td>\n<td>Rishabh Bhadauria<\/td>\n<td><span title=\"In this work, we explore how non-equivocation mechanism can be used to solve various problems in distributed computing. We consider a setting with n parties and a computationally-bounded adversary that can control up to t parties in a Byzantine fashion. One of the main challenges in dealing with a Byzantine adversary is that corrupt parties can equivocate, i.e. send contradictory messages to different parties. In order to deal with this challenge, Chun et al. introduced a mechanism for restricting the equivocating behavior of Byzantine adversary. This is termed as non-equivocation mechanism. Clement et al.(PODC 2012) showed how to convert any crash-tolerant distributed protocol to Byzantine-tolerant distributed protocol. More specifically, they used non-equivocation mechanism along with transferrable authentication in order to solve the Asynchronous Byzantine Agreement (ABA) problem from Asynchronous Crash-tolerant Agreement; also, they improved the resilience from t &lt; n\/3 to t &lt; n\/2. Using a similar non-equivocation mechanism, Backes et al.(PODC 2014) proposed to also improve the resilience of Asynchronous Multi-party Computation (AMPC) protocol from t &lt; n\/3 to t &lt; n\/2.\n\nWe revisit their work and show that it is impossible to solve the ABA problem in t &lt; n\/2 setting with Byz-Validity (if all honest parties have input \u2019v\u2019, then the output will also be \u2019v\u2019). This impossibility raises questions regarding the feasibility of another important primitive - Agreement of Common Subset (ACS). The constructions of ACS use ABA as a building block. Since ABA with Byz-Validity is impossible in our setting, the question of whether ACS is possible is left open. We first show that constructing ACS in a similar way as before, replacing ABA with an ABA protocol with weaker validity condition will not work. We then propose an alternate construction of ACS using ABA with weaker validity condition.\n\">Asynchronous Secure Distributed Computing using Transferrable Non-equivocation<\/span><\/td>\n<\/tr>\n<tr>\n<td>15\/4\/2019<\/td>\n<td><strong><span style=\"color: #ff0000\">Passover<\/span><\/strong><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>1\/4\/2019<\/td>\n<td>Rotem Oshman (TAU)<\/td>\n<td><span title=\"Property testing is a paradigm that evolved in order to deal with huge amounts of data: we have some very large input, which we cannot afford to examine in its entirety, but we would still like to learn something about it. Since we cannot read the entire input, we cannot make fine-grained decisions that depend on individual bits of the input. Nevertheless, we can make approximate decisions: we can tell whether our input satisfies some property, or whether it is far from satisfying the property, in the sense that we would need to change a large fraction of the input to make it satisfy the property.\n\nThe property-testing approach seems especially suited for distributed networks, where, due to memory, energy and communication constraints, each computing unit can typically observe only a small part of the network and the input to the computation; recent work has shown that indeed, there exist efficient distributed testers for problems that are difficult to solve exactly.\n\nIn this talk we will survey two problems where distributed property testing was recently shown to be helpful: first, the subgraph-freeness problem, where we are asked whether the network graph contains a copy of a specific constant-sized subgraph (e.g., a triangle) or not; and second, uniformity testing, where the network nodes take samples from some unknown distribution, and the goal is to determine whether the input distribution is uniform or not. (No prior background is assumed.)\">Distributed Property Testing<\/span><\/td>\n<\/tr>\n<tr>\n<td>18\/3\/2019<\/td>\n<td>Zvika Lotker<\/td>\n<td><span title=\"Conflict is an essential element of a good story. Conflict is used not only as a device by storytellers (see \\cite{abbott2008cambridge}), but in many other contexts as well. In science and engineering, there is frequently the need to partition a space or a network into two parts. In computer science, this is called the divide and conquer method, in reference to Julius Caesar. In this talk, I will discuss how to partition a network using conflicts. And how generalization simplifies our understating and writing.\">From voting to Conflictation Journey through generalization and simplification<\/span><\/td>\n<\/tr>\n<tr>\n<td>4\/3\/2019<\/td>\n<td>Itay Tsabary (Technion)<\/td>\n<td><span title=\"Blockchain-based cryptocurrencies secure a decentralized consensus protocol by incentives. The protocol participants, called miners, generate (mine) a series of blocks, each containing monetary transactions created by system users. As incentive for participation, miners receive newly minted currency and transaction fees paid by transaction creators. Blockchain bandwidth limits lead users to pay increasing fees in order to prioritize their transactions. However, most prior work focused on models where fees are negligible. In a notable exception, Carlsten et al. [17] postulated that if incentives come only from fees then a mining gap would form~--- miners would avoid mining when the available fees are insufficient. In this work, we analyze cryptocurrency security in realistic settings, taking into account all elements of expenses and rewards. To study when gaps form, we analyze the system as a game we call the gap game. We analyze the game with a combination of symbolic and numeric analysis tools in a wide range of scenarios. Our analysis confirms Carlsten et al.'s postulate; indeed, we show that gaps form well before fees are the only incentive, and analyze the implications on security. Perhaps surprisingly, we show that different miners choose different gap sizes to optimize their utility, even when their operating costs are identical. Alarmingly, we see that the system incentivizes large miner coalitions, reducing system decentralization. We describe the required conditions to avoid the incentive misalignment, providing guidelines for future cryptocurrency design. \n\nhttps:\/\/dl.acm.org\/citation.cfm?id=3243737\">The Gap Game<\/span><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">21\/1-18\/2<\/td>\n<td style=\"width: 204.383px;height: 32px\"><strong><span style=\"color: #ff0000\">Spring Break<\/span><\/strong><\/td>\n<td style=\"width: 343.1px;height: 32px\"><\/td>\n<\/tr>\n<tr>\n<td>7\/1\/2019<\/td>\n<td>Naama Ben-David (CMU)<\/td>\n<td><span title=\"The shared-memory and message-passing models have traditionally been studied separately in the distributed computing community. However, recent trends in hardware have led to machines that may use both shared memory and message-passing primitives. Motivated by these trends, we consider a hybrid message-and-memory model that allows programs to both share memory and pass messages.\n\nWe show that the message-and-memory model can leverage the shared memory to become more powerful than the message-passing model in isolation.\n\nIn this talk, I will exemplify the power of a message-and-memory network by considering the classic consensus problem. I will show that such a network can tolerate more failures when solving consensus than a purely message-passing one. This is true even when limiting shared memory communication to be only between neighbors in a sparse shared memory graph, rather than between every pair of processes. In particular, I will show that graphs with high expansion properties provide a good trade-off between scalability and fault-tolerance in this context, and prove upper and lower bounds on the fault-tolerance of a message-and-memory network.\n\nBased on joint work with Marcos Aguilera, Irina Calciu, Rachid Guerraoui, Erez Petrank, and Sam Toueg.\n\n\">Passing Messages while Sharing Memory<\/span><\/td>\n<\/tr>\n<tr>\n<td>24\/12\/2018<\/td>\n<td>Zachi Tamo (TAU)<\/td>\n<td><span title=\"It is a well known fact that any k evaluation points of a polynomial P(x) of degree less than k suffice to calculate (recover) the evaluation at any other point. Motivated by applications to error correcting codes for storage systems, we consider the following question.  Is it possible to recover P (\u03b1) for some \u03b1, by observing some partial information of d \u2265 k evaluation points P (\u03b1_i)? More precisely, the observed partial information is f_i (P (\u03b1_i)) for  some function f_i which is not necessarily injective, and the goal is to perform the recovery, while minimizing the total amount of observed partial information.\">Optimal repair of polynomials: Achieving the cut-set bound<\/span><\/td>\n<\/tr>\n<tr>\n<td>10\/12\/2018<\/td>\n<td>Toni B\u00f6hnlein<\/td>\n<td><span title=\"In a Stackelberg pricing game, a distinguished player, the &#096;leader&#096;, chooses prices for a set of items, and the other players, the &#096;followers&#096;, each seek to buy a minimum cost feasible subset of the items. The goal of the leader is to maximize her revenue, which is determined by the sold items and their prices. Most previously studied cases of such games can be captured by a combinatorial model where we have one follower, a base set of items, some with fixed prices, some priceable, and constraints on the subsets that are feasible for the follower. We are interested in computing revenue maximizing prices for the leader. \n\nIn my talk, I give a survey on Stackelberg pricing games ranging from ptime algorithms to hardness, approximation and fixed-parameter results.\">Stackelberg pricing games<\/span><\/td>\n<\/tr>\n<tr>\n<td>26\/11\/2018<\/td>\n<td>Amir Leshem - <strong><span style=\"color: #ff0000\">Cancelled<\/span><\/strong><\/td>\n<td><span title=\"in this talk i will review some results on channel allocation techniques in wireless channels. \">Matching in wireless communication :<br \/>\nFrom stabe marriage to Game of Thrones dynamics. <\/span><\/td>\n<\/tr>\n<tr>\n<td>12\/11\/2018<\/td>\n<td>Eylon Yogev (Technion)<\/td>\n<td><span title=\"A cycle cover of a bridgeless graph G is a collection of simple cycles in G such that each edge appears on at least one cycle. The common objective in cycle cover computation is to minimize the total lengths of all cycles. Motivated by applications to distributed computation, we introduce the notion of \\emph{low-congestion} cycle covers, in which all cycles in the cycle collection are both \\emph{short} and nearly \\emph{edge-disjoint}. Formally, a (d,c)-cycle cover of a graph G is a collection of cycles in G in which each cycle is of length at most d and each edge participates in at least one cycle and at most c cycles. \n\nA-priori, it is not clear that cycle covers that enjoy both a small overlap and a short cycle length even exist, nor if it is possible to efficiently find them. Perhaps quite surprisingly, we prove the following: Every bridgeless graph of diameter D admits a (d,c)-cycle cover where d = O(D) and c=O(1). That is, the edges of G can be covered by cycles such that each cycle is of length at most O(D) and each edge participates in at most O(1) cycles. These parameters are existentially tight up to polylogarithmic terms.\n\nWe demonstrate the usefulness of low congestion cycle covers in different settings of resilient computation. For instance, we consider a Byzantine fault model where in each round, the adversary chooses a single message and corrupt in an arbitrarily manner. We provide a compiler that turns any r-round distributed algorithm for a graph G with diameter D, into an equivalent fault tolerant algorithm with r poly(D) rounds.\">Low Congestion Cycle Covers and Their Applications<\/span><\/td>\n<\/tr>\n<tr>\n<td>29\/10\/2018<\/td>\n<td>Eyal Ronen (Weizmann)<\/td>\n<td><span title=\"In this talk, we describe a new type of attack on IoT devices, which exploits their ad-hoc networking capabilities via the ZigBee wireless protocol, and thus cannot be monitored or stopped by standard Internet-based protective mechanisms. \n\nWe developed and verified the attack using the Philips Hue smart lamps as a platform. We exploited a major bug in the implementation of the ZigBee Light Link protocol to take over preinstalled lightbulbs. We also used a new version of a side channel attack to extract the global AES-CCM key (for each device type) that Philips uses to encrypt and authenticate new firmware. By plugging in a single infected lamp anywhere in the city, an attacker can create a chain reaction in which a worm can jump from any lamp to all its physical neighbors, and thus stealthily infect the whole city if the density of smart lamps in it is high enough. This makes it possible to turn all the city's smart lights on or off, to brick them, or to use them to disrupt nearby WiFi transmissions.\">IoT Goes Nuclear: Creating a ZigBee Chain Reaction<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h4><\/h4>\n<h4>2017-2018<\/h4>\n<p>We meet every other Monday, 16:00-17:00, room 431 (Engineering Building, Bar-Ilan campus, Ramat-Gan).<\/p>\n<p><!-- End Of Title --><\/p>\n<table style=\"width: 689px;height: 323px\">\n<tbody>\n<tr style=\"height: 26.1834px\">\n<td style=\"width: 107.517px;height: 26.1834px\"><strong>Date<\/strong><\/td>\n<td style=\"width: 204.383px;height: 26.1834px\"><strong>Speaker<\/strong><\/td>\n<td style=\"width: 343.1px;height: 26.1834px\"><strong>Topic<\/strong> (hover for an abstract)<\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">18\/6\/2018<\/td>\n<td style=\"width: 204.383px;height: 32px\">Hillel Kugler<\/td>\n<td style=\"width: 343.1px;height: 32px\"><span title=\"Temporal Logic is an established formalism to specify and reason about the dynamics of complex reactive systems. The standard definition provides semantics of temporal logic over infinite paths. I will introduce temporal logic and discuss the semantics of temporal logics over truncated paths - paths that correspond to pre fixes of computations of the system at hand. In recent work we explore providing semantics for temporal logics on other types of incomplete paths, namely incomplete ultimately periodic paths and segmentally broken paths. I will also briefly review usages of temporal logic reasoning in system biology, and explore whether system biology can benefit from the suggested extensions. Joint work with Dana Fisman (BGU)\">Temporal Reasoning on Incomplete Paths<\/span><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">4\/6\/2018<\/td>\n<td style=\"width: 204.383px;height: 32px\">Mor Lilintal<\/td>\n<td style=\"width: 343.1px;height: 32px\"><span title=\"Secure computation enables to a set of parties to compute some function on their private inputs without revealing any information except for the output of the function. The common approach in secure two-party computation is to represent the desired functionality as a Boolean circuit. However, this approach falls short when the computation involves access to a large memory, since each memory access must be translated into a linear scan of the memory. An alternative and more appealing model of computation is the RAM model, that yields sublinear computation overhead in the input size. Amongst previous work, only [GHL+14,GLOS15,GLO15] are constant round but induce impractical overhead, mainly due to a generic protocol for the memory setup. In this work, we design new constant-round protocols with better memory management. Our constructions combine an optimized variant of the garbled RAM due to Garg et al. [GLOS15] with the 'simple ORAM' of Chung et al. [CP13]. This is a joint work with Prof. Carmit Hazay.\">Improved Constant Round 2PC for RAM Programs<\/span><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">21\/5\/2018<\/td>\n<td style=\"width: 204.383px;height: 32px\">Shavuot Holiday - <strong>No Talk<\/strong><\/td>\n<td style=\"width: 343.1px;height: 32px\"><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">9\/5\/2018<\/td>\n<td style=\"width: 204.383px;height: 32px\">Vassilis Zikas (U. Edinburgh)<br \/>\n(consolidated with Colloquium)<\/td>\n<td style=\"width: 343.1px;height: 32px\"><span title=\"The core of the blockchain research addresses questions related to the security (or insecurity) of various blockchain constructions, and\/or investigates ways in which blockchains can be used as a monetary system. Interestingly, blockchains also provide means for better cryptography. In this talk I will discuss the core cryptographic goals that blockchains achieve, and how blockchains can be used as an enabler\/catalyst to improve the security of cryptographic distributed computation protocols. I will show how to distill the core functionality of blockchains in a global transaction-ledger resource and discuss how various applications can benefit from the existence of such a ledger.\">Cryptography on the Blockchain<\/span><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">23\/4\/2018<\/td>\n<td style=\"width: 204.383px;height: 32px\"><span style=\"color: #000000\">Hila Rabii<\/span><\/td>\n<td style=\"width: 343.1px;height: 32px\"><span title=\"Robust codes are codes that can detect any nonzero error e with probability 1-Q(e) &gt; 0. This property makes them useful in protecting hardware systems from fault injection attacks which cause an arbitrary number of bit flips. The talk presents a new construction of non-linear robust q-ary codes with q=2^m and an error correction capability. The codes are built upon systematic linear codes [n,k,d]_q whereas the n-k redundant symbols that were originally allocated to increase the minimum distance of the code are modified to provide both correction capability and robustness. The error masking probability of the codes is Q(e) upper bounded by 2\/q for odd values of m and by 4\/q for even m. Hence, they are more effective in detecting maliciously injected errors and have a higher code rate than codes obtained by concatenation of a linear error correcting code with a security oriented code.\">A New Class of Security Oriented Error Correcting Robust Codes<\/span><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">9\/4\/2018<\/td>\n<td style=\"width: 204.383px;height: 32px\"><span style=\"color: #000000\">Carmit Hazay<\/span><\/td>\n<td style=\"width: 343.1px;height: 32px\"><span title=\"In this work we study the problem of private set-intersection in the multi-party setting and design two protocols with the following improvements compared to prior work. First, our protocols are designed in the so-called star network topology, where a designated party communicates with everyone else, and take a new approach of leveraging the 2PC protocol of \\cite{FreedmanNP04}. This approach minimizes the usage of a broadcast channel, where our semi-honest protocol does not make any use of such a channel and all communication is via point-to-point channels. In addition, the communication complexity of our protocols scales with the number of parties. More concretely, (1) our first semi-honest secure protocol implies communication complexity that is linear in the input sizes, namely O((\\sum_{i=1}^n m_i)\\cdot\\kappa) bits of communication where \\kappa is the security parameter and m_i is the size of P_i's input set, whereas overall computational overhead is quadratic in the input sizes only for a designated party, and linear for the rest. We further reduce this overhead by employing two types of hashing schemes. (2) Our second protocol is proven secure in the malicious setting. This protocol induces communication complexity O((n^2 + nm_max + nm_mon log m_max)\\kappa) bits of communication where m_min (resp. m_max) is the minimum (resp. maximum) over all input sets sizes and n is the number of parties. This is a joint work with Muthuramakrishnan Venkitasubramaniam.\">Scalable Multi-Party Private Set-Intersection<\/span><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">26\/3\/2018<\/td>\n<td style=\"width: 204.383px;height: 32px\"><span style=\"color: #000000\">Klim Efremenko (BGU)<\/span><\/td>\n<td style=\"width: 343.1px;height: 32px\"><span title=\"In this talk we show first constant rate coding scheme for a noisy broadcast model defined by El Gamal in 1984. In this model a set of n players, each holding a private input bit, communicate over a noisy broadcast channel. Their mutual goal is for all players to learn all inputs. At each round one of the players broadcasts a bit to all the other players, and the bit received by each player is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed? The best know protocol before our work was given in 1988 by Gallager, who gave an elegant noise-resistant protocol requiring with 1\/log log n rate. We show that constant rate is possible. We will do so by exploiting the power of adaptive protocols.\"> Interactive Coding Over the Noisy Broadcast Channel<\/span><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">12\/3\/2018<\/td>\n<td style=\"width: 204.383px;height: 32px\"><span style=\"color: #000000\">Anat Paskin-Cherniavsky (Ariel)<\/span><\/td>\n<td style=\"width: 343.1px;height: 32px\"><span title=\"In this talk I will introduce and motivate unbounded secret sharing [KN16]. In this setting, the parties arrive one by one and the number of parties to arrive is not known in advance (at any given point in time). It is required that each new party receives a share, while the shares of existing parties are not modified. In particular, an approach for designing schemes for general (evolving) access structures from [KN16] will be presented. This approach results in exponential share complexity even for simple access structures such as (evolving) majority. In this work, we devise an optimization of the above approach, leading to share complexity \\tilde{O}(t^4) for evolving majority and generally the entire class of so called &#096;counting&#096; access structures (while still resulting in exponential share complexity in the general case), solving an open problem by [KN16]. Finally, I will briefly discuss additional related concepts and results we have obtained, such as unbounded robust secret sharing, and applications to unbounded secure multi party computation. This is joint work with Ilan Komargosdi - a preliminary version appears on eprint 2016\/1088.\">A design paradigm for unbounded secret sharing<\/span><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">12\/2-26\/2<\/td>\n<td style=\"width: 204.383px;height: 32px\"><strong><span style=\"color: #ff0000\">Spring Break<\/span><\/strong><\/td>\n<td style=\"width: 343.1px;height: 32px\"><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">29\/1\/2018<\/td>\n<td style=\"width: 204.383px;height: 32px\">Uri Stemmer (Weizmann)<\/td>\n<td style=\"width: 343.1px;height: 32px\"><span title=\"In the heavy-hitters problem, each user holds an input item (say, a password), and our goal is to identify all \u201cheavy-hitters\u201d, which are common input items (e.g., passwords that are used by more than 10,000 users). In this work we study the heavy-hitters problem in the local model of differential privacy (LDP), where the users randomize their data locally, and send differentially private reports to an untrusted server that aggregates them. In our case, this means that every user only sends the server a single randomized message that leaks very little information about the input of that user. We present new heavy-hitters algorithms satisfying local-differential-privacy, with optimal or near-optimal worst-case error, running time, and memory. In our algorithms, the server running time is $\\tilde O(n)$ and user running time is $\\tilde O(1)$, hence improving on the prior state-of-the-art result of Bassily and Smith [STOC 2015] requiring $O(n^{5\/2})$ server time and $O(n^{3\/2})$ user time. With a typically large number of participants in local algorithms ($n$ in the millions), this reduction in time complexity is crucial for making locally-private heavy-hitters algorithms usable in practice. Based on a joint work with Raef Bassily, Kobbi Nissim, and Abhradeep Thakurta, and a joint work with Mark Bun and Jelani Nelson.\">Locally Private Heavy Hitters<\/span><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">22\/1\/2018<\/td>\n<td style=\"width: 204.383px;height: 32px\">Osnat Keren<\/td>\n<td style=\"width: 343.1px;height: 32px\">\u00a0Algebraic manipulation detection codes<\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">8\/1\/2018<\/td>\n<td style=\"width: 204.383px;height: 32px\">Seri Khoury (Technion)<\/td>\n<td style=\"width: 343.1px;height: 32px\"><span title=\"We introduce a novel lower bound technique for distributed graph algorithms under bandwidth limitations. We define the notion of \\emph{fooling views} and exemplify its strength by proving two new lower bounds for triangle membership in the CONGEST(B) model: (i) Any 1-round algorithm requires B\u2265c\u0394logn for a constant c&gt;0. (ii) If B=1, even in constant-degree graphs any algorithm must take \u03a9(log\u2217n) rounds. The implication of the former is the first proven separation between the LOCAL and the CONGEST models for deterministic triangle membership. The latter result is the first non-trivial lower bound on the number of rounds required, even for \\emph{triangle detection}, under limited bandwidth. All previous known techniques are provably incapable of giving these bounds. We hope that our approach may pave the way for proving lower bounds for additional problems in various settings of distributed computing for which previous techniques do not suffice.\">Fooling Views: A New Lower Bound Technique for Distributed Computations under Congestion<\/span><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">25\/12\/2017<\/td>\n<td style=\"width: 204.383px;height: 32px\"><strong>No Talk<\/strong><br \/>\n(consolidated with Colloquium)<\/td>\n<td style=\"width: 343.1px;height: 32px\"><\/td>\n<\/tr>\n<tr style=\"height: 32px\">\n<td style=\"width: 107.517px;height: 32px\">11\/12\/2017<\/td>\n<td style=\"width: 204.383px;height: 32px\">Dror Rawitz<\/td>\n<td style=\"width: 343.1px;height: 32px\"><span title=\"We present local ratio interpretations of known algorithms for minimum s,t-cut and the assignment problem. Our interpretations are the first application of local ratio with negative weights. These interpretations lead to primal-dual analyses that are based on new IP formulations.\">Local Ratio with Negative Weights<\/span><\/td>\n<\/tr>\n<tr style=\"height: 63px\">\n<td style=\"width: 107.517px;height: 63px\">27\/11\/2017<\/td>\n<td style=\"width: 204.383px;height: 63px\">Siddharth Iyer<br \/>\n(BITS Pilani, India)<\/td>\n<td style=\"width: 343.1px;height: 63px\">Efficient Interactive Communication with randomized insertions and deletions<\/td>\n<\/tr>\n<tr style=\"height: 63px\">\n<td style=\"width: 107.517px;height: 63px\">13\/11\/2017<\/td>\n<td style=\"width: 204.383px;height: 63px\">Ran Gelles<\/td>\n<td style=\"width: 343.1px;height: 63px\">Privacy vs. Error-Correction - Part II (possibility)<\/td>\n<\/tr>\n<tr style=\"height: 63px\">\n<td style=\"width: 107.517px;height: 63px\">30\/11\/2017<\/td>\n<td style=\"width: 204.383px;height: 63px\">Ran Gelles<\/td>\n<td style=\"width: 343.1px;height: 63px\">Privacy vs. Error-Correction - Part I\u00a0 (impossibility)<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h6>Mailing List<\/h6>\n<p>The CE TheoryGroup has an active mailing list.<br \/>\nEmail me if you wish\u00a0 to be added (or removed) from the list.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Starting 2017 I&#8217;ve been running the CE TheoryGroup meetings. The main scope is Cryptography, Coding, and Algorithms, but we are always happy to learn about other tangential topics. 2020-2021 The seminar this year is run by Dr. Manuj Mukherjee (mukherm@biu.ac.il). See the new Seminar&#8217;s webpage. 2018-2019 We meet every other Monday, 12:00-13:00\u219212:30-13:30, room 431 (Engineering &hellip; <a href=\"https:\/\/www.eng.biu.ac.il\/gellesr\/theory-group\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Theory Group<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-130","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/pages\/130"}],"collection":[{"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/comments?post=130"}],"version-history":[{"count":63,"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/pages\/130\/revisions"}],"predecessor-version":[{"id":310,"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/pages\/130\/revisions\/310"}],"wp:attachment":[{"href":"https:\/\/www.eng.biu.ac.il\/gellesr\/wp-json\/wp\/v2\/media?parent=130"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}