ERC FUNDED PROJECTS

Resolution of singularities is one of classical, central and difficult areas of algebraic geometry, with a centennial history of intensive research and contributions of such great names as Zariski, Hironaka and Abhyankar. Nowadays, desingularization of schemes of characteristic zero is very well understood, while semistable reduction of morphisms and desingularization in positive characteristic are still waiting for major breakthroughs. In addition to the classical techniques with their triumph in characteristic zero, modern resolution of singularities includes de Jong's method of alterations, toroidal methods, formal analytic and non-archimedean methods, etc. The aim of the proposed research is to study nearly all directions in resolution of singularities and semistable reduction, as well as the wild ramification phenomena, which are probably the main obstacle to transfer methods from characteristic zero to positive characteristic. The methods of algebraic and non-archimedean geometries are intertwined in the proposal, though algebraic geometry is somewhat dominating, especially due to the new stack-theoretic techniques. It seems very probable that increasing the symbiosis between birational and non-archimedean geometries will be one of by-products of this research.

1 365 600 €

Start date: 2018-05-01, End date: 2023-04-30

"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

Supercomputers are strategically crucial for facilitating advances in science and technology: in climate change research, accelerated genome sequencing towards cancer treatments, cutting edge physics, devising engineering innovative solutions, and many other compute intensive problems. However, the future of super-computing depends on our ability to cope with the ever increasing rate of faults (bit flips and component failure), resulting from the steadily increasing machine size and decreasing operating voltage. Indeed, hardware trends predict at least two faults per minute for next generation (exascale) supercomputers. The challenge of ascertaining fault tolerance for high-performance computing is not new, and has been the focus of extensive research for over two decades. However, most solutions are either (i) general purpose, requiring little to no algorithmic effort, but severely degrading performance (e.g., checkpoint-restart), or (ii) tailored to specific applications and very efficient, but requiring high expertise and significantly increasing programmers' workload. We seek the best of both worlds: high performance and general purpose fault resilience. Efficient general purpose solutions (e.g., via error correcting codes) have revolutionized memory and communication devices over two decades ago, enabling programmers to effectively disregard the very likely memory and communication errors. The time has come for a similar paradigm shift in the computing regimen. I argue that exciting recent advances in error correcting codes, and in short probabilistically checkable proofs, make this goal feasible. Success along these lines will eliminate the bottleneck of required fault-tolerance expertise, and open exascale computing to all algorithm designers and programmers, for the benefit of the scientific, engineering, and industrial communities.

1 824 467 €

Start date: 2019-06-01, End date: 2024-05-31

We present a large variety of novel lines of research in Homogeneous Dynamics with emphasis on the dynamics of the diagonal group. Both new and classical applications are suggested, most notably to • Number Theory • Geometry of Numbers • Diophantine approximation. Emphasis is given to applications in • Diophantine properties of algebraic numbers. The proposal is built of 4 sections. (1) In the first section we discuss questions pertaining to topological and distributional aspects of periodic orbits of the diagonal group in the space of lattices in Euclidean space. These objects encode deep information regarding Diophantine properties of algebraic numbers. We demonstrate how these questions are closely related to, and may help solve, some of the central open problems in the geometry of numbers and Diophantine approximation. (2) In the second section we discuss Minkowski's conjecture regarding integral values of products of linear forms. For over a century this central conjecture is resisting a general solution and a novel and promising strategy for its resolution is presented. (3) In the third section, a novel conjecture regarding limiting distribution of infinite-volume-orbits is presented, in analogy with existing results regarding finite-volume-orbits. Then, a variety of applications and special cases are discussed, some of which give new results regarding classical concepts such as continued fraction expansion of rational numbers. (4) In the last section we suggest a novel strategy to attack one of the most notorious open problems in Diophantine approximation, namely: Do cubic numbers have unbounded continued fraction expansion? This novel strategy leads us to embark on a systematic study of an area in homogeneous dynamics which has not been studied yet. Namely, the dynamics in the space of discrete subgroups of rank k in R^n (identified up to scaling).

1 432 730 €

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

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

Staggering amounts of information are stored in natural language documents, rendering them unavailable to data-science techniques. Information Extraction (IE), a subfield of Natural Language Processing (NLP), aims to automate the extraction of structured information from text, yielding datasets that can be queried, analyzed and combined to provide new insights and drive research forward. Despite tremendous progress in NLP, IE systems remain mostly inaccessible to non-NLP-experts who can greatly benefit from them. This stems from the current methods for creating IE systems: the dominant machine-learning (ML) approach requires technical expertise and large amounts of annotated data, and does not provide the user control over the extraction process. The previously dominant rule-based approach unrealistically requires the user to anticipate and deal with the nuances of natural language. I aim to remedy this situation by revisiting rule-based IE in light of advances in NLP and ML. The key idea is to cast IE as a collaborative human-computer effort, in which the user provides domain-specific knowledge, and the system is in charge of solving various domain-independent linguistic complexities, ultimately allowing the user to query unstructured texts via easily structured forms. More specifically, I aim develop: (a) a novel structured representation that abstracts much of the complexity of natural language; (b) algorithms that derive these representations from texts; (c) an accessible rule language to query this representation; (d) AI components that infer the user extraction intents, and based on them promote relevant examples and highlight extraction cases that require special attention. The ultimate goal of this project is to democratize NLP and bring advanced IE capabilities directly to the hands of domain-experts: doctors, lawyers, researchers and scientists, empowering them to process large volumes of data and advance their profession.

