Algorithms and Complexity Theory Seminars

We study two combinatorial settings of the contract design problem, in which a principal wants to delegate the execution of a costly task. In the first setting, the principal delegates the task to an agent that can take any subset of a given set of unobservable actions, each of which has an associated cost. The principal receives a reward which is a combinatorial function of the actions taken by the agent. In the second setting, we study the single-principal multi-agent contract problem, in which the principal motivates a team of agents to exert effort toward a given task. We design (approximately) optimal algorithms for both settings along with impossibility results for various classes of combinatorial functions. In particular, for the single agent setting, we show that if the reward function is gross substitutes, then an optimal contract can be computed with polynomially many value queries, whereas if it is submodular, the optimal contract is NP-hard. For the multi-agent setting, we show how using demand and value queries, it is possible to obtain a constant approximation, where for subadditive reward functions it is impossible to achieve an approximation of o(\sqrt(n)). Our analysis uncovers key properties of gross substitutes and XOS functions, and reveals many interesting connections between combinatorial contracts and combinatorial auctions. This talk is based on joint work with Paul Duetting, Michal Feldman, and Thomas Kesselheim. Bio: Tomer Ezra is a postdoc at Sapienza University of Rome, hosted by Prof. Stefano Leonardi. He completed his Ph.D. in Tel Aviv University under the supervision of Prof. Michal Feldman. His research interests lie in the border of Computer Science and Economics, focusing on the analysis and design of simple mechanisms and algorithms in limited information settings.

We consider prophet inequalities under general downward-closed constraints. In a prophet inequality problem, a decision-maker sees a series of online elements with values, and needs to decide immediately and irrevocably whether or not to select each element upon its arrival, subject to an underlying feasibility constraint. Traditionally, the decision-maker's expected performance has been compared to the expected performance of the prophet, i.e., the expected offline optimum. We refer to this measure as the Ratio of Expectations (or, in short, RoE). However, a major limitation of the RoE measure is that it only gives a guarantee against what the optimum would be on average, while, in theory, algorithms still might perform poorly compared to the realized ex-post optimal value. Hence, we study alternative performance measures. In particular, we suggest the Expected Ratio (or, in short, EoR), which is the expectation of the ratio between the value of the algorithm and the value of the prophet. This measure yields desirable guarantees, e.g., a constant EoR implies achieving a constant fraction of the ex-post offline optimum with constant probability. Moreover, in the single-choice setting, we show that the EoR is equivalent (in the worst case) to the probability of selecting the maximum, a well-studied measure in the literature. This is no longer the case for combinatorial constraints (beyond single-choice), which is the main focus of this paper. Our main goal is, thus, to understand the relation between RoE and EoR in combinatorial settings. Specifically, we establish two reductions: for every feasibility constraint, the RoE and the EoR are at most a constant factor apart. Additionally, we show that the EoR is a stronger benchmark than the RoE in that for every instance (feasibility constraint and product distribution) the RoE is at least a constant of the EoR, but not vice versa. Both these reductions imply a wealth of EoR results in multiple settings where RoE results are known.

The Johnson-Lindenstrauss transform allows one to embed a dataset of n points in R^d into R^m, while preserving the pairwise distance between any pair of points up to a factor (1 ± ε), provided that m = Ω(ε -2lg n). The transform has found an overwhelming number of algorithmic applications, allowing to speed up algorithms and reducing memory consumption at the price of a small loss in accuracy. A central line of research on such transforms, focus on developing fast embedding algorithms, with the classic example being the Fast JL transform by Ailon and Chazelle. All known such algorithms have an embedding time of Ω(d lg d), but no lower bounds rule out a clean O(d) embedding time. In this work, we establish the first non-trivial lower bounds (of magnitude Ω(mlg m)) for a large class of embedding algorithms, including in particular most known upper bounds.

We present the first fully persistent external memory search tree achieving amortized IO bounds matching those of the classic (ephemeral) B-tree by Bayer and McCreight. The insertion and deletion of a value in any version requires amortized O(log_B N_v) IOs and a range reporting query in any version requires worst-case O(log_B N_v + K/B) IOs, where K is the number of values reported, N_v is the number of values in the version v of the tree queried or updated, and B is the external memory block size. The data structure requires space linear in the total number of updates. Compared to the previous best bounds for fully persistent B-trees [Brodal, Sioutas, Tsakalidis, and Tsichlas, SODA 2012], this paper eliminates from the update bound an additive term of O(log₂ B) IOs. This result matches the previous best bounds for the restricted case of partial persistent B-trees [Arge, Danner and Teh, JEA 2003]. Central to our approach is to consider the problem as a dynamic set of two-dimensional rectangles that can be merged and split.

Efficiently computing low discrepancy colorings of various set systems, has been studied extensively since the breakthrough work by Bansal (FOCS 2010), who gave the first polynomial time algorithms for several important settings, including for general set systems, sparse set systems and for set systems with bounded hereditary discrepancy. The hereditary discrepancy of a set system, is the maximum discrepancy over all set systems obtainable by deleting a subset of the ground elements. While being polynomial time, Bansal's algorithms were not practical, with e.g. his algorithm for the hereditary setup running in time Ω(mn^4.5) for set systems with m sets over a ground set of n elements. More efficient algorithms have since then been developed for general and sparse set systems, however, for the hereditary case, Bansal's algorithm remains state-of-the-art. In this work, we give a significantly faster algorithm with hereditary guarantees, running in O(mn² lg(2+m/n)+n3) time. Our algorithm is based on new structural insights into set systems with bounded hereditary discrepancy. We also implement our algorithm and show experimentally that it computes colorings that are significantly better than random and finishes in a reasonable amount of time, even on set systems with thousands of sets over a ground set of thousands of elements.

Cut games are among the most fundamental strategic games in algorithmic game theory. It is well-known that computing an exact pure Nash equilibrium in these games is PLS-hard, so research has focused on computing approximate equilibria. We present a polynomial-time algorithm that computes 2.7371-approximate pure Nash equilibria in cut games. This is the first improvement to the previously best-known bound of 3, due to the work of Bhalgat, Chakraborty, and Khanna from EC 2010. Our algorithm is based on a general recipe proposed by Caragiannis, Fanelli, Gravin, and Skopalik from FOCS 2011 and applied on several potential games since then. The first novelty of our work is the introduction of a phase that can identify subsets of players who can simultaneously improve their utilities considerably. This is done via semidefinite programming and randomized rounding. In particular, a negative objective value to the semidefinite program guarantees that no such considerable improvement is possible for a given set of players. Otherwise, randomized rounding of the SDP solution is used to identify a set of players who can simultaneously improve their strategies considerably and allows the algorithm to make progress. The way rounding is performed is another important novelty of our work. Here, we exploit an idea that dates back to a paper by Feige and Goemans from 1995, but we take it to an extreme that has not been analyzed before. Based on joint work with Ioannis Caragiannis

Schelling's famous model of segregation assumes agents of different types, who would like to be located in neighborhoods having at least a certain fraction of agents of the same type. We consider natural generalizations that allow for the possibility of agents being tolerant towards other agents, even if they are not of the same type. In particular, we consider an ordering of the types, and make the realistic assumption that the agents are in principle more tolerant towards agents of types that are closer to their own according to the ordering. Based on this, we study the strategic games induced when the agents aim to maximize their utility, for a variety of tolerance levels. We provide a collection of results about the existence of equilibria, and their quality in terms of social welfare. Joint work with Panagiotis Kanellopoulos and Alexandros A. Voudouris.

In this talk, we will look at an algorithm to find a shortest cycle in a weighted directed graph. Let G be a directed graph with weight on the edges, where the weight of every edge is an integer in [-W,...,W]. The weight of a cycle is defined to be the sum of the weights of edges in the cycle. Cygan, Gabow, and Sankowski gave an algorithm to find a shortest cycle in time O(W n^ω log W), where n^ω is the time to multiply two n × n matrices. The algorithm uses algebraic tools to compute the determinant of a polynomial matrix and find an edge in a shortest cycle efficiently.

We give a simplified and improved lower bound for the simplex range reporting problem. We show that given a set P of n points in \R^d, any data structure that uses S(n) space to answer such queries must have Q(n)=Ω((n²/S(n))^(d-1)/d+k) query time, where k is the output size. For near-linear space data structures, i.e., S(n)=O(nlog^O(1)n), this improves the previous lower bounds by Chazelle and Rosenberg [CR96] and Afshani [A12] but perhaps more importantly, it is the first ever tight lower bound for any variant of simplex range searching for d≥ 3 dimensions. We obtain our lower bound by making a simple connection to well-studied problems in incident geometry which allows us to use known constructions in the area. We observe that a small modification of a simple already existing construction can lead to our lower bound. We believe that our proof is accessible to a much wider audience, at least compared to the previous intricate probabilistic proofs based on measure arguments by Chazelle and Rosenberg [CR96] and Afshani [A12]. The lack of tight or almost-tight (up to polylogarithmic factor) lower bounds for near-linear space data structures is a major bottleneck in making progress on problems such as proving lower bounds for multilevel data structures. It is our hope that this new line of attack based on incidence geometry can lead to further progress in this area.

Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {0,1}ⁿ   to {0,1} and G ∈ {AND₂, XOR₂}, the bounded-error quantum communication complexity of the composed function (f \circ G) = O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f. This is known as the BCW Simulation Theorem. This is in contrast with the classical setting, where it is easy to show that R^cc(f \circ G) ≤ 2R(f), where R^cc and R denote bounded-error communication and query complexity, respectively. We exhibited a total function for which the (log n) overhead in the BCW simulation is required. We also show that the (log n) overhead is not required when f is symmetric (i.e., depends only on the Hamming weight of its input), generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05).

We study the task of obliviously compressing a vector comprised of n ciphertexts of size ξ bits each, where at most t of the corresponding plaintexts are non-zero. This problem commonly features in applications involving encrypted outsourced storages, such as searchable encryption or oblivious message retrieval. We present two new algorithms with provable worst-case guarantees, solving this problem by using only homomorphic additions and multiplications by constants. Both of our new constructions improve upon the state of the art asymptotically and concretely. Our first construction, based on sparse polynomials, is perfectly correct and the first to achieve an asymptotically optimal compression rate by compressing the input vector into \bigOt ξ bits. Compression can be performed homomorphically by performing \bigOn log n homomorphic additions and multiplications by constants. The main drawback of this construction is a decoding complexity of Ω(√n). Our second construction is based on a novel variant of invertible bloom lookup tables and is correct with probability 1-2^-κ. It has a slightly worse compression rate compared to our first construction as it compresses the input vector into \bigOξκ t /log t bits. In exchange, both compression and decompression of this construction are highly efficient. The compression complexity is dominated by \bigOn κ homomorphic additions and multiplications by constants. The decompression complexity is dominated by \bigOξκ t /log t decryption operations and equally many inversions of a pseudorandom permutation.

