ERC FUNDED PROJECTS

We propose to establish a research group that will unveil the combinatorial nature of the second uncountable cardinal. This includes its Ramsey-theoretic, order-theoretic, graph-theoretic and topological features. Among others, we will be directly addressing fundamental problems due to Erdos, Rado, Galvin, and Shelah. While some of these problems are old and well-known, an unexpected series of breakthroughs from the last three years suggest that now is a promising point in time to carry out such a project. Indeed, through a short period, four previously unattainable problems concerning the second uncountable cardinal were successfully tackled: Aspero on a club-guessing problem of Shelah, Krueger on the club-isomorphism problem for Aronszajn trees, Neeman on the isomorphism problem for dense sets of reals, and the PI on the Souslin problem. Each of these results was obtained through the development of a completely new technical framework, and these frameworks could now pave the way for the solution of some major open questions. A goal of the highest risk in this project is the discovery of a consistent (possibly, parameterized) forcing axiom that will (preferably, simultaneously) provide structure theorems for stationary sets, linearly ordered sets, trees, graphs, and partition relations, as well as the refutation of various forms of club-guessing principles, all at the level of the second uncountable cardinal. In comparison, at the level of the first uncountable cardinal, a forcing axiom due to Foreman, Magidor and Shelah achieves exactly that. To approach our goals, the proposed project is divided into four core areas: Uncountable trees, Ramsey theory on ordinals, Club-guessing principles, and Forcing Axioms. There is a rich bilateral interaction between any pair of the four different cores, but the proposed division will allow an efficient allocation of manpower, and will increase the chances of parallel success.

1 362 500 €

Start date: 2018-10-01, End date: 2023-09-30

Our senses face a constant barrage of information. Hence, understanding how our brain enables us to attend to relevant stimuli, while ignoring distractions, is of increasing biomedical importance. Recently, I discovered that the claustrum, a multi-sensory hub and recipient of extensive neuromodulatory input, enables resilience to distraction. In my ERC project, I will explore the mechanisms underlying claustral mediation of resilience to distraction and develop novel approaches for assessing and modulating attention in mice, with implications for humans. Transgenic mouse models that I identified as enabling selective access to claustral neurons overcome its limiting anatomy, making the claustrum accessible to functional investigation. Using this novel genetic access, I obtained preliminary results strongly suggesting that the claustrum functions to filter distractions by adjusting cortical sensory gain. My specific aims are: 1) To delineate the mechanisms whereby the claustrum achieves sensory gain control, by applying in-vivo cell-attached, multi-unit and fiber photometry recordings from claustral and cortical neurons during attention-demanding tasks. 2) To discriminate between the functions of the claustrum in multi-sensory integration and implementation of attention strategies, by employing multi-sensory behavioral paradigms while modulating claustral function. 3) To develop validated complementary physiological and behavioral protocols for adjusting claustral mediation of attention via neuromodulation. This study is unique in its focus and aims: it will provide a stringent neurophysiological framework for defining a key mechanism underlying cognitive concepts of attention, and establish a novel platform for studying the function of the claustrum and manipulating its activity. The project is designed to achieve breakthroughs of fundamental nature and potentially lead to diagnostic and therapeutic advances relevant to attention disorders.

1 995 000 €

Start date: 2018-03-01, End date: 2023-02-28

"The objective of this proposal is to study ""continuous"" (or C^0) objects, as well as C^0 properties of smooth objects, in the field of symplectic geometry and topology. C^0 symplectic geometry has seen spectacular progress in recent years, drawing attention of mathematicians from various background. The proposed study aims to discover new fascinating C^0 phenomena in symplectic geometry. One circle of questions concerns symplectic and Hamiltonian homeomorphisms. Recent studies indicate that these objects possess both rigidity and flexibility, appearing in surprising and counter-intuitive ways. Our understanding of symplectic and Hamiltonian homeomorphisms is far from being satisfactory, and here we intend to study questions related to action of symplectic homeomorphisms on submanifolds. Some other questions are about Hamiltonian homeomorphisms in relation to the celebrated Arnold conjecture. The PI suggests to study spectral invariants of continuous Hamiltonian flows, which allow to formulate the C^0 Arnold conjecture in higher dimensions. Another central problem that the PI will work on is the C^0 flux conjecture. A second circle of questions is about the Poisson bracket operator, and its functional-theoretic properties. The first question concerns the lower bound for the Poisson bracket invariant of a cover, conjectured by L. Polterovich who indicated relations between this problem and quantum mechanics. Another direction aims to study the C^0 rigidity versus flexibility of the L_p norm of the Poisson bracket. Despite a recent progress in dimension two showing rigidity, very little is known in higher dimensions. The PI proposes to use combination of tools from topology and from hard analysis in order to address this question, whose solution will be a big step towards understanding functional-theoretic properties of the Poisson bracket operator."