1 499 354 €

Start date: 2019-05-01, End date: 2024-04-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 proposed research deals with the extremes of logarithmically correlated fields, in both the Gaussian and non-Gaussian setups. Examples of such fields are branching random walks, the (discrete) two dimensional Gaussian free field, the set of points left uncovered by a random walk on the two dimensional torus at times close to the cover time of the torus, the (absolute) values of the characteristic polynomial of random matrices, Ginzburg-Landau models, and more. The proposal builds on recent progress in the study of the maximum and of the extremal process of the two dimensional Gaussian free field, which was made possible by Gaussian comparisons and the introduction of a refined version of the second moment method. The proposed research will develop the tools needed for building a general and flexible theory applicable to general logarithmically correlated fields. Applications to the multiplicative chaos will also be considered.

1 292 500 €

Start date: 2016-06-01, End date: 2021-12-31

Can we program computers in our native tongue? This idea, termed natural language programming, has attracted attention almost since the inception of computers themselves. From the point of view of software engineering (SE), efforts to program in natural language (NL) have relied thus far on controlled natural languages (CNL) -- small unambiguous fragments of English with strict grammars and limited expressivity. Is it possible to replace CNLs with truly natural, human language? From the point of view of natural language processing (NLP), current technology successfully extracts static information from NL texts. However, human-like NL understanding goes far beyond such extraction -- it requires dynamic interpretation processes which affect, and are affected by, the environment, update states and lead to action. So, is it possible to endow computers with this kind of dynamic NL understanding? These two questions are fundamental to SE and NLP, respectively, and addressing each requires a huge leap forward in the respective field. In this proposal I argue that the solutions to these seemingly separate challenges are actually closely intertwined, and that one community's challenge is the other community's stepping stone for a huge leap, and vice versa. Specifically, I propose to view executable programs in SE as semantic structures in NLP, and use them as the basis for broad-coverage dynamic semantic parsing. My ambitious, cross-disciplinary goal is to develop a new NL compiler based on this novel approach to NL semantics. The NL compiler will accept an NL description as input and return an executable system as output. Moreover, it will continuously improve its NL understanding capacity via online learning that will feed on verification, simulation, synthesis or user feedback. Such dynamic, ever-improving, NL compilers will have vast applications in AI, SE, robotics and cognitive computing and will fundamentally change the way humans and computers interact.

1 449 375 €

Start date: 2016-08-01, End date: 2022-07-31

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

The objective of this proposal is an investigation of the geometric structure of random spaces that arise in critical models of statistical physics. The proposal is motivated by inspiring yet non-rigorous predictions from the physics community and the models studied are some of the most popular models in contemporary probability theory such as percolation, random planar maps and random walks. One set of problems are on the topic of random planar maps and quantum gravity, a thriving field on the intersection of probability, statistical physics, combinatorics and complex analysis. Our goal is to develop a rigorous theory of these maps viewed as surfaces (rather than metric spaces) via their circle packing. The circle packing structure was recently used by the PI and Gurel-Gurevich to show that these maps are a.s. recurrent, resolving a major conjecture in this area. Among other consequences, this research will hopefully lead to progress on the most important open problem in this field: a rigorous proof of the mysterious KPZ correspondence, a conjectural formula from the physics literature allowing to compute dimensions of certain random sets in the usual square lattice from the corresponding dimension in the random geometry. Such a program will hopefully lead to the solution of the most central problems in two-dimensional statistical physics, such as finding the typical displacement of the self-avoiding walk, proving conformal invariance for percolation on the square lattice and many others. Another set of problems is investigating aspects of universality in critical percolation in various high-dimensional graphs. These graphs include lattices in dimension above 6, Cayley graphs of finitely generated non-amenable groups and also finite graphs such as the complete graph, the Hamming hypercube and expanders. It is believed that critical percolation on these graphs is universal in the sense that the resulting percolated clusters exhibit the same mean-field geometry.

1 286 150 €

Start date: 2016-01-01, End date: 2020-12-31