Using participatory budgeting (PB), cities give their residents an opportunity to influence how the city's budget is spent. This is often done by collecting project proposals, and then voting on those proposals. This talk gives a survey on work in computational social choice on this voting problem. First, we discuss the voting systems in use in major cities, which mostly involve a naive greedy algorithm based on approval scores. Then we formalize a model of voting under a knapsack constraint with additive valuations, and discuss how standard approval votes fit in that model. We then discuss a new voting rule, the Method of Equal Shares, that I have recently proposed with my coauthor Piotr Skowron. This rule provides proportional representation, which I'll argue is a desirable goal in PB. Finally, I will mention PB work on the core, strategyproofness, computational complexity, and several extensions which could form directions for future research: allowing negative votes, allowing for constraints, as well as analyzing input formats and the process of agenda setting, among others.

A distance oracle of a graph is a preferably compact data structure that can efficiently answer queries for the shortest path distance from one query vertex to another. A trivial distance oracle is a look-up table that stores the shortest path distance between any pair of vertices. This oracle has constant query time but requires Θ(n²) space. For general graphs, this is the best one can hope for for exact shortest path distance queries. In this talk, I will present some recent results I have been involved in which show that for planar graphs, it is possible to get an oracle that reports exact shortest path distances using space truly subquadratic in n (i.e., O(n^2-ε) for some constant ε > 0) and constant or O(log n) query time. The previous best space bounds with polylogarithmic query time in planar graphs were only below Θ(n²) by log n-factors. I will also briefly mention progress I have obtained for approximate distance oracles in planar graphs.

In the problem of semialgebraic range searching, we are to preprocess a set of points in R^D such that the subset of points inside a semialgebraic region described by O(1) polynomial inequalities of degree Δ can be found efficiently. Relatively recently, several major advances were made on this problem. Using algebraic techniques, "near-linear space" structures [AMS13,MP15] with almost optimal query time of Q(n) = O(n^1-1/D+o(1)) were obtained. For "fast query" structures (i.e., when Q(n) = n^o(1)), it was conjectured that a structure with space S(n) = O(n^D+o(1)) is possible. The conjecture was refuted recently by Afshani and Cheng [AC21]. In the plane, they proved that S(n)=Ω(n^Δ+1-o(1)/Q(n)^(Δ+3)Δ/2) which shows Ω(n^Δ+1-o(1)) space is needed for Q(n) = n^o(1). While this refutes the conjecture, it still leaves a number of unresolved issues: the lower bound only works in 2D and for fast queries, and neither the exponent of n or Q(n) seem to be tight even for D = 2, as the current upper bound is S(n) = O(n^m+o(1)/Q(n)^(m-1)D/(D-1)) where m = D+Δ \choose D - 1 = Ω(Δ^D) is the maximum number of parameters to define a monic degree-Δ D-variate polynomial, for any D, Δ = O(1). In this paper, we resolve two of the issues: we prove a lower bound in D-dimensions and show that when Q(n) = n^o(1)m + O(k), S(n) = Ω(n^m-o(1)), which is almost tight as far as the exponent of n is considered in the pointer machine model. When considering the exponent of Q(n), we show that the analysis in [AC21] is tight for D = 2, by presenting matching upper bounds for uniform random point sets. This shows either the existing upper bounds can be improved or a new fundamentally different input set is needed to get a better lower bound.

We consider the problem of maximizing the Nash social welfare when allocating a set G of indivisible goods to a set N of agents. We study instances, in which all agents have 2-value additive valuations: The value of every agent i ∈ N for every good j ∈ G is either p or q, for p,q ∈ N, p<q. In this work, we design an algorithm to compute an optimal allocation in polynomial time if p divides q, i.e., when p = 1 and q ∈ N, after appropriate scaling. The problem is NP-hard whenever p and q are coprime and p ≥ 3. In terms of approximation, we present positive and negative results for general p and q. We show that our algorithm obtains an approximation ratio of at most 1.0345. Moreover, we prove that the problem is APX-hard, with a lower bound of 1.000015 achieved at p/q = 4/5.

A priority queue stores a set of items with associated keys and supports the insertion of a new item and extraction of an item with minimum key. In applications like Dijkstra's single source shortest path algorithm and Prim-Jarnik's minimum spanning tree algorithm, the key of an item can decrease over time. Usually this is handled by either using a priority queue supporting the deletion of an arbitrary item or a dedicated DecreaseKey operation, or by inserting the same item multiple times but with decreasing keys. We study what happens if the keys associated with items in a priority queue can decrease over time without informing the priority queue, and how such a priority queue can be used in Dijkstra's algorithm. We show that binary heaps with bottom-up insertions fail to report items with unchanged keys in correct order, while binary heaps with top-down insertions report items with unchanged keys in correct order. Furthermore, we show that skew heaps, leftist heaps, and priority queues based on linking roots of heap-ordered trees, like pairing heaps, binomial queues and Fibonacci heaps, work correctly with decreasing keys without any modifications. Finally, we show that the post-order heap by Harvey and Zatloukal, a variant of a binary heap with amortized constant time insertions and amortized logarithmic time deletions, works correctly with decreasing keys and is a strong contender for an implicit priority queue supporting decreasing keys in practice. To be presented at FUN22.

We consider the following surveillance problem: Given a set P of n sites in a metric space and a set of k robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency L of a schedule is the maximum latency of any site, where the latency of a site s is the supremum of the lengths of the time intervals between consecutive visits to s. When k=1 the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into l groups, for some l ≤ k, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a 1 + ε factor loss in the approximation factor and an O((k/ε)k) factor loss in the runtime, for any ε>0. Our second main result shows that an optimal cyclic solution is a 2(1-1/k)-approximation of the overall optimal solution. Note that for k=2 this implies that an optimal cyclic solution is optimal overall. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a (2(1-1/k)+ε)-approximation of the optimal unrestricted solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting.

Tensors are mathematical concepts known as multidimensional arrays of numerical values in literature and these concepts are used for representing high dimensional data in many scientific problems. Therefore, tensor decomposition methods have wide application area such in psychometrics, chemometrics, signal processing, numerical linear algebra, computer vision, numerical analysis, data mining, neuroscience, graph analysis, machine learning, etc. The scope of this talk is to introduce basic tensor concepts and some of well-known tensor decomposition methods in literature and also giving information about my research studies related with tensor decomposition.

Abstract: We consider the maximum matching in dynamic graphs. Given a sequence of edge insertions and deletions, we aim to maintain a large matching using as little update time per edge as possible. In this talk, we will present a deterministic algorithm that maintains a 3/2+eps approximate matching using O(m¹/4) worst case update time. The talk will focus on efficiently maintaining a subgraph known as an edge degree constrained subgraph (EDCS) with strong structural properties, which may be of independent interest. Based on joint work with Fabrizio Grandoni, Shay Solomon and Amitai Uzrad.

We study the PAC learnability of multiwinner voting, focusing on the class of approval-based committee scoring (ABCS) rules. These are voting rules applied on profiles with approval ballots, where each voter approves some of the candidates. According to ABCS rules, each committee of k candidates collects from each voter a score, that depends on the size of the voter's ballot and on the size of its intersection with the committee. Then, committees of maximum score are the winning ones. Our goal is to learn a target rule (i.e., to learn the corresponding scoring function) using information about the winning committees of a small number of sampled profiles. Despite the existence of exponentially many outcomes compared to single-winner elections, we show that the sample complexity is still low: a polynomial number of samples carries enough information for learning the target committee with high confidence and accuracy. Unfortunately, even simple tasks that need to be solved for learning from these samples are intractable. We prove that deciding whether there exists some ABCS rule that makes a given committee winning in a given profile is a computationally hard problem. Our results extend to the class of sequential Thiele rules, which have received attention due to their simplicity.

We study the computational complexity of computing solutions for the straight-cut and square-cut pizza sharing problems. We show that finding an approximate solution is PPA-hard for the straight-cut problem, and PPA-complete for the square-cut problem, while finding an exact solution for the square-cut problem is FIXP-hard and in BU. Our PPA-hardness results apply even when all mass distributions are unions of non-overlapping squares, and our FIXP-hardness result applies even when all mass distributions are unions of weighted squares and right-angled triangles. We also show that decision variants of the square-cut problem are hard: we show that the approximate problem is NP-complete, and the exact problem is ETR-complete. Joint Work with John Fearnley and Themistoklis Melissourgos Link: https://arxiv.org/abs/2012.14236

Expander graphs, over the last few decades, have played a pervasive role in almost all areas of theoretical computer science. Loosely, speaking an expander graph is an extremely wellconnected graph despite being sparse. Recently, various highdimensional analogues of these objects have been studied in mathematics and even more recently, there have been some surprising applications in computer science, especially in the area of property testing, coding theory and approximate counting. In this talk, I'll give a high-level introduction to these high-dimensional expanders (HDXs). In particular, we will view them through the perspective of random walks on graphs. Time permitting, we will then some see applications of these HDXs towards property testing, coding theory and matroid counting.

In 2017, Goldstein, Kopelowitz, Lewenstein, and Porat introduced the data structure variant of the 3SUM problem called 3SUM-Indexing in the cell probe model and furthermore drew links between its lower bounds and lower bounds for the Set Disjointness problem. Golovnev, Guo, Horel, Park, and Vaikuntanathan in 2020 then gave the first non-trivial data structure lower bound for small query times which match the best known lower bounds for static data structure problems and reductions to other problems in computational geometry. In this talk, we will present two small improvements to their lower bound result. Namely, we show that for any sufficiently small query time T, we require a data structure of size at least n(1+2/T) (which is a factor of n1/T larger than the existing lower bound). Furthermore, we show that if each memory cell only contains a single bit, the size of the data structure must be at least n3.

Graph neural networks are the de-facto standard way of applying machine learning to graphs. In this talk, we will cover the basic idea of GNNs and how they are typically used in graph-based machine learning. We then look into the expressivity of GNNs and present the connection to the 1-dimensional Weisfeiler-Leman algorithm, also known as color refinement. Article: https://arxiv.org/abs/1810.02244