1 345 282 €

Start date: 2017-10-01, End date: 2022-09-30

The explosion of information around us has democratized knowledge and transformed its availability for people around the world. Still, since information is mediated through automated systems, access is bounded by their ability to understand language. Consider an economist asking “What fraction of the top-5 growing countries last year raised their co2 emission?”. While the required information is available, answering such complex questions automatically is not possible. Current question answering systems can answer simple questions in broad domains, or complex questions in narrow domains. However, broad and complex questions are beyond the reach of state-of-the-art. This is because systems are unable to decompose questions into their parts, and find the relevant information in multiple sources. Further, as answering such questions is hard for people, collecting large datasets to train such models is prohibitive. In this proposal I ask: Can computers answer broad and complex questions that require reasoning over multiple modalities? I argue that by synthesizing the advantages of symbolic and distributed representations the answer will be “yes”. My thesis is that symbolic representations are suitable for meaning composition, as they provide interpretability, coverage, and modularity. Complementarily, distributed representations (learned by neural nets) excel at capturing the fuzziness of language. I propose a framework where complex questions are symbolically decomposed into sub-questions, each is answered with a neural network, and the final answer is computed from all gathered information. This research tackles foundational questions in language understanding. What is the right representation for reasoning in language? Can models learn to perform complex actions in the face of paucity of data? Moreover, my research, if successful, will transform how we interact with machines, and define a role for them as research assistants in science, education, and our daily life.

1 499 375 €

Start date: 2019-04-01, End date: 2024-03-31

Tame geometry studies structures in which every definable set has a finite geometric complexity. The study of tame geometry spans several interrelated mathematical fields, including semialgebraic, subanalytic, and o-minimal geometry. The past decade has seen the emergence of a spectacular link between tame geometry and arithmetic following the discovery of the fundamental Pila-Wilkie counting theorem and its applications in unlikely diophantine intersections. The P-W theorem itself relies crucially on the Yomdin-Gromov theorem, a classical result of tame geometry with fundamental applications in smooth dynamics. It is natural to ask whether the complexity of a tame set can be estimated effectively in terms of the defining formulas. While a large body of work is devoted to answering such questions in the semialgebraic case, surprisingly little is known concerning more general tame structures - specifically those needed in recent applications to arithmetic. The nature of the link between tame geometry and arithmetic is such that any progress toward effectivizing the theory of tame structures will likely lead to effective results in the domain of unlikely intersections. Similarly, a more effective version of the Yomdin-Gromov theorem is known to imply important consequences in smooth dynamics. The proposed research will approach effectivity in tame geometry from a fundamentally new direction, bringing to bear methods from the theory of differential equations which have until recently never been used in this context. Toward this end, our key goals will be to gain insight into the differential algebraic and complex analytic structure of tame sets; and to apply this insight in combination with results from the theory of differential equations to effectivize key results in tame geometry and its applications to arithmetic and dynamics. I believe that my preliminary work in this direction amply demonstrates the feasibility and potential of this approach.

1 155 027 €

Start date: 2018-09-01, End date: 2023-08-31

Boolean function analysis is a topic of research at the heart of theoretical computer science. It studies functions on n input bits (for example, functions computed by Boolean circuits) from a spectral perspective, by treating them as real-valued functions on the group Z_2^n, and using techniques from Fourier and functional analysis. Boolean function analysis has been applied to a wide variety of areas within theoretical computer science, including hardness of approximation, learning theory, coding theory, and quantum complexity theory. Despite its immense usefulness, Boolean function analysis has limited scope, since it is only appropriate for studying functions on {0,1}^n (a domain known as the Boolean hypercube). Discrete harmonic analysis is the study of functions on domains possessing richer algebraic structure such as the symmetric group (the group of all permutations), using techniques from representation theory and Sperner theory. The considerable success of Boolean function analysis suggests that discrete harmonic analysis could likewise play a central role in theoretical computer science. The goal of this proposal is to systematically develop discrete harmonic analysis on a broad variety of domains, with an eye toward applications in several areas of theoretical computer science. We will generalize classical results of Boolean function analysis beyond the Boolean hypercube, to domains such as finite groups, association schemes (a generalization of finite groups), the quantum analog of the Boolean hypercube, and high-dimensional expanders (high-dimensional analogs of expander graphs). Potential applications include a quantum PCP theorem and two outstanding open questions in hardness of approximation: the Unique Games Conjecture and the Sliding Scale Conjecture. Beyond these concrete applications, we expect that the fundamental results we prove will have many other applications that are hard to predict in advance.