In a free society, there is persistent tension between utility and privacy. Citizens have the basic right to keep their personal information private. However, sometimes keeping our data private could significantly reduce our ability to use this data to benefit ourselves or society. This tension is multiplied many times over in our modern data driven society, where data is utilized using remote algorithms. State of the art research suggests that new advanced cryptographic primitives can mitigate this tension. These include computing on encrypted data via fully homomorphic encryption, fine grained access control to encrypted data via attribute based encryption, and most recently general purpose program obfuscation, which on paper can solve many of cryptography's long standing problems. However, these primitives are largely either too complicated or not sufficiently founded to be considered for real world applications. Project REACT will apply foundational theoretical study towards removing the barriers between advanced cryptographic primitives and reality. My viewpoint, supported by my prior research success, is that orders-of-magnitude improvement in efficiency and security requires foundational theoretical study, rather than focusing on optimizations or heuristics. My projection is that progress in this direction will both allow for future realistic implementation of these primitives, reducing said tension, as well as contribute to basic cryptographic study by opening new avenues for future research. To achieve this goal, I will pursue the following objectives: (i) Studying the computational complexity of underlying hardness assumptions, specifically lattice based, to better understand the level of security we can expect of proposed primitives. (ii) Simplifying and extending the LWE/trapdoor paradigm that underlies many of the new primitives, and that I find incomplete. (iii) Constructing cryptographic graded encoding schemes and obfuscators.

1 493 803 €

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

Noise sensitivity and noise stability of Boolean functions, percolation, and other models were introduced in a paper by Benjamini, Kalai, and Schramm (1999) and were extensively studied in the last two decades. We propose to extend this study to various stochastic and combinatorial models, and to explore connections with computer science, quantum information, voting methods and other areas. The first goal of our proposed project is to push the mathematical theory of noise stability and noise sensitivity forward for various models in probabilistic combinatorics and statistical physics. A main mathematical tool, going back to Kahn, Kalai, and Linial (1988), is applications of (high-dimensional) Fourier methods, and our second goal is to extend and develop these discrete Fourier methods. Our third goal is to find applications toward central old-standing problems in combinatorics, probability and the theory of computing. The fourth goal of our project is to further develop the ``argument against quantum computers'' which is based on the insight that noisy intermediate scale quantum computing is noise stable. This follows the work of Kalai and Kindler (2014) for the case of noisy non-interacting bosons. The fifth goal of our proposal is to enrich our mathematical understanding and to apply it, by studying connections of the theory with various areas of theoretical computer science, and with the theory of social choice.

1 754 500 €

Start date: 2019-06-01, End date: 2024-05-31

The starting point of this research proposal is a recent result by the PI, making progress in a half century old, notoriously open problem. In the mid 1960’s, Tukey and Cooley discovered the Fast Fourier Transform, an algorithm for performing one of the most important linear transformations in science and engineering, the (discrete) Fourier transform, in time complexity O(n log n). In spite of its importance, a super-linear lower bound has been elusive for many years, with only very limited results. Very recently the PI managed to show that, roughly speaking, a faster Fourier transform must result in information loss, in the form of numerical accuracy. The result can be seen as a type of computational uncertainty principle, whereby faster computation increases uncertainty in data. The mathematical argument is established by defining a type of matrix quasi-entropy, generalizing Shannon’s measure of information (entropy) to “quasi-probabilities” (which can be negative, more than 1, or even complex). This result, which is not believed to be tight, does not close the book on Fourier complexity. More importantly, the vision proposed by the PI here reaches far beyond Fourier computation. The computation-information tradeoff underlying the result suggests a novel view of complexity theory as a whole. We can now revisit some classic complexity theoretical problems with a fresh view. Examples of these problems include better understanding of the complexity of polynomial multiplication, integer multiplication, auto-correlation and cross-correlation computation, dimensionality reduction via the Fast Johnson-Linednstrauss Transform (FJLT; also discovered and developed by the PI), large scale linear algebra (linear regression, Principal Component Analysis - PCA, compressed sensing, matrix multiplication) as well as binary functions such as integer multiplication.

1 515 801 €

Start date: 2016-06-01, End date: 2021-05-31

One of the most significant recent developments in applied machine learning has been the resurgence of ``deep learning'', usually in the form of artificial neural networks. The empirical success of deep learning is stunning, and deep learning based systems have already led to breakthroughs in computer vision and speech recognition. In contrast, from the theoretical point of view, by and large, we do not understand why deep learning is at all possible, since most state of the art theoretical results show that deep learning is computationally hard. Bridging this gap is a great challenge since it involves proficiency in several theoretic fields (algorithms, complexity, and statistics) and at the same time requires a good understanding of real world practical problems and the ability to conduct applied research. We believe that a good theory must lead to better practical algorithms. It should also broaden the applicability of learning in general, and deep learning in particular, to new domains. Such a practically relevant theory may also lead to a fundamental paradigm shift in the way we currently analyze the complexity of algorithms. Previous works by the PI and his colleagues and students have provided novel ways to analyze the computational complexity of learning algorithms and understand the tradeoffs between data and computational time. In this proposal, in order to bridge the gap between theory and practice, I suggest a departure from worst-case analyses and the development of a more optimistic, data dependent, theory with ``grey'' components. Success will lead to a breakthrough in our understanding of learning at large with significant potential for impact on the field of machine learning and its applications.

1 342 500 €

Start date: 2016-02-01, End date: 2021-01-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