לוח שנה משולב

The  turnstile continual release model of differential privacy captures scenarios where a privacy-preserving real-time analysis  is sought for a dataset evolving  through additions and deletions.  In typical applications of real-time data analysis, both the length of the stream T and the size of the universe |U| from which data come can be extremely large. This motivates the study of private algorithms in the turnstile setting using space sublinear in both T and |U|. In this paper, we give the first sublinear space differentially private algorithms for the fundamental problems of counting distinct elements and $ell_p$-frequency moment estimation in the turnstile streaming model. For counting distinct elements, our algorithm achieves O(T^{1/3}) space and additive error, and a (1 eta)-relative approximation for all eta in (0,1). Our result significantly improves upon the space requirements of the state-of-the-art for this problem in this model, which has a linear dependency in both T and |U|, while still achieving an additive error that is close to the known Omega(T^{1/4}) lower bound for arbitrary streams. This addresses an open question posed in prior work about designing low-memory mechanisms for this problem. For the more general problem of L_p-frequency moment estimation, our algorithm achieves an additive error and space of O(T^{1/3}), and a (1 eta)-relative approximation for all eta in (0,1). We also give a space lower bound for this problem, which shows that any algorithm that uses our techniques must use space Omega}(T^{1/3}). Joint work with Alessandro Epasto, Jieming Mao, Tamalika Mukherjee, Tingting Ou, and Peilin Zhong.

An error-correcting code is locally testable (LTC) if there is a random tester that reads only a small number of bits of a given word and decides whether the word is in the code, or at least close to it. A long-standing problem asks if there exists such a code that also satisfies the golden standards of coding theory: constant rate and constant distance. Unlike the classical situation in coding theory, random codes are not LTC, so this problem is a challenge of a new kind. 

 

We construct such codes based on what we call (Ramanujan) Left/Right Cayley square complexes.  These objects seem to be of independent group-theoretic interest. The codes built on them are 2-dimensional versions of the expander codes constructed by Sipser and Spielman (1996). 

 

The main result and lecture will be self-contained. But we hope also to explain how the seminal work of Howard Garland (1972) on the cohomology of quotients of the Bruhat–Tits buildings of p-adic Lie group has led to this construction (even though it is not used at the end). 

 

Based on joint work with I. Dinur, S. Evra, R. Livne, and S. Mozes.

Electrocatalytically driven reactions that produce alternative fuels and chemicals are considered as a useful means to store renewable
energy in the form of chemical bonds. in recent years there has been a significant increase in research efforts aiming to develop highly
efficient electrocatalysts that are able to drive those reactions. Yet, despite having made significant progress in this field, there is still a
need for developing new materials that could function both as active and selective electrocatalysts.
In that respect, Metal–Organic Frameworks (MOFs), are an emerging class of hybrid materials with immense potential in electrochemical
catalysis. Yet, to reach a further leap in our understanding of electrocatalytic MOF-based systems, one also needs to consider the welldefined
structure and chemical modularity of MOFs as another important virtue for efficient electrocatalysis, as it can be used to fine-tune
the immediate chemical environment of the active site, and thus affect its overall catalytic performance. Our group utilizes Metal-Organic
Frameworks (MOFs) based materials as a platform for imposing molecular approaches to control and manipulate heterogenous
electrocatalytic systems. In this talk, I will present our recent study on electrocatalytic schemes involving MOFs, acting as: a) electroactive
unit that incorporates molecular electrocatalysts, or b) non-electroactive MOF-based membranes coated on solid heterogenous catalysts.

Climate change is having an impact on agricultural production and food
security. Rising temperatures, changes in rainfall patterns and extreme
weather events can reduce crop yields, sometimes dramatically. However,
climate change can also offer new opportunities, by generating more
favorable climatic conditions for agricultural production in certain regions
that were previously less productive. In order to assess the positive and
negative impacts of climate change on agriculture and identify effective
adaptation strategies, scientists have produced massive amounts of data
during the last two decades, conducting local experiments in agricultural
plots and using models to simulate the effect of climate on crop yields. In
most cases, these data are not pooled together and are analyzed separately
by different groups of scientists to assess the effects of climate change at a
local level, without any attempt to upscale the results at a larger scale. Yet, if
brought together, these data represent a rich source of information that are
relevant to analyze the effect of climate across diverse environmental
conditions. The wealth of data available has led to the emergence of a new
type of scientific activity, involving the retrieval of all available data on a
given subject and their synthesis into more robust and generic results. In this
talk, I review the statistical methods available to synthesize data generated
in studies quantifying the effect of climate change on agriculture. I discuss
both the most classic methods - such as meta-analysis - and more recent
methods based on machine learning. In particular, I show how this approach
can be used to map the impact of climate change on a large scale (national,
continental and global) from local data. I illustrate these methods in several
case studies and present several research perspectives in this area.

Alex Furman (University of Illinois)

Title: Picking out arithmetic rank-one locally symmetric manifolds among negatively curved ones

Abstract: The definition of an arithmetic locally symmetric manifold uses the language of algebraic groups and number theory. It turns out that in the world of negatively curved manifolds the arithmetic locally symmetric ones can be detected using abstract commensurators and coarse-geometry. Based on a joint work with Yanlong Hao.

-------

Balint Virag (University of Toronto)

Title: Random plane geometry: a gentle introduction

Abstract: Assign a random length of 1 or 2 to each edge of the square grid based on independent fair coin tosses. The resulting random geometry, first passage percloation, is conjectured to have a scaling limit.  Most random plane geometric models (including hidden geometries) should have the same scaling limit. I will explain the basics of the limiting geometry, the "directed landscape", the central object in the class of models named after
Kardar, Parisi and Zhang.

 

------

Emmanuel Breuillard (University of Oxford)

Title: Undecidable problems in linear groups.

Abstract: The Skolem problem asks to determine whether or not a linear recurrence sequence over the integers has a zero. No algorithm is known to answer this simple question. In this talk I will discuss recent joint work with G. Kocharyan, where we consider a wider class of problems, dealing with finitely generated subgroups of matrices,  and show their undecidability.

-------

Omer Angel (University of British Columbia)

Title: Interacting Polya urns.

Abstract: The classical Polya urn has counters X_t,Y_t that are incremented with probability proportional to their current value. I will discuss some of the many generalizations possible when multiple
Polya urns are coupled.

-------

Shmuel Weinberger (University of Chicago)

Title: How existential is topology?


Abstract:  Topology proves many things exist

A distribution is k-incompressible, Yao [FOCS ’82], if no efficient compression scheme compresses it to less than k bits. While being a natural measure, its relation to other computational analogs of entropy such as pseudoentropy (Hastad, Impagliazzo, Levin, and Luby [SICOMP 99]), and to other cryptographic hardness assumptions, was unclear.

We advance towards a better understating of this notion, showing that a k-incompressible distribution has (k-2) bits of next-block pseudoentropy, a refinement of pseudoentropy introduced by Haitner, Reingold, and Vadhan [SICOMP ’13]. We deduce that a samplable distribution X that is (H(X) 2)-incompressible, implies the existence of one-way functions.

Joint work with Iftach Haitner and Jad Silbak.