1 473 750 €

Start date: 2019-03-01, End date: 2024-02-29

Machine learning has rapidly evolved in the last decade, significantly improving accuracy on tasks such as image classification. Much of this success can be attributed to the re-emergence of neural nets. However, learning algorithms are still far from achieving the capabilities of human cognition. In particular, humans can rapidly organize an input stream (e.g., textual or visual) into a set of entities, and understand the complex relations between those. In this project I aim to create a general methodology for semantic interpretation of input streams. Such problems fall under the structured-prediction framework, to which I have made numerous contributions. The proposal identifies and addresses three key components required for a comprehensive and empirically effective approach to the problem. First, we consider the holistic nature of semantic interpretations, where a top-down process chooses a coherent interpretation among the vast number of options. We argue that deep-learning architectures are ideally suited for modeling such coherence scores, and propose to develop the corresponding theory and algorithms. Second, we address the complexity of the semantic representation, where a stream is mapped into a variable number of entities, each having multiple attributes and relations to other entities. We characterize the properties a model should satisfy in order to produce such interpretations, and propose novel models that achieve this. Third, we develop a theory for understanding when such models can be learned efficiently, and how well they can generalize. To achieve this, we address key questions of non-convex optimization, inductive bias and generalization. We expect these contributions to have a dramatic impact on AI systems, from machine reading of text to image analysis. More broadly, they will help bridge the gap between machine learning as an engineering field, and the study of human cognition.

1 932 500 €

Start date: 2019-02-01, End date: 2024-01-31

Despite decades of intensive research, there is no agreement about the general scheme of perception: Is the external object a trigger for a brain-internal process (open-loop perception, OLP) or is the object included in brain dynamics during the entire perceptual process (closed-loop perception, CLP)? HOWPER is designed to provide a definite answer to this question in the cases of human touch and vision. What enables this critical test is our development of an explicit CLP hypothesis, which will be contrasted, via specific testable predictions, with the OLP scheme. In the event that CLP is validated, HOWPER will introduce a radical paradigm shift in the study of perception, since almost all current experiments are guided, implicitly or explicitly, by the OLP scheme. If OLP is confirmed, HOWPER will provide the first formal affirmation for its superiority over CLP. Our approach in this novel paradigm is based on a triangle of interactive efforts comprising theory, analytical experiments, and synthetic experiments. The theoretical effort (WP1) will be based on the core theoretical framework already developed in our lab. The analytical experiments (WP2) will involve human perceivers. The synthetic experiments (WP3) will be performed on synthesized artificial perceivers. The fourth WP will exploit our novel rat-machine hybrid model for testing the neural applicability of the insights gained in the other WPs, whereas the fifth WP will translate our insights into novel visual-to-tactile sensory substitution algorithms. HOWPER is expected to either revolutionize or significantly advance the field of human perception, to greatly improve visual to tactile sensory substitution approaches and to contribute novel biomimetic algorithms for autonomous robotic agents.

2 493 441 €

Start date: 2018-06-01, End date: 2023-05-31

The drive for rewards controls almost every aspect of our behavior, from stereotypic reflexive behaviors to complex voluntary action. It is therefore not surprising that the symptoms of neurological disorders that interrupt reward processing, such as those stemming from drug-abuse and depression, include deficits in the capacity to make even simple movements. Accordingly, how do rewards drive and shape movements? The brain uses two major subcortical networks to drive behavior: the basal ganglia and the cerebellum. Both areas are essential for the control of movement as damage to either structure leads to severe motor disabilities. Research on the basal ganglia has highlighted their importance in the control of reward-driven behavior-but how the reward information interacts with sensorimotor signals to drive the motor periphery is unknown. By contrast, research on the cerebellum has focused primarily on how sensory error signals are used to optimize motor commands but has mostly ignored the modulatory factors that influence behavior, such as reward. My goal is to unify research on the basal ganglia and cerebellum in order to understand how the computations underlying the influence of reward on action are implemented in the brain. I hypothesize that rewards drive and shape the motor commands in both subcortical networks, albeit with differing behavioral functions. While in the basal ganglia, information about reward is used to mediate selection between multiple actions; I predict that, in the cerebellum, reward potentiates movements to drive more accurate behavior. I will use the monkey smooth pursuit eye movement system as a powerful model motor system to study the neural mechanisms by which reward influences motor processing. I will combine the use of novel behavioral paradigms together with novel application of neural recording and optogenetic stimulation in primates to probe activity of neurons in the cerebral cortex, basal ganglia, and cerebellum.