We follow up on the idea of Lars Arge to rephrase the Reduce and Apply procedures of Binary Decision Diagrams (BDDs) as iterative I/O-efficient algorithms. We identify multiple avenues to simplify and improve the performance of his proposed algorithms. Furthermore, we extend the technique to other common BDD operations, many of which are not derivable using Apply operations alone, and we provide asymptotic improvements for the procedures that can be derived using Apply. These algorithms are implemented in a new BDD package, named Adiar. We see very promising results when comparing the performance of Adiar with conventional BDD package that use recursive depth-first algorithms. For instances larger than 9.5 GiB, our algorithms, in parts using the disk, are 1.47 to 3.7 times slower compared to CUDD and Sylvan, exclusively using main memory. Yet, our proposed techniques are able to obtain this performance at a fraction of the main memory needed by Sylvan to function. Furthermore, with Adiar we are able to manipulate BDDs that outgrow main memory and so surpass the limits of other BDD packages. arXiv Paper: https://arxiv.org/abs/2104.12101 GitHub: https://github.com/ssoelvsten/adiar

The program performance on modern hardware is characterized bylocality of reference, that is, it is fasterto access data that is close in address space to data that has been accessed recently than data in a randomlocation. This is due to many architectural features including caches, prefetching, virtual address translationand the physical properties of a hard disk drive; attempting to model all the components that constitute theperformance of a modern machine is impossible, especially for general algorithm design purposes. What ifone could prove an algorithm is asymptotically optimal on all systems that reward locality of reference, nomatter how it manifests itself within reasonable limits? We show that this is possible, and that excluding somepathological cases, cache-oblivious algorithms that are asymptotically optimal in the ideal-cache model areasymptotically optimal in any reasonable setting that rewards locality of reference. This is surprising as thecache-oblivious framework envisions a particular architectural model involving blocked memory transfer into amulti-level hierarchy of caches of varying sizes, and was not designed to directly model locality-of-referencecorrelated performance.

We prove an Ω(log nloglog n) lower bound for the span of implementing the n input, log n-depth FFT circuit (also known as butterfly network) in the nonatomic binary fork-join model. In this model, memory-access synchronizations occur only through fork operations, which spawn two child threads, and join operations, which resume a parent thread when its child threads terminate. Our bound is asymptotically tight for the nonatomic binary fork-join model, which has been of interest of late, due to its conceptual elegance and ability to capture asynchrony. Our bound implies super-logarithmic lower bound in the nonatomic binary fork-join model for implementing the butterfly merging networks used, e.g., in Batcher's bitonic and odd-even mergesort networks. This lower bound also implies an asymptotic separation result for the atomic and nonatomic versions of the fork-join model, since, as we point out, FFT circuits can be implemented in the atomic binary fork-join model with span equal to their circuit depth. Joint work with Michael T. Goodrich and Riko Jacob, presented at SODA 2021.

Microchip design is a process which consists of several stages, each stage posing its own flavour of algorithmic challenges. These challenges fall within different fields of algorithmic research, such as computational geometry, graph theory, parallel algorithms, and combinatorial optimization. In this talk we present an overview of the modern chip design process, and we briefly outline some of the main problems currently encountered in this field.

I will introduce a new direction in categorical range counting. Categorical range counting is the problem of given a colored point set in d-dimension store them in a datastructure, such that we can answer the following query: Given a range, output the number of distinct colors within the query range. In the classical setting the categories/colors are thought of as independent. In this talk I will present a version of the problem where the color set have dependency and show some basic lowerbounds and upper bounds in this setting.

I will give a brief overview of Fair Division, and then describe its elegant connection to a celebrated result in combinatorial topology, namely Sperner's Lemma.

Iterative methods for approximating zero-sum Nash equilibria in extensive-form games have been a core component of recent advances in superhuman poker AIs. In this talk, I will first give an optimization-oriented description of how these methods work. Then, I will discuss and contrast two recent results: First, the development of a new entropy-based regularization method for the decision spaces associated with extensive-form games, which is simultaneously simpler to analyze and has better theoretical properties than the current state of the art. Second, I will discuss new algorithms based on optimistic variants of regret matching and CFR, which lead to very strong practical performance, in spite of inferior theoretical guarantees.

Robust property-preserving hash (PPH) functions compress large inputs x and y into short digests h(x) and h(y) in a manner that allows for evaluating a predicate P on x and y while only having access to the corresponding hash values. In contrast to locality-sensitive hash functions, a robust PPH function guarantees to correctly evaluate a predicate on h(x) and h(y) even if x and y are chosen adversarially after seeing h. In this talk, I'll give an introduction to this new area and I'll will present the first construction of a robust PPH function for the exact hamming distance predicate (i.e. "is the hamming distance between inputs x and y larger than some parameter t?"). The talk will be based on recent results that will appear at Eurocrypt 2021

I will introduce the notion of a probabilistic polynomial for a Boolean function, which arose in the 1980s in the study of circuit lower bounds (Razborov 1987) and has more recently found use in algorithms for combinatorial problems such as All Pairs Shortest Paths (Williams 2014). Informally, a probabilistic polynomial is a randomized algorithm, where the algorithm is a polynomial and its efficiency is measured by its degree. I will try to describe two results. 1. A result from 2016 where we proved lower bounds on the probabilistic polynomial degree of the OR function. This is proved via interesting results about anti-concentration of low-degree polynomials. 2. A recent result where we show lower bounds on the minimum possible probabilistic degree of an n-variable function. This is joint work with Prahladh Harsha and S Venkitesh.

In a landmark paper, Patrascu demonstrated how a single lower bound for the static data structure problem of reachability in the butterfly graph, could be used to derive a wealth of new and previous lower bounds via reductions. These lower bounds are tight for numerous static data structure problems. Moreover, he also showed that reachability in the butterfly graph reduces to dynamic marked ancestor, a classic problem used to prove lower bounds for dynamic data structures. Unfortunately, Patrascu's reduction to marked ancestor loses a lglg n factor and therefore falls short of fully recovering all the previous dynamic data structure lower bounds that follow from marked ancestor. In this paper, we revisit Patrascu's work and give a new lossless reduction to dynamic marked ancestor, thereby establishing reachability in the butterfly graph as a single seed problem from which a range of tight static and dynamic data structure lower bounds follow. To be presented at SOSA 2021.

We investigate the limits of one of the fundamental ideas in data structures: fractional cascading. This is an important data structure technique to speed up repeated searches for the same key in multiple lists and it has numerous applications. Specifically, the input is a ``catalog'' graph, G, of constant degree together with a list of values assigned to every vertex of G. The goal is to preprocess the input such that given a connected subgraph G' of G and a single query value q, one can find the predecessor of q in every list that belongs to G'. The classical result by Chazelle and Guibas shows that in a pointer machine, this can be done in the optimal time of O(log n + |G'|) where n is the total number of values. However, if insertion and deletion of values are allowed, then the query time slows down to O(log n + |G'| loglog n). If only insertions (or deletions) are allowed, then once again, an optimal query time can be obtained but by using amortization at update time. We prove a lower bound of Ω( log n √loglog n) on the worst-case query time of dynamic fractional cascading, when queries are paths of length O(log n). The lower bound applies both to fully dynamic data structures with amortized polylogarithmic update time and incremental data structures with polylogarithmic worst-case update time. As a side, this also proves that amortization is crucial for obtaining an optimal incremental data structure. This is the first non-trivial pointer machine lower bound for a dynamic data structure that breaks the Ω(log n) barrier. In order to obtain this result, we develop a number of new ideas and techniques that hopefully can be useful to obtain additional dynamic lower bounds in the pointer machine model. To be presented at SODA 2021.