1 570 000 €

Start date: 2018-07-01, End date: 2023-06-30

Over the next five years, fifty billion new smart devices will be connected to the Internet of Things (IoT), creating a revolution in the way we interact with our environment. Such resource constrained devices will require lightweight cryptography to protect them and us from bad actors. Unfortunately, such schemes can be highly vulnerable: Two notable examples are the encryption schemes used in GSM cellular phones and in car remote controls - both broken by the PI. We claim that it is not sufficient to adjust the current design and analysis tools to the constrained environment. Instead, we must establish a new research methodology, aiming directly at the problems arising in the 'lightweight realm'. We plan to concentrate on four main directions. First, we will go 'a level up' to study the security of generic lightweight building blocks in order to find the minimal number of operations required to transition from insecure to secure designs. Second, when considering specific ciphers we will pursue practical low complexity attacks, which are more relevant to the lightweight realm than standard theoretical attacks. Third, we will pursue new directions toward establishing 'white-box cryptography' – a central challenge in IoT cryptography. Finally, we will explore further applications of discrete analysis to lightweight cryptography, trying to establish rigorous conditions under which the standard cryptanalytic techniques apply in order to avoid unnecessarily pessimistic security estimates. For the near future, we hope that our research will make it possible to detect and fix weaknesses in existing lightweight ciphers before they can be exploited by the 'bad guys'. Looking forward farther, we hope to understand how to design new secure lightweight ciphers for the billions of IoT devices to come.

1 487 500 €

Start date: 2017-10-01, End date: 2022-09-30

"The main goal of my research is to understand the origins of brain specialization and its flexibility across the lifespan. In our modern society Novel Sensory Experiences (NSE) and augmenting technologies are increasingly part of our everyday life (e.g. www.pokemongo.com). How does our brain deal with processing these new experiences? How much of its functional specializations and organization principle (e.g. topography in early sensory and motor brain areas) are already predefined by evolution and are locked after critical periods (i.e. early in life)? Our main hypothesis is that computational tasks, cognitive goals and partially innate network connectivity patterns, rather than sensory input per se, drive the emergence of brain specializations even after the critical periods pass. We base this also on our extensive experience with teaching blind to ""see"" with their ears using sensory substitution devices (SSDs) and the resulting brain specializations (including putative mechanisms). Here, we will extend, generalize and consolidate this theory by tracking in healthy adults the development of NSE (Novel since never experienced it before during life nor evolution). We suggest here to build 5 novel topographic devices (e.g. we developed recently the IRThermoSense for perceiving heat information and beyond walls thermal images without interfering with regular vision). We will also work with providing novel experiences to congenitally sensory deprived populations (e.g. deaf) to promote sensory restoration. In both cases, we aim to characterize the integration of NSEs in the brain using longitudinal self and supervised learning in virtual and real world environments and cutting-edge biologically inspired computational neuroimaging tools, with special emphasis on topography (similar to how natural senses are represented e.g. body homunculus and retinotopy), task-selective specializations, multisensory and sensorimotor binding, and the emergence of distal attribution. "

2 000 000 €

Start date: 2018-10-01, End date: 2023-09-30

Computer Science, in particular, Analysis of Algorithms and Computational-Complexity theory, classify algorithmic-problems into feasible ones and those that cannot be efficiently-solved. Many fundamental problems were shown NP-hard, therefore, unless P=NP, they are infeasible. Consequently, research efforts shifted towards approximation algorithms, which find close-to-optimal solutions for NP-hard optimization problems. The PCP Theorem and its application to infeasibility of approximation establish that, unless P=NP, there are no efficient approximation algorithms for numerous classical problems; research that won the authors --the PI included-- the 2001 Godel prize. To show infeasibility of approximation of some fundamental problems, however, a stronger PCP was postulated in 2002, namely, Khot's Unique-Games Conjecture. It has transformed our understanding of optimization problems, provoked new tools in order to refute it and motivating new sophisticated techniques aimed at proving it. Recently Khot, Minzer (a student of the PI) and the PI proved a related conjecture: the 2-to-2-Games conjecture (our paper just won Best Paper award at FOCS'18). In light of that progress, recognized by the community as half the distance towards the Unique-Games conjecture, resolving the Unique-Games conjecture seems much more likely. A field that plays a crucial role in this progress is Analysis of Boolean-functions. For the recent breakthrough we had to dive deep into expansion properties of the Grassmann-graph. The insight was subsequently applied to achieve much awaited progress on fundamental properties of the Johnson-graph. With the emergence of cloud-computing, cryptocurrency, public-ledger and Blockchain technologies, the PCP methodology has found new and exciting applications. This framework governs SNARKs, which is a new, emerging technology, and the ZCASH technology on top of Blockchain. This is a thriving research area, but also an extremely vibrant High-Tech sector.

2 059 375 €

Start date: 2019-10-01, End date: 2024-09-30

Asymptotic Geometric Analysis is a relatively new field, the young finite dimensional cousin of Banach Space theory, functional analysis and classical convexity. It concerns the {\em geometric} study of high, but finite, dimensional objects, where the disorder of many parameters and many dimensions is "regularized" by convexity assumptions. The proposed research is composed of several connected innovative studies in the frontier of Asymptotic Geometric Analysis, pertaining to the deeper understanding of two fundamental notions: Polarity and Central-Symmetry. While the main drive comes from Asymptotic Convex Geometry, the applications extend throughout many mathematical fields from analysis, probability and symplectic geometry to combinatorics and computer science. The project will concern: The polarity map for functions, functional covering numbers, measures of Symmetry, Godbersen's conjecture, Mahler's conjecture, Minkowski billiard dynamics and caustics. My research objectives are twofold. First, to progress towards a solution of the open research questions described in the proposal, which I consider to be pivotal in the field, including Mahler's conjecture, Viterbo's conjecture and Godberesen's conjecture. Some of these questions have already been studied intensively, and the solution is yet to found; progress toward solving them would be of high significance. Secondly, as the studies in this proposal lie at the meeting point of several mathematical fields, and use Asymptotic Geometric Analysis in order to address major questions in other fields, such as Symplectic Geometry and Optimal transport theory, my second goal is to deepen these connections, creating a powerful framework that will lead to a deeper understanding, and the formulation, and resolution, of interesting questions currently unattainable.

1 514 125 €

Start date: 2018-09-01, End date: 2023-08-31

In the context of data-intensive systems, data provenance captures the way in which data is used, combined and manipulated by the system. Provenance information can for instance be used to reveal whether data was illegitimately used, to reason about hypothetical data modifications, to assess the trustworthiness of a computation result, or to explain the rationale underlying the computation. As data-intensive systems constantly grow in use, in complexity and in the size of data they manipulate, provenance tracking becomes of paramount importance. In its absence, it is next to impossible to follow the flow of data through the system. This in turn is extremely harmful for the quality of results, for enforcing policies, and for the public trust in the systems. Despite important advancements in research on data provenance, and its possible revolutionary impact, it is unfortunately uncommon for practical data-intensive systems to support provenance tracking. The goal of the proposed research is to develop models, algorithms and tools that facilitate provenance tracking for a wide range of data-intensive systems, that can be applied to large-scale data analytics, allowing to explain and reason about the computation that took place. Towards this goal, we will address the following main objectives: (1) supporting provenance for modern data analytics frameworks such as data exploration and data science, (2) overcoming the computational overhead incurred by provenance tracking, (3) the development of user-friendly, provenance-based analysis tools and (4) experimental validation based on the development of prototype tools and benchmarks.

1 306 250 €

Start date: 2018-12-01, End date: 2023-11-30

Our remote memories, weeks to decades long, define who we are and how we experience the world, yet almost nothing is known about the neuronal ensembles encoding them, or the mechanisms underlying the transition from recent to remote memory. I propose a novel hypothesis explaining the selection of the ensembles supporting remote memories based on their activity, connectivity and stability. I further suggest that 'systems consolidation', underlying the transition from recent to remote memory, is implemented by ongoing interactions between brain regions. Finally, I propose a novel role for astrocytes in recent and remote memory. My Specific Objectives are to: 1) Provide multi-dimensional characterization of the neuronal ensembles supporting recent and remote memory, by using activity-based tagging to show how recent and remote recall ensembles differ in activity, connectivity and stability. 2) Perturb the functional connectivity underlying 'systems consolidation' by employing connectivity-based tagging to label specific hippocampal and cortical projection neurons, image their activity during recent and remote memory, and causally demonstrate their functional significance to systems consolidation. 3) Determine the role of astrocytes in recent and remote memory consolidation and retrieval. We will manipulate astrocytes to show their role in recent and remote memory, ensemble allocation, and long-distance communication between neuronal populations. We will image astrocytic activity during a memory task to test if they can independently encode memory features, and how their activity corresponds to that of the neurons around them. This pioneering ERC project, comprised of innovative and ambitious experiments going far and beyond the state of the art in the field, will drive considerable progress to our contemporary understanding of the transition from recent to remote memory, identifying ensemble dynamics and critical projections and how they are modulated by astrocytes.