In this work, we present the first asymptotically optimal oblivious priority queue, which matches the lower bound of Jacob, Larsen, and Nielsen (SODA'19). Our construction is conceptually simple and statistically secure. We illustrate the power of our optimal oblivious priority queue by presenting a conceptually equally simple construction of statistically secure offline ORAMs with O(log n) bandwidth overhead. To be presented at SODA 2021.

Chazelle introduced the soft heap as a building block for efficient minimum spanning tree algorithms, and recently Kaplan et al. showed how soft heaps can be applied to achieve simpler algorithms for various selection problems. A soft heap trades-off accuracy for efficiency by allowing ε N of the items in a heap to be corrupted after a total of N insertions, where a corrupted item is an item with artificially increased key and 0<ε≤ 1/2 is a fixed error parameter. Chazelle's soft heaps are based on binomial trees and support insertions in amortized O(log (1/ε)) time and extract-min operations in amortized O(1) time. In this paper we explore the design space of soft heaps. The main contribution of this paper is an alternative soft heap implementation based on merging sorted sequences, with time bounds matching those of Chazelle's soft heaps. We also discuss a variation of the soft heap by Kaplan et al., where we avoid performing insertions lazily. It is based on ternary trees instead of binary trees and matches the time bounds of Kaplan et al., i.e. amortized O(1) insertions and amortized O(log (1/ε)) extract-min. Both our data structures only introduce corruptions after extract-min operations which return the set of items corrupted by the operation. To be presented at SOSA 2021.

Various Neural Networks employ time-consuming matrix operations like matrix inversion. Many such matrix operations are faster to compute given the Singular Value Decomposition (SVD). Previous work allows using the SVD in Neural Networks without computing it. In theory, the techniques can speed up matrix operations, however, in practice, they are not fast enough. We present an algorithm that is fast enough to speed up several matrix operations. The algorithm increases the degree of parallelism of an underlying matrix multiplication H· X where H is an orthogonal matrix represented by a product of Householder matrices. To be presented at NeurIPS 2020.

Motivated by practical generalizations of the classic k-median and k-means objectives, such as clustering with size constraints, fair clustering, and Wassterstein barycenter, we introduce a meta-theorem for designing coresets for constrained-clustering problems. The meta-theorem reduces the task of coreset construction to one on a bounded number of ring-instances with a much-relaxed additive error. This enables us to use uniform sampling, in contrast to the widely used importance sampling, when constructing our coreset, and consequently we can easily handle constrained objectives. Notably and perhaps surprisingly, we show that this simpler sampling scheme can yields bounds that are independent of n, the number of input points. Our technique yields better coreset bounds, and sometimes the first coreset, for a large number of constrained clustering problems, including capacitated clustering, fair clustering, clustering with anonymity, clustering with diversity, Euclidean Wasserstein barycenter, clustering in minor-excluded graph, and polygon clustering under Frechet and Hausdorff distance. Finally, our technique also yields improved coresets for 1-Median in low-dimensional Euclidean spaces.

Fractional cascading is one of the influential and important techniques in data structures, as it provides a general framework for solving a common important problem: the iterative search problem. In the problem, the input is a graph G with constant degree. Also as input, we are given a set of values for every vertex of G. The goal is to preprocess G such that when we are given a query value q, and a connected subgraph π of G, we can find the predecessor of q in all the sets associated with the vertices of π. The fundamental result of fractional cascading, by Chazelle and Guibas, is that there exists a data structure that uses linear space and it can answer queries in O(log n + |π|) time, at essentially constant time per predecessor. While this technique has received plenty of attention in the past decades, an almost quadratic space lower bound for ``two-dimensional fractional cascading'' by Chazelle and Liu in STOC 2001 has convinced the researchers that fractional cascading is fundamentally a one-dimensional technique. In two-dimensional fractional cascading, the input includes a planar subdivision for every vertex of G and the query is a point q and a subgraph π and the goal is to locate the cell containing q in all the subdivisions associated with the vertices of π. In this paper, we show that it is actually possible to circumvent the lower bound of Chazelle and Liu for axis-aligned planar subdivisions. We present a number of upper and lower bounds which reveal that in two-dimensions, the problem has a much richer structure. When G is a tree and π is a path, then queries can be answered in O(logn+|π|+min{|π|√logn,α(n)√|π|logn}) time using linear space where α is an inverse Ackermann function; surprisingly, we show both branches of this bound are tight, up to the inverse Ackermann factor. When G is a general graph or when π is a general subgraph, then the query bound becomes O(log n + |π|√log n) and this bound is once again tight in both cases.

We reexamine three classical settings of optimization under uncertainty, which have been extensively studied in the past, assuming that the several random events involved are mutually independent. Here, we assume that such events are only pair-wise independent; this gives rise to a much richer space of instances. Our aim has been to explore whether positive results are possible even under the more general assumptions. We show that this is indeed the case. Indicatively, we show that, when applied to pair-wise independent distributions of buyer values, sequential posted pricing mechanisms get at least 11.299 of the revenue they get from mutually independent distributions with the same marginals. We also adapt the well-known prophet inequality to pair-wise independent distributions of prize values to get a 1/3-approximation using a non-standard uniform threshold strategy. Finally, in a stochastic model of generating random bipartite graphs with pair-wise independence on the edges, we show that the expected size of the maximum matching is large but considerably smaller than in Erd Hos-Renyi random graph models where edges are selected independently. Our techniques include a technical lemma that might find applications in other interesting settings involving pair-wise independence. Joint work with Nick Gravin, Pinyan Lu, and Zihe Wang

This work presents an improved hashing-based algorithm for Private Set Intersection (PSI) in the honest-but-curious setting. The protocol is generic, modular and provides both asymptotic and concrete efficiency improvements over existing PSI protocols. If each player has m elements, our scheme requires only O(mλ) communication between the parties, where λ is a security parameter. Our protocol builds on the hashing-based PSI protocol of Pinkas et al. (USENIX 2014, USENIX 2015), but we replace one of the sub-protocols (handling the cuckoo "stash") with a special-purpose PSI protocol that is optimized for comparing sets of unbalanced size. This brings the asymptotic communication complexity of the overall protocol down from ω(mλ) to O(mλ), and provides concrete performance improvements (10-15% reduction in communication costs) over Kolesnikov et al. (CCS 2016) under real-world parameter choices. Our protocol is simple, generic and benefits from the permutation-hashing optimizations of Pinkas et al. (USENIX 2015) and the Batched, Relaxed Oblivious Pseudo Random Functions of Kolesnikov et al. (CCS 2016).

This interactive presentation consists of several parts, including: 1) A simple abstract resource theory, where resources are elements of a partially ordered set and where ajoining resources, relaxations of resources, and constructions (of resources from resources), are captured as order-preserving functions (i.e., as homomorphisms) satisfying certain axioms, for example (one-sided) commutativity of certain homomorphisms. 2) A theory of discrete probabilistic systems, where most systems discussed in cryptography (and beyond) can be understood as descriptions (in a particular language, for example a specific pseudo-code language) of such discrete systems. An instantiation of discrete systems for modeling time is also discussed, which is important for modeling guarantees in asynchronous systems such as blockchain systems. 3) Constructive cryptography as an instantiation of the resource theory, where resources are (specifications, i.e., sets of) discrete systems. Many diverse types of traditional statements in cryptography can benaturally unified and seen as being of the same type, for example information-theoretic and cryptographic security, static and adaptive corruption, and synchronous and asynchronous models as well as models capturing time. If time permits, I will also discuss an abstract theory of reductions that requires no computational model but nevertheless allows to capture typical complexity-based statements in cryptography (and beyond). The presentation is targeted at two different audiences, cryptographers and formal method specialists, and it aims at providing a bridge between them to allow cryptographers to make clean security statements that are formalizable and amenable to machine-checkable proofs. But the presented framework has a wider scope than cryptography; the ultimate goal (not yet worked out) is to capture statements at various levels, from the physical layer over digital circuits and software to the application, with cryptographic statements naturally integrated, as construction steps in a single framework. Based partially on joint work with Renato Renner and with many other researchers.

Traditionally arithmetic multiparty computation protocols have mostly worked over finite fields. Recently, more general commutative rings have been considered, mostly notably the integers modulo a prime power. The SPDZ2k protocol (CRYPTO 2018) showed that in the dishonest majority setting MPC over these rings can be obtained with comparable efficiency to over fields. Since then, several works have shown that in some cases, working over these rings can be much faster than working over fields. We discuss some of the differences of doing MPC over fields versus these rings, and show that comparable efficiency to fields can also be obtained in the information-theoretic honest-majority setting.

Fairness in Secure Multiparty Computation (MPC) is known to be impossible to achieve in the presence of a dishonest majority. Previous works have proposed combining MPC protocols with Cryptocurrencies in order to financially punish aborting adversaries, providing an incentive for parties to honestly follow the protocol. This approach also yields privacy-preserving Smart Contracts, where private inputs can be processed with MPC in order to determine the distribution of funds given to the contract. Unfortunately, the focus of existing work is on proving that this approach is possible and they present monolithic and mostly inefficient constructions. In this work, we put forth the first modular construction of ``Insured MPC'', where either the output of the private computation (which describes how to distribute funds) is fairly delivered or a proof that a set of parties has misbehaved is produced, allowing for financial punishments. Moreover, both the output and the proof of cheating are publicly verifiable, allowing third parties to independently validate an execution. We present a highly efficient compiler that uses any MPC protocol with certain properties together with a standard (non-private) Smart Contract and a publicly verifiable homomorphic commitment scheme to implement Insured MPC. As an intermediate step, we propose the first construction of a publicly verifiable homomorphic commitment scheme achieving composability guarantees and concrete efficiency. Our results are proven in the Global Universal Composability framework using a Global Random Oracle as the setup assumption. From a theoretical perspective, our general results provide the first characterization of sufficient properties that MPC protocols must achieve in order to be efficiently combined with Cryptocurrencies, as well as insights into publicly verifiable protocols. On the other hand, our constructions have highly efficient concrete instantiations, allowing for fast implementations.

In the 'frequent items' problem one sees a sequence of items in a stream (e.g. a stream of words coming into a search query engine like Google) and wants to report a small list of items containing all frequent items. We would like algorithms for this problem that use memory substantially sublinear in the length of the stream. In this talk we describe a new state-of-the-art solution to this problem, called the "BPTree". We make use of chaining methods to control the suprema of Rademacher processes to develop this new algorithm which has provably near-optimal memory consumption for the "l₂" heavy hitters problem, improving upon the CountSieve and CountSketch from previous work. Based on joint work with Vladimir Braverman, Stephen Chestnut, Nikita Ivkin, Zhengyu Wang, and David P. Woodruff

Machine Learning models, and specially convolutional neural networks (CNNs), are at the heart of many day-to-day applications like image classification and speech recognition. The need for evaluating such models whilst preserving the privacy of the input provided increases as the models are used for more information-sensitive tasks like DNA analysis or facial recognition. Research on evaluating CNNs securely has been very active during the last couple of years, e.g. Mohassel & Zhang (S&P'17) and Liu et al. (CCS'17), leading to very efficient frameworks like SecureNN (ePrint:2018:442), which can perform evaluation of some CNNs with a multplicative overhead of only 17--33 with respect to evaluation in the clear. We contribute to this line of research by introducing a technique from the Machine Learning domain, namely quantization, which allows us to scale secure evaluation of CNNs to much larger networks without the accuracy loss that could happen by adapting the network to the MPC setting. Quantization is motivated by the deployment of ML models in resource-constrained devices, and we show it to be useful in the MPC setting as well. Our results show that it is possible to evaluate realistic models---specifically Google's MobileNets line of models for image recognition---within seconds. Our performance gain can be mainly attributed to two key ingredients: One is the use of the three-party MPC protocol based on replicated secret sharing by Araki et al. (S&P'17), whose multiplication only requires sending one number per party. Moreover, it allows to evaluate arbitrary long dot products at the same communication cost of a single multiplication, which facilitates matrix multiplications considerably. The second main ingredient is the use of arithmetic modulo 2⁶4 , for which we develop a set of primitives of independent interest that are necessary for the quantization like comparison and truncation by a secret shift. This talk is based on joint work with Daniel Escudero (Aarhus), Assi Barak (BIU) and Marcel Keller (data61). The paper is on eprint at https://eprint.iacr.org/2019/131

We prove a lower bound on the communication complexity of unconditionally secure multiparty computation with n=2t+1 parties of which t are corrupted. We prove that for any g ∈ N there exists a Boolean circuit C with g gates, where any secure protocol implementing C must communicate Ω(t g) bits, even if only passive and statistical security is required, and even if parties are given access to correlated randomness. The results easily extends to constructing similar circuits over any fixed finite field. This shows that for all sizes of circuits, the O(n) overhead of all known protocols when t≥ ⌊ n/2 ⌋ is inherent. It also shows that security comes at a price: the circuit we consider could namely be computed among n parties with communication only O(g) bits if no security was required. Our results extend to the case where the threshold t is suboptimal and this shows that the known optimizations via packed secret-sharing can only be obtained if one accepts that the threshold is t= (1/2 - c)n for a constant c. For the case of honest majority and no correlated randomness, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor log n off for Boolean circuits). Joint work with Jesper Buus Nielsen and Kasper Green Larsen

Spatial Scan Statistics measure and detect anomalous spatial behavior, specifically they identify geometric regions where significantly more of a measured characteristic is found than would be expected from the background distribution. These techniques have been used widely in geographic information science, such as to pinpoint disease outbreaks. However, until recently, available algorithms and software only scaled to at most a thousand or so spatial records. In this work I will describe how using coresets, efficient constructions, and scanning algorithms, we have developed new algorithms and software that easily scales to millions or more data points. Along the way we provide new efficient algorithms and constructions for ε-samples and ε-nets for various geometric range spaces. This is a case where subtle theoretical improvements of old structures from discrete geometry actually result in substantial empirical improvements.

We start our talk by reflections on the similarity between (some) game-based and (some) simulation-based definitions. We then explain shortly how a typical game-playing proof for a real-life protocol such as TLS looks like and why/how we reach limits of human understanding quickly in such proofs. We then present a new technique to carry out game-playing proofs: We here package pieces of code that share state and allow information between packages only to flow via calls. Thereby, we obtain a call graph where the packages are the nodes. We then show how reductions can be represented via cuts in the graph and show proof examples that become more manageable when thinking on the level of packages rather than on the level of individual code lines. In the end of the seminar, we would like to discuss the complexity of MPC proofs with the audience.

Using an homomorphic authenticator (HA) scheme (e.g., homomorphic MAC or signature) a user, Alice, can authenticate a collection of data items using her secret key, and send the authenticated data to an untrusted server. At any later point in time, the server can generate a short authenticator vouching for the correctness of the output of a function computed on the outsourced data to another user Bob. However, how can we authenticate homomorphic computation of functions that involve data authenticated by different users holding independent secret keys? In this talk I will present two solutions to create multi-key homomorphic authenticators. I will describe the first multi-key homomorphic MAC construction by Fiore et al (Asiacrypt 2016) and the first compiler to enhance any sufficiently expressive single-key homomorphic signature with multi-key properties (Fiore and Pagnin, to appear at SCN 2018).

Take a finite set of biased dice that share some common faces. An adversary repeatedly tosses them, with each choice of die possibly depending on the previous outcomes. Can you extract true randomness? In 1986 Santha and Vazirani gave a negative answer when the dice are (two-sided) coins. In 2015 Beigi, Etesami, and Gohari showed how to obtain an almost-unbiased bit for other sets of dice. The sample complexity of their extractor is polynomial in the inverse of the error. We completely classify all non-trivial randomness sources of this type into: (1) non-extractable ones; (2) extractable from polynomially many samples; and (3) extractable from an logarithmically many samples (in the inverse of the error). The extraction algorithms are efficient and easy to describe. I will discuss the relevance to distributed and cryptographic computation from imperfect randomness and point out some open questions in this context.

Asymmetric External Memory (AEM) model, introduced by Blelloch et al. at SPAA 2015, models computations on new non-volatile memory (NVM), rather than tradition DRAM technology for storage purposes. The significant difference in NVMs is the fact that the cost of writing data is significantly more expensive than the cost of reading it. This asymmetry requires new algorithmic techniques that emphasize the ability to trade-off write accesses for extra read accesses during computation. In this talk I will present sorting algorithms, which achieve such trade-off between read and write accesses in the AEM model. I will also show a lower bound that proves that these algorithms are asymptotically optimal. This is joint work with Riko Jacob, and appeared in SPAA 2017.

We will present a heavy-hitters protocol in the model of local differential privacy. Our protocol achieves optimal or near optimal worst-case error, running time, and memory, improving on the prior state-of-the-art result of Bassily and Smith [STOC 2015]. The improvement is crucial for making locally-private heavy-hitters algorithms usable when the number of participants is in the millions. Joint work with Raef Bassily, Kobbi Nissim, and Abhradeep Thakurta.

Three important properties of classification machinery are: (i) the system preserves the core information of the input data; (ii) the training examples convey information about unseen data; and (iii) the system is able to treat differently points from different classes. In this talk, I will show that these fundamental properties are satisfied by the architecture of deep neural networks. I will highlight a formal proof that such networks with random Gaussian weights perform a distance-preserving embedding of the data, with a special treatment for in-class and out-of-class data. Similar points at the input of the network are likely to have a similar output. The theoretical analysis of deep networks I will present exploits tools used in the compressed sensing and dictionary learning literature, thereby making a formal connection between these important topics. The derived results allow drawing conclusions about the metric learning properties of the network and their relation to its structure, as well as providing bounds on the required size of the training set such that the training examples would represent faithfully the unseen data. I will show how these conclusions are validated by state-of-the-art trained networks. I believe that these results provide an insight why deep learning works and potentially allow designing more efficient network architectures and learning strategies.

Locality-sensitive hashing (LSH) has recently emerged as the dominant algorithmic technique for similarity search due to its sublinear performance guarantees. In the talk we will cover the background and some recent advances of LSH in Hamming space, including bit sampling LSH, Covering LSH, Fast Covering LSH. Experiments on synthetic and real-world data sets demonstrate that recent Fast Covering LSH is comparable (and often superior) to traditional hashing-based approaches for search radius up to 20 in high-dimensional Hamming space.

We study the consensus-halving problem of dividing an object into two portions, such that each of n agents has equal valuation for the two portions, given any set of (succinctly representable) valuation functions. The ε-approximate consensus-halving problem allows each agent to have an ε discrepancy on the values of the portions. We prove that computing an ε-approximate consensus-halving solution using n cuts is in PPA, and is PPAD-hard, where ε is some positive constant; the problem remains PPAD-hard when we allow a constant number of additional cuts. We also prove that it is NP-hard to decide whether a solution with n-1 cuts exists for the problem. Finally, we establish a reduction from the more general problem of approximate consensus-(1/k)-division to the known Necklace Splitting Problem, proving that the latter problem is PPAD-hard as a corollary. Joint work with Paul W. Goldberg, Søren Kristoffer Stiil Frederiksen and Jie Zhang.

This talk is a brief overview of my topics of research. In particular, the talk is focused on non-malleable protocols. Loosely speaking, in a non-malleable setting a man-in-the-middle (MIM) is defined as an adversary that can participates in many executions of the protocol and he has the power to omit, insert or modify messages at its choice. He has also full control over the scheduling of the messages. A non-malleable protocol is a protocol that remains secure even in presence of a MIM adversary. We will present the following results: - 3-round delayed-input concurrent non-malleable commitment from one-way permutations secure w.r.t. sub-exponentially time adversary; - 4-round delayed-input parallel non-malleable zero-knowledge (NMZK) from one-way functions; As an application of our 4-round delayed-input parallel NMZK we construct a 4-round multi-party protocol for coin tossing functionality based on one-way permutations.

The talk is divided in two parts. 1) Proofs of partial knowledge allow a prover to prove knowledge of witnesses for k out of n instances of NP languages. Cramer, Schoenmakers and Damgaard [CDS94] provided an efficient construction of a 3-round public-coin witness-indistinguishable (k,n)-proof of partial knowledge for any NP language, by cleverly combining n executions of sigma-protocols for that language. This transform assumes that all n instances are fully specified before the proof starts, and thus directly rules out the possibility of choosing some of the instances after the first round. In the first part of the talk we see how to have a proof of partial knowledge where knowledge of all n instances can be postponed. Indeed, this property is achieved only by inefficient constructions requiring NP reductions (Lapidot and Shamir, CRYPTO 1990). 2) Katz and Ostrovsky in CRYPTO 2004 showed a 5 (optimal) round construction assuming trapdoor permutations for the general case where both players receive the output. They also proved that their result is round optimal. This lower bound has been recently revisited by Garg et al. in Eurocrypt 2016 where a 4 (optimal) round protocol is showed assuming a simultaneous message exchange channel. Unfortunately there is no instantiation of the protocol of Garg et al. under standard polynomial time hardness assumptions. In this second part of the talk will be showed how to construct a 4-round protocol for secure two-party computation (when a simultaneous message exchange channel is available) with black-box simulation, assuming trapdoor permutations against polynomial-time adversaries. Moreover, in order to provide such a construction two additional results will be showed: a) an oblivious transfer protocol from trapdoor permutations that enjoys special properties; b) a new security proof approach that avoids "rewinding issues".

One class learning denotes the set of methods designed to isolate a target data set from unexpected data which are considered as anomalies or outliers. This problem is commonly considered as a challenging task because we are often faced with a double barrier: scarcity and dimensionality. "Scarcity" means that it is difficult to collect enough examples to build a representative class. This is often the case in the applications where anomalies are rare and therefore difficult to collect. This limited representativeness shows up the failings of standard machine learning algorithms for classification which are based on the statistical balance of the classes. Secondly, searching for anomalies in high-dimensional data is also another challenging issue which is directly related to the general problem of 'curse of dimensionality'. Indeed, in high dimensional space, the data is sparse and the notion of proximity fails to retain its meaningfulness. In this talk, in order to solve these issues, I propose an extension of a previous work which is based on a new contrast measure to separate a target data set from outliers. This generalization is formulated from the null space theory. More precisely, the Null space based strategy is a way to solve our problem when the dimensionality of the data is higher than the sample size. This problem is named the small sample size problem. This is a common case in image processing, for instance for face recognition problems. In this specific subspace, our learning data set is reduced to a single point making the classification easier (up to a given threshold). The decision boundary will be built from a target data sample beforehand collected and one counter example "artificially" located at the origin of the feature space. Next, I will compare our approach with other novelty detectors on numerous data sets. Lastly, we apply the proposed methodology to extract stationary/moving objects in video sequences which are subjected to varying weather conditions. The goal is to learn the lighting variations of the background which is considered as the target data set and then to classify the moving image structures as outliers.

Constraint-hiding constrained PRFs (CHCPRFs), initially studied by Boneh, Lewi and Wu [PKC 2017], are constrained PRFs where the constrained key hides the description of the constraint. Envisioned with powerful applications such as searchable encryption, private-detectable watermarking and symmetric deniable encryption, the only known candidates of CHCPRFs were based on indistinguishability obfuscation or multilinear maps with strong security properties. In this work we build CHCPRFs for all NC1 circuits from the Learning with Errors assumption. The construction is based on the graph-induced multilinear maps proposed by Gentry, Gorbunov and Halevi [TCC 2015]. In the talk I will demonstrate how to use GGH15 safely, and mention some open problems related to GGH15 and CHCPRF. Based on joint work with Ran Canetti. https://eprint.iacr.org/2017/143

The topic of this talk is the oblivious evaluation of a linear function f(x) = ax + b. This problem is non-trivial in the sense that a sender chooses (a, b) and the receiver x, but the receiver may only learn f(x), while the sender learns nothing about a or b. We present a highly efficient and UC-secure construction of OLE in the OT-hybrid model that requires only O(1) OTs per OLE. The construction is based on noisy encodings. Our main technical contribution solves a problem left open in previous work, namely we show in a generic way how to achieve full simulation-based security from noisy encodings. All previous constructions using noisy encodings achieve only passive security. From our OLE construction we derive improvements in MPC and OPE over existing results from the literature.

We introduce a batch version of sparse recovery, where the goal is to construct A'₁,...,A'_m ∈ Rⁿ that estimate a sequence of unknown signals A₁,...,A_m ∈ Rⁿ, using linear measurements, each involving exactly one signal vector, under an assumption of average sparsity. More precisely, we want to have ∑_{j ∈ [m]}|A_j- A_j'|_p^p ≤ C · min { ∑_{j ∈ [m]}|A_j - A_j^*|_p^p } (1) for predetermined constants C ≥ 1 and p, where the minimum is over all A₁^*,...,A_m^* ∈ Rⁿ that are k-sparse on average (strictly speaking, k is given as input). The special case m=1 is known as stable sparse recovery. The main question is what is the minimal number of measurements required to satisfy (1). We resolve the question for p ∈ {1,2} up to polylogarithmic factors, by presenting a randomized adaptive scheme that with high probability performs Õ(km) measurements and gives an output satisfying (1). Additionally, we show that adaptivity is necessary for every non-trivial scheme that solves the batch sparse recovery problem. Joint work with Alexandr Andoni, Robert Krauthgamer and Eric Price.

Blockchains offer users the ability to securely transfer money without a trusted party or intermediary, and the transparency of blockchain transactions also enables public verifiability. This openness, however, comes at a cost to user privacy, as even though the pseudonyms users go by within the blockchain are not linked to their real-world identities, all movements of money among these pseudonyms are still traceable. This talk will introduce Möbius, a system that prevents anyone from being able to link senders and recipients and is compatible with the Ethereum blockchain. Möbius achieves strong notions of unlinkability, as even senders cannot identify which pseudonyms belong to the recipients to whom they sent money, and is also able to resist denial-of-service attacks. It also achieves a much lower off-chain communication complexity than all previous schemes, with senders and recipients needing to send only one initial message in order to engage in an arbitrary number of transactions.

We study exchange of information among rational agents, that is mechanism design in the setting where agents are rewarded using information only. This is an interesting setting motivated, among other things, by the increasing interest in secure multi party computation techniques. Moreover this is a very challenging setting, since information (as opposed to money) can be easily replicated and is not fungible i.e., the same piece of information might have different values for different agents. More specifically, we consider the setting of a joint computation where different agents have inputs of different quality or value, and their utility incorporates both correctness and exclusiveness, i.e. every agent is interested in improving the quality of his own piece of information while preventing other agents from doing so. Then we ask the question of whether we can design mechanisms that motivate all agents (even those with high-quality input) to participate in the computation. We begin answering this fascinating question by proposing mechanisms for natural joint computation tasks such as intersection, union, and average. Based on Joint work with Guang Yang

Data exploration is about efficiently extracting knowledge from data. It has a wide range of applications in exploratory analysis applications. In this seminar, I will present my recent research works in this area, namely, top-k insights extraction and k-shortlist preference space, which will appear in SIGMOD'2017. The background of these two problems are given below. OLAP tools have been extensively used by enterprises to make better and faster decisions. Nevertheless, they require users to specify group-by attributes and know precisely what they are looking for. Our top-k insights extraction problem takes the first attempt towards automatically extracting top-k insights from multi-dimensional data from data warehouses. This is useful not only for non-expert users, but also reduces the manual effort of data analysts. Determining the impact regions of a given object (i.e., a specific product) is a key subroutine in many market analysis applications. Our k-shortlist preference space problem aims to identify impact regions of user preferences for which the given object is highly preferable (i.e., in top-k result list). This problem is important in potential customer identification, profile-based marketing, targeted advertising, etc. Biography: Bo Tang is currently a PhD candidate in the Department of Computing at the Hong Kong Polytechnic University. He is a member of Database Research Group. His main research interests are in the area of multidimensional data management, i.e., similarity search on high dimensional data, data exploration techniques on multidimensional dataset.

In this talk, we will consider the problem of how to consistently reroute flows in a network: this problem has recently received much attention by the networking community, and is motivated by the advent of so-called software-defined networks (a novel paradigm in computer networking). While many fundamental research questions are still open, I will provide an overview of the state-of-the-art. In particular, I will discuss three problem variants: (1) algorithms to consistently reroute flows in uncapacitated networks, such that loop-freedom is preserved, (2) algorithms to reroute flows such that basic security policies (namely waypointing) are preserved, and (3) algorithms to reroute flows in capacitated networks, ensuring congestion-freedom. If time permits (and there is interest), I will also discuss some security implications on today's shift toward more programmable and virtualized networks. The talk will be based on our HotNets 2014, PODC 2015, DSN 2016, SIGMETRICS 2016 papers, as well as on the arXiv paper: https://arxiv.org/abs/1611.09296 See also our recent survey on the topic: https://net.t-labs.tu-berlin.de/ stefan/survey-network-update-sdn.pdf Bio: Stefan Schmid is an Associate Professor at Aalborg University, Denmark. Before that, he was a senior research scientist at T-Labs, Berlin, a postdoc at TU Munich, and a PhD student at ETH Zürich. Stefan's research interests revolve around the fundamental problems of dynamic distributed systems and networks. Stefan has received the ComSoc ITC early-career award 2016 and is currently looking for PhD and Postdoc students. For more information, see: https://net.t-labs.tu-berlin.de/ stefan/

Practical anonymous credential systems are generally built around sigma-protocol ZK proofs. This requires that credentials be based on specially formed signatures. In this work, we ask whether we can instead use a standard (say, RSA, or (EC)DSA) signature that includes formatting and hashing messages, as a credential, and still provide privacy. Existing techniques do not provide efficient solutions for proving knowledge of such a signature: On the one hand, ZK proofs based on garbled circuits (Jawurek et al. 2013) give efficient proofs for checking formatting of messages and evaluating hash functions. On the other hand they are expensive for checking algebraic relations such as RSA or discrete-log, which can be done efficiently with sigma protocols. We design new constructions obtaining the best of both worlds: combining the efficiency of the garbled circuit approach for non-algebraic statements and that of sigma protocols for algebraic ones. We then show how to use these as building-blocks to construct privacy-preserving credential systems based on standard RSA and (EC)DSA signatures. Other applications of our techniques include anonymous credentials with more complex policies, the ability to efficiently switch between commitments (and signatures) in different groups, and secure two-partycomputation on committed/signed inputs. Joint work with Melissa Chase and Payman Mohassel.

In this talk, we will introduce a novel technique for secure computation over large inputs. Based on the Decisional Diffie-Hellman (DDH) assumption, we provide a new oblivious transfer (OT) protocol with a laconic receiver. In particular, the laconic OT allows a receiver to commit to a large input D (of length m) via a short message. Subsequently, a single short message by a sender allows the receiver to learn s_Di , where s₀ , s₁ and i ∈ [m] are dynamically chosen by the sender. All prior constructions of OT required the receiver message to grow with m. Such an OT is apt for realizing secure computation over large data. More specifically, we show applications of laconic OT to non-interactive secure computation and homomorphic encryption for RAM programs.

We revisit the question of constructing public-key encryption and signature schemes with security in the presence of bounded leakage and tampering memory attacks. For signatures we obtain the first construction in the standard model; for public-key encryption we obtain the first construction free of pairing (avoiding non-interactive zero-knowledge proofs). Our constructions are based on generic building blocks, and, as we show, also admit efficient instantiations under fairly standard number-theoretic assumptions.

In this talk I give an introduction to turn-based stochastic games, a special case of Shapley's stochastic games from 1953, and show how they relate to linear programming and Markov decision processes. I present some recent algorithmic breakthroughs from the area, focusing in particular on my own work, and describe the future research directions that I find most promising. My main focus will be on simplex algorithms; the classical combinatorial algorithm for linear programming.

Many cryptosystems widely used today can be efficiently broken using a quantum computer. Experts estimate that within the next two decades large enough quantum computers will be constructed. In order to keep our communications secure, the cryptographic community is developing new cryptosystems whose security can be based on quantum-resistant problems. One of these problems is solving systems of multivariate quadratic polynomial equations over finite fields. Cryptosystems build from the hardness of this problem are known as Multivariate Public Key Cryptosystems. In this seminar we will take a look at some of the cryptosystems developed within this field and explore attacks against them and improvements.

We study the following computational problem: for which values of k, the majority of n bits MAJ_n can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJ_k o MAJ_k. We observe that the minimum value of k for which there exists a MAJ_k o MAJ_k circuit that has high correlation with the majority of n bits is equal to Θ(n^1/2). We then show that for a randomized MAJ_k o MAJ_k circuit computing the majority of n input bits with high probability for every input, the minimum value of k is equal to n^2/3+o(1). We show a worst case lower bound: if a MAJ_k o MAJ_k circuit computes the majority of n bits correctly on all inputs, then k ≥ n^13/19+o(1). This lower bound exceeds the optimal value for randomized circuits and thus is unreachable for pure randomized techniques. For depth 3 circuits we show that a circuit with k=O(n^2/3) can compute MAJ_n correctly on all inputs. The talk is based on joint results with Alexander Kulikov.

In this talk I will propose a way to carry out verifiable computation over cryptocurrency networks. Cryptocurrencies (e.g. Bitcoin, Ethereum) have two appealing features as a base for verifiable computation: (i) they can execute code in their blockchain (although with certain limitations); (ii) as platforms for financial transactions, they are a natural choice for rationality assumptions. Within research in cryptographic protocols, rationality assumptions have proven to achieve complexities otherwise impossible. A high-level description of my proposal is to run rational protocol for delegation of computation on the Ethereum network. The material in this talk is still a work in progress.

We show that in the document exchange problem, where Alice holds x ∈ {0,1}ⁿ and Bob holds y ∈ {0,1}ⁿ, Alice can send Bob a message of size O(K(log² K+log n)) bits such that Bob can recover x using the message and his input y if the edit distance between x and y is no more than K, and output ``error'' otherwise. Both the encoding and decoding can be done in time Õ(n+poly(K)). This result significantly improves the previous communication bounds under polynomial encoding/decoding time. We also show that in the referee model, where Alice and Bob hold x and y respectively, they can compute sketches of x and y of sizes poly(K log n) bits (the encoding), and send to the referee, who can then compute the edit distance between x and y together with all the edit operations if the edit distance is no more than K, and output ``error'' otherwise (the decoding). To the best of our knowledge, this is the first result for sketching edit distance using poly(K log n) bits. Moreover, the encoding phase of our sketching algorithm can be performed by scanning the input string in one pass. Thus our sketching algorithm also implies the first streaming algorithm for computing edit distance and all the edits exactly using poly(K log n) bits of space.

The discrete logarithm problem (DLP) is classified as a one-way function, and therefore used within public key cryptography. Nowadays, the standard algorithm to compute the discrete logarithm is the index-calculus algorithm. This algorithm has sub-exponential time complexity and consists of four phases: (i) factor base, (ii) generation of relations, (iii) linear algebra and (iv) descent. The descent phase is performed in steps, and the most complex operation in these steps is to determine whether a polynomial is smooth with respect to a given degree. For this, one can either factorise the polynomial or perform a smoothness test on it. The latter approach is more efficient from a computational perspective. This work focuses on the smoothness test for polynomials. The main objective was to develop an efficient implementation in C of this test in order to compute the discrete logarithm in a field of cryptographic interest. We decided to work with the finite field F_3^6x509. Specifically, our smoothness test implementation was used in the continued-fraction and classical steps of the descent phase of the index-calculus algorithm. Before this work, there were no reported results on the computation of the discrete logarithm for the chosen field. On July 2016, it was announced that our computation in F_3^6x509 finished taking about 200 core-years, setting a new record in a finite field of characteristic 3.

In this talk we are interested in Unique Sink Orientations (USO): an abstract optimization framework that generalizes (among other things) Linear Programming. These are orientations of the edges of the hypercube graph that satisfy certain properties. USO is a concept that has been well-studied in the last 15 years; we will introduce and motivate it with examples and references. In addition, we consider Random Edge (RE). This is arguably the most natural randomized pivot rule for the simplex algorithm: at every vertex pick an edge uniformly at random from the set of outgoing edges and move to the other endpoint of this edge. Back in 2001, Welzl introduced the concept of niceness of a USO, in an effort to better understand the behavior of RE. Niceness implies natural upper bounds for RE and, moreover, it inspires a very simple derandomization. We introduce this concept in detail and give answers to the related questions asked by Welzl in 2001. The results presented are joint work with Bernd Gärtner.

We study the question of how much interaction is needed for unconditionally secure multiparty computation. We first consider the number of messages that need to be sent to compute a Boolean function with semi-honest security, where all n parties learn the result. We consider two classes of functions called t-difficult and t-very difficult functions, where t refers to the number of corrupted players. For instance, the AND of an input bit from each player is t-very difficult while the XOR is t-difficult but not t-very difficult. We show lower bounds on the message complexity of both types of functions, considering two notions of message complexity called conservative and liberal, where conservative is the more standard one. In all cases the bounds are Ω(nt). We also show (almost) matching upper bounds for t=1 and functions in a rich class PSM _eff including non-deterministic log-space, as well as a stronger upper bound for the XOR function. In particular, we find that the conservative message complexity of 1-very difficult functions in PSM _eff is 2n, while the conservative message complexity for XOR (and t=1) is 2n-1. Next, we consider round complexity. It is a long-standing open problem to determine whether all efficiently computable functions can also be efficiently computed in constant-round with unconditional security. Motivated by this, we consider the question of whether we can compute any function securely, while minimizing the interaction of some of the players? And if so, how many players can this apply to? Note that we still want the standard security guarantees (correctness, privacy, termination) and we consider the standard communication model with secure point-to-point channels. We answer the questions as follows: for passive security, with n=2t+1 players and t corruptions, up to t players can have minimal interaction, i.e., they send 1 message in the first round to each of the t+1 remaining players and receive one message from each of them in the last round. Using our result on message complexity, we show that this is (unconditionally) optimal. For malicious security with n=3t+1 players and t corruptions, up to t players can have minimal interaction, and we show that this is also optimal. Joint work with Jesper Buus Nielsen, Rafail Ostrovsky and Adi Rosén.

In this talk, we will discuss how to infer a function on all vertices of a graph from observations on a few of the vertices. Given real-valued observations on some vertices, we find a smooth extension to all vertices. We study both minimal Lipschitz extensions and the absolutely minimal Lipschitz extension (AMLE) which is the limit of p-Laplacian regularization. These extensions generalize naturally to directed graphs. We develop provably fast algorithms for computing these extensions. Our implementation of these algorithms runs in minutes on graphs with millions of vertices. We provide experimental evidence that AMLE performs well for spam webpage detection. To handle noisy input graphs, we develop regularization techniques for Lipschitz extensions and give algorithms for outlier removal. The latter is surprising, as the analogous least-squares problem is NP-hard.

The problem of verifiable data streaming (VDS) considers a client with limited computational and storage capacities that streams an a-priori unknown number of elements to an untrusted server. The client may retrieve and update any outsourced element. Other parties may verify each outsourced element's integrity using the client's public-key. All previous VDS constructions incur a bandwidth and computational overhead on both client and server side, which is at least logarithmic in the number of transmitted elements. We propose two novel, fundamentally different approaches to constructing VDS. The first scheme is based on a new cryptographic primitive called Chameleon Vector Commitment (CVC). A CVC is a trapdoor commitment scheme to a vector of messages where both commitments and openings have constant size. Using CVCs we construct a tree-based VDS protocol that has constant computational and bandwidth overhead on the client side. The second scheme shifts the workload to the server side by combining signature schemes with cryptographic accumulators. Here, all computations are constant, except for queries, where the computational cost of the server is linear in the total number of updates.

Noisy channels can be very useful in cryptography, allowing to design unconditionally secure protocols for primitives like commitment and OT. As it turns out that noisy channels are valuable resources for cryptography, it becomes important to understand the optimal way in which these noisy channels can be used for implementing cryptographic tasks. In this talk we will explore the concepts of commitment and OT capacities of noisy channels. More specifically, we will focus on the commitment capacity of Unfair Noisy Channels and on the OT capacity of Generalized Erasure Channel.

In this talk, I discuss a technique for computing approximate single-source shortest paths using a hop set. A hop set is a set of weighted edges that, when added to the graph, allows to approximate all distances by using only a few edges. This approach was previously used by Cohen in the PRAM model [STOC '94]. I will show how to obtain almost tight approximate SSSP algorithms in both the distributed setting (CONGEST model) and the centralized deletions-only setting using a suitable hop set. Joint work with Monika Henzinger and Danupon Nanongkai.

Given a set Z of n positive integers and a target value t, the SubsetSum problem asks whether any subset of Z sums to t. A textbook pseudopolynomial time algorithm by Bellman from 1957 solves SubsetSum in time O(nt). Here we present a simple and elegant randomized algorithm running in time soft-O(n+t). This improves upon a classic result and is likely to be near-optimal, since it matches conditional lower bounds from SetCover and k-Clique. We also present a new algorithm with pseudopolynomial time and polynomial space.

We present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in \hatO(n³/log⁴ n) time, where the \hatO notation suppresses poly(loglog) factors. This improves the previous best combinatorial algorithm by Chan that runs in \hatO(n³/log³ n) time. Our algorithm generalizes the divide-and-conquer strategy of Chan's algorithm. Moreover, we propose a general framework for detecting triangles in graphs and computing Boolean matrix multiplication. Roughly speaking, if we can find the ``easy parts'' of a given instance efficiently, we can solve the whole problem faster than n³.

We study the two-party communication complexity of finding an approximate Brouwer fixed-point of a composition of two Lipschitz functions g*f, where Alice knows f and Bob knows g. We prove an essentially tight deterministic communication lower bound on this problem, using a "geometric" adaptation of the Raz-McKenzie simulation theorem, allowing us to "smoothly lift" the query lower bound for approximate fixed-point ([HPV'89]) from the oracle model to the two-party model. We show that a slightly "smoother" version of our lower bound would imply an N^Ω(1) deterministic lower bound on the well known open problem of finding an approximate Nash equilibrium in an N*N 2-player game, where each player initially knows only his own payoff matrix. In contrast, the non-deterministic communication complexity of this problem is only polylog(N). Such improvement would also imply an exp(k) communication lower bound for finding an Ω(1)-Nash equilibrium in k-player games. Joint work with Tim Roughgarden.

I consider the problem of representing integers in close to optimal number of bits to support increment and decrement operations efficiently as described in "Integer Representations towards Efficient Counting in the Bit Probe Model" by Gerth Stølting Brodal, Mark Greve, Vineet Pandey, Srinivasa Rao Satti. [BGPS2013]. The problem is studied in the bit probe model. I analyse the number of bits read to perform the operation in the worst case. Such representations together with the corresponding increment and decrement algorithms are called counters. The article [BGPS2013] contains two basic constructions: one uses n bits to represent exactly 2ⁿ values and requires n-1 reads in the worst case, the other one is redundant (represents less than 2ⁿ values), but requires only a logarithmic number of reads for incrementing. The only known lower bound for number of reads to increment a non-redundant counter was logarithmic. Reducing the gap between the linear upper bound and logarithmic lower bound remained an open problem. I present a proof of a linear lower bound for the number of bits read in the worst case.

For competitive analysis of online algorithms, it is assumed that an online algorithm has no information at all about the input before it arrives. This leaves open the question of whether or not a small amount of information (advice) about the input could significantly improve the performance of an online algorithm. We introduce a simple but surprisingly useful technique for proving lower bounds on online algorithms with a limited amount of advice about the future. For example, using this technique, we show that: (1) A paging algorithm needs linear advice to achieve a competitive ratio better than log k, where k is the cache size. Previously, it was only known that linear advice was necessary to achieve a constant competitive ratio smaller than 5/4. (2) Every vertex coloring algorithm with a sublinear competitive ratio must use superlinear advice. Previously, it was only known that superlinear advice was necessary to be optimal. For certain online problems, including the MTS, k-server, paging, list update, and dynamic binary search tree problem, we show that randomization and sublinear advice are equally powerful (if the underlying metric space or node set is finite). This means that several long-standing open questions regarding randomized online algorithms can be equivalently stated as questions regarding online algorithms with sublinear advice. For example, we show that there exists a deterministic O(log k)-competitive k-server algorithm with advice complexity o(n) if and only if there exists a randomized O(log k)-competitive k-server algorithm without advice.

I will show how constraints on a secret-sharing scheme can be used to prove a linear communication lower bound for three-party parallel bitwise AND.

The most classic textbook hash function, e.g. taught in CLRS [MIT Press '09], is h(x) = ((ax+b) mod p) mod m where a,b ∈ {0,1,...,p-1} are chosen uniformly at random. It is known that (*) is 2-independent and almost uniform provided p >> m. This implies that when using (*) to build a hash table with chaining, the expected query time is O(1) and the expected length of the longest chain is O(√n). This result holds for any 2-independent hash function. No hash function can improve on the expected query time, but the upper bound on the expected length of the longest chain is not known to be tight for (*). Partially addressing this problem, Alon et al. [STOC '97] proved the existence of a class of linear hash functions such that the expected length of the longest chain is Ω(√n) and leave as an open problem to decide which non-trivial properties (*) has. We make the first progress on this fundamental problem showing that the expected length of the longest chain is at most n^1/3+o(1), showing that the performance of (*) is similar to that of a 3-independent hash function for which we can prove an upper bound of O(n^1/3). As a lemma we show that within a fixed set of integers there are few pairs such that the height of the ratio of the pairs are small. This is proved using a mixture of techniques from additive combinatorics and number theory, and we believe that the result might be of independent interest. For a natural variation of (*) where we look at the most significant instead of the least significant bits of (ax+b) mod p to create the hash value, we show that it is possible to apply second order moment bounds even when a hash value is fixed. As a consequence: - For min-wise hashing it was known that any key from a set of n keys have the smallest hash value with probability O(1/√n). We improve this to n^-1+o(1). - For linear probing it was known that the worst case expected query time is O(√n). We improve this to n^o(1).

The dynamic shortest paths problem on planar graphs asks us to preprocess a planar graph G such that we may support insertions and deletions of edges in G as well as distance queries between any two nodes u,v subject to the constraint that the graph remains planar at all times. This problem has been extensively studied in both the theory and experimental communities over the past decades and gets solved millions of times every day by companies like Google, Microsoft, and Uber. The best known algorithm performs queries and updates in Õ(n^2/3) time, based on ideas of a seminal paper by Fakcharoenphol and Rao [FOCS'01]. A (1+ε)-approximation algorithm of Abraham et al. [STOC'12] performs updates and queries in Õ(n^1/2) time. An algorithm with O(polylog(n)) runtime would be a major breakthrough. However, such runtimes are only known for a (1+ε)-approximation in a model where only restricted weight updates are allowed due to Abraham et al. [SODA'16], or for easier problems like connectivity. In this paper, we follow a recent and very active line of work on showing lower bounds for polynomial time problems based on popular conjectures, obtaining the first such results for natural problems in planar graphs. Such results were previously out of reach due to the highly non-planar nature of known reductions and the impossibility of "planarizing gadgets". We introduce a new framework which is inspired by techniques from the literatures on distance labelling schemes and on parameterized complexity. Using our framework, we show that no algorithm for dynamic shortest paths or maximum weight bipartite matching in planar graphs can support both updates and queries in amortized O(n^1/2-ε) time, for any ε>0, unless the classical all-pairs-shortest-paths problem can be solved in truly subcubic time, which is widely believed to be impossible. We extend these results to obtain strong lower bounds for other related problems as well as for possible trade-offs between query and update time. Interestingly, our lower bounds hold even in very restrictive models where only weight updates are allowed. See also: http://arxiv.org/abs/1605.03797 Joint work with Amir Abboud, Stanford University

Most research in anonymous communication assumes some amount of trust: for example that there is at least one server that can be trusted. In this talk we will see what happens if no active participant can be trusted and an adversary can see all communication. We consider both the model where the adversary's computational power is bounded and the model where it is unbounded. In both models, we will see that it is possible to achieve something anonymously. However, we will also show very low upper bounds on how much information you can send. This justifies the assumption of trust in anonymity research. Part of this talk is based on joint work with Claudio Orlandi.

Talk will focus on few cool* proofs of quite easy yet important (and sometimes misquoted) facts. *-I mean seriously cool. 1) We will discuss sizes of (Universal) Hashing Families: H is a universal hashing family if for all x ≠ y P_{h ← H} (h(x)=h(y))=2^-m where m is the size of output of h. We will discuss the sizes of hashing families (this is not a rocket science but for some reason very few people actually has seen the proofs). We will relax universality condition (collision probably will not be optimal) and we will show that the family can be significantly smaller, the second argument is a probabilistic argument, very similar to proof of Johnson-Lindenstrauss lemma (used in datamining or something). 2) Then we will discuss the following lemma: if H_∞(X)=k then X can be represented as a convex combination of flat distributions Y_i such that H_∞(Y_i)=k lemma allows us to prove things for flat distributions and then immediately generalize it for any distribution. Obviously lemma above is true only if 2^k is Natural number. This lemma is almost always cited incorrectly. We will present a short but cool proof of above lemma using extreme points methods (Krein-Milman theorem), ALL conditions in K-M are trivially fulfilled in finite fields thus making it a nice and EASY tool.

We pioneer techniques to extract randomness from massive unstructured data. This is the first work that achieves theoretical guarantees with a practical implementation. It includes innovated constructions, lower bounds, implementation and extensive validation of our systems-level software system. The computation over huge input size is often modeled by streaming algorithms. In this work we consider a pragmatic multi-stream model. Here every algorithm uses a small (e.g., polylog(n)) local memory and constant many (e.g., 2) streams which are space-unbounded tapes, and the algorithm reads and writes them sequentially from left to right. Unlike the traditional view in Machine Learning or Data Mining, we view Big Data as a low-quality source of entropy, from which we can extract high-quality (i.e. almost-uniform) random bits. We propose a randomness extractor that uses O(loglog n) passes over 2 streams. This is asymptotically optimal according to our lower bound result. Furthermore, we implement and experimentally validate our randomness extractor on real-world data including videos, social network feeds, DNA sequenced data, and so on. Its efficiency outperforms every known extractor (e.g. 10 hours vs. 100,000 years), and the quality of the extracted bits is certified by standardized tests. The related papers are joint work with Periklis Papakonstantinou.

How many times did you or a colleague of yours implement a prototype for a MPC protocol or application from scratch? Each time building the network stack, storage options and newly invented architecture. Well, now your days of doing tedious work is over. Introducing FRESCO, created by the Alexandra Institute as well as a few guys formerly from the CS department, this framework will grant you: 1) Easy to produce protocols. 2) Fair comparison with other protocols also implemented in FRESCO. 3) Access for your protocol to a large set of tests and applications already written. 4) The ability to produce applications independent of the underlying MPC protocol. What will this cost you? Nothing, it's free - open source. Find it at https://github.com/aicis/fresco.

Previously it was known that all l2 ε-heavy hitters could be found in the turnstile model in optimal O((1/ε²)lg n) words of space with O(lg n) update time and very slow O(nlg n) query time with 1/poly(n) failure probability, via the CountSketch of Charikar, Chen and Farach-Colton. The query time could be improved drastically using the "dyadic trick" to O((1/ε²) poly(lg n)), but the space and update time worsened to log² n to achieve such small failure probability. We show that the best of all worlds is possible: we give a new algorithm, ExpanderSketch, achieving O((1/ε²) lg n) space, O(lg n) update time, and O((1/ε²) poly(lg n)) query with 1/poly(n) failure probability. This is accomplished via a new reduction from the heavy hitters problem to a graph clustering problem of independent interest, which we solve using a new clustering algorithm CutCloseGrab which is guaranteed to find every single cluster regardless of the number of clusters or the comparative sizes between the cluster and the entire graph.

Computing the phylogenetic diversity of a set of species is an important part of many ecological case studies. More specifically, let T be a phylogenetic tree, and let R be a subset of its leaves representing the species under study. Specialists in ecology want to evaluate a function f(T,R) (a phylogenetic measure) that quantifies the evolutionary distance between the elements in R. But, in most applications, it is also important to examine how f(T,R) behaves when R is selected at random. The standard way to do this is to compute the mean and the variance of f among all subsets of leaves in T that consist of exactly |R| = r elements. For certain measures, there exist algorithms that can compute these statistics, under the condition that all subsets of r leaves are equiprobable. Yet, so far there are no algorithms that can do this exactly when the leaves in T are weighted with unequal probabilities. As a consequence, for this general setting, specialists try to compute the statistics of phylogenetic measures using methods which are both inexact and very slow. We present for the first time exact and efficient algorithms for computing the mean and the variance of phylogenetic measures when leaf subsets of fixed size are selected from T under a non-uniform random distribution. In particular, let T be a tree that has n nodes and depth d, and let r be a non-negative integer. We show how to compute in O((d + log n)n log n) time and O(n) space the mean and the variance for any measure that belongs to a well-defined class. We show that two of the most popular phylogenetic measures belong to this class: the Phylogenetic Diversity (PD) and the Mean Pairwise Distance (MPD). The random distribution that we consider is the Poisson binomial distribution restricted to subsets of fixed size r. More than that, we provide a stronger result; specifically for the PD and the MPD we describe algorithms that compute in a batched manner the mean and variance on T for all possible leaf-subset sizes in O((d + log n)n log n) time and O(n) space. For the PD and MPD, we implemented our algorithms that perform batched computations of the mean and variance. We also developed alternative implementations that compute in O((d + log n)n² ) time the same output. For both types of implementations, we conducted experiments and measured their performance in practice. Despite the difference in the theoretical performance, we show that the algorithms that run in O((d+log n)n² ) time are more efficient on datasets encountered in ecology, and numerically more stable. We also compared the performance of these algorithms with standard inexact methods that can be used in case studies. We show that our algorithms are outstandingly faster, making it possible to process much larger datasets than before. Our implementations will become publicly available through the R package PhyloMeasures.

We consider a new construction of locality-sensitive hash functions for Hamming space that is covering in the sense that is it guaranteed to produce a collision for every pair of vectors within a given radius r. The construction is efficient in the sense that the expected number of hash collisions between vectors at distance cr, for a given c > 1, comes close to that of the best possible data independent LSH without the covering guarantee, namely, the seminal LSH construction of Indyk and Motwani (FOCS '98). The efficiency of the new construction essentially matches their bound if cr = log(n)/k, where n is the number of points in the data set and k∈ N, and differs from it by at most a factor ln 4 in the exponent for general values of cr. As a consequence, LSH-based similarity search in Hamming space can avoid the problem of false negatives at little or no cost in efficiency.

In this paper, we develop a new communication model to prove a data structure lower bound for the dynamic interval union problem. The problem is to maintain a multiset of intervals I over [0, n] with integer coordinates, supporting the following operations:

• insert(a, b): add an interval [a, b] to I, provided that a and b are integers in [0, n];
• delete(a, b): delete a (previously inserted) interval [a, b] from I;
• query(): return the total length of the union of all intervals in I.