1 637 500 €

Start date: 2018-11-01, End date: 2023-10-31

The proposal studies deterministic problems in the spectral theory of the Laplacian and in analytic number theory by using random models. I propose two projects in spectral theory on this theme, both with a strong arithmetic ingredient, the first about minimal gaps between the eigenvalues of the Laplacian, where I seek a fit with the corresponding quantities for the various conjectured universality classes (Poisson/GUE/GOE), and the second about curvature measures of nodal lines of eigenfunctions of the Laplacian, where I seek to determine the size of the curvature measures for the large eigenvalue limit. The third project originates in analytic number theory, on angular distribution of prime ideals in number fields, function field analogues and connections with Random Matrix Theory, where I raise new conjectures and problems on a very classical subject, and aim to resolve them at least in the function field setting.

1 840 625 €

Start date: 2019-02-01, End date: 2024-01-31

Modern society relies more and more on computing for managing complex safety-critical tasks (e.g., in medicine, avionics, economy). Correctness of computerized systems is therefore crucial, as incorrect behaviors might lead to disastrous outcomes. Still, correctness is a big open problem without satisfactory theoretical or practical solutions. This has dramatic effects on the security of our lives. The current practice in industry mainly employs testing which detects bugs but cannot ensure their absence. In contrast, formal verification can provide formal correctness guarantees. Unfortunately, existing formal methods are still limited in their applicability to real world systems since most of them are either too automatic, hindered by the undecidability of verification, or too manual, relying on substantial human effort. This proposal will introduce a new methodology of supervised verification, based on which, we will develop novel approaches that can be used to formally verify certain realistic systems. This will be achieved by dividing the verification process into tasks that are well suited for automation, and tasks that are best done by a human supervisor, and finding a suitable mode of interaction between the human and the machine. Supervised verification represents a conceptual leap as it is centered around automatic procedures but complements them with human guidance; It therefore breaks the classical pattern of automated verification, and creates new opportunities, both practical and theoretical. In addition to opening the way for developing tractable verification algorithms, it can be used to prove lower and upper bounds on the asymptotic complexity of verification by explicitly distilling the human's role. The approaches developed by this research will significantly improve system correctness and agility. At the same time, they will reduce the cost of testing, increase developers productivity, and improve the overall understanding of computerized systems.

1 499 528 €

Start date: 2018-04-01, End date: 2023-03-31

Much of the research on the foundations of graph algorithms is carried out under the assumption that the algorithm has full knowledge of the input data. In spite of the theoretical appeal and simplicity of this setting, the assumption that the algorithm has full knowledge does not always hold. Indeed uncertainty and partial knowledge arise in many settings. One example is where the data is very large, in which case even reading the entire data once is infeasible, and sampling is required. Another example is where data changes occur over time (e.g., social networks where information is fluid). A third example is where processing of the data is distributed over computation nodes, and each node has only local information. Randomization is a powerful tool in the classic setting of graph algorithms with full knowledge and is often used to simplify the algorithm and to speed-up its running time. However, physical computers are deterministic machines, and obtaining true randomness can be a hard task to achieve. Therefore, a central line of research is focused on the derandomization of algorithms that relies on randomness. The challenge of derandomization also arise in settings where the algorithm has some degree of uncertainty. In fact, in many cases of uncertainty the challenge and motivation of derandomization is even stronger. Randomization by itself adds another layer of uncertainty, because different results may be attained in different runs of the algorithm. In addition, in many cases of uncertainty randomization often comes with additional assumptions on the model itself, and therefore weaken the guarantees of the algorithm. In this proposal I will investigate the power of randomization in uncertain environments. I will focus on two fundamental areas of graph algorithms with uncertainty. The first area relates to dynamic algorithms and the second area concerns distributed graph algorithms.

1 500 000 €

Start date: 2019-10-01, End date: 2024-09-30