Idea | EPFL Graph Search

In common usage and in philosophy, ideas are the results of thought. Also in philosophy, ideas can also be mental representational images of some object. Many philosophers have considered ideas to be a fundamental ontological . The capacity to create and understand the meaning of ideas is considered to be an essential and defining feature of human beings. An idea arises in a reflexive, spontaneous manner, even without thinking or serious reflection, for example, when we talk about the idea of a person or a place. A new or an original idea can often lead to innovation. Etymology The word idea comes from Greek ἰδέα idea "form, pattern," from the root of ἰδεῖν idein, "to see." History The argument over the underlying nature of ideas is opened by Plato, whose exposition of his theory of forms—which recurs and accumulates over the course of his many dialogs—appropriates and adds a new sense to the Greek word for things that are "seen" (re. εἶδος) that highlights those

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also been numerous works that study combinatorial problems with submodular objective functions. This is motivated by their natural diminishing returns property which is useful in real-world applications. The thesis at hand is concerned with the study of streaming and matching problems with submodular functions.Firstly, motivated by developing robust algorithms, we propose a new adversarial injections model, in which the input is ordered randomly, but an adversary may inject misleading elements at arbitrary positions. We study the maximum matching problem and cardinality constrained monotone submodular maximization. We show that even under this seemingly powerful adversary, it is possible to break the barrier of 1/2 for both these problems in the streaming setting. Our main result is a novel streaming algorithm that computes a 0.55-approximation for cardinality constrained monotone submodular maximization.In the second part of the thesis, we study the problem of matroid intersection in the semi-streaming setting. Our main result is a (2 + e)-approximate semi-streaming algorithm for weighted matroid inter- section improving upon the previous best guarantee of 4 + e. While our algorithm is based on the local ratio technique, its analysis differs from the related problem of weighted maximum matching and uses the concept of matroid kernels. We are also able to generalize our results to work for submodular functions by adapting ideas from a recent result by Levin and Wajc (SODA'21) on submodular maximization subject to matching constraints.Finally, we study the submodular Santa Claus problem in the restricted assignment case. The submodular Santa Claus problem was introduced in a seminal work by Goemans, Harvey, Iwata, and Mirrokni (SODA'09) as an application of their structural result. In the mentioned problem n unsplittable resources have to be assigned to m players, each with a monotone submodular utility function fi. The goal is to maximize mini fi(Si) where S1, . . . , Sm is a partition of the resources. The result by Goemans et al. implies a polynomial time O(n1/2+e)-approximation algorithm. In the restricted assignment case, each player is given a set of desired resources Gi and the individual valuation functions are defined as fi(S)= f(SnGi). OurmainresultisaO(loglog(n))-approximation algorithm for the problem. Our proof is inspired by the approach of Bansal and Srividenko (STOC'06) to the Santa Claus problem. Com- pared to the more basic linear setting, the introduction of submodularity requires a much more involved analysis and several new ideas.

EPFL2022

Permanence and Persistence Conception, Construction and Conversion of Modern Cinema Theatres [1910-1939]

Joana de Almeida Gouveia Oliveira Alves

This work is based on the assumption that it is possible to achieve sustainable development by preserving the twentieth century heritage. Modern European cinemas were especially vulnerable to the passing of time: in a few decades buildings with tremendous socio-cultural importance became obsolete structures in cities. This research into cinema theatre design in Western Europe during the period 1910-1939 is based on articles on cinema design published in leading architectural periodicals, using the information they contain to trace the history of the cinemas which had the greatest influence on the development of this building type in Europe. Chapters II and III focus on the theoretical and technical approaches to cinema building and aim to synthesise the ideas discussed at the time. They represent a study of the emergence of cinema as an autonomous architectural programme and how this building type was developed. The final chapters concern the abandonment of cinema theatres, which has resulted in a number of public demonstrations calling for the function of these buildings as cultural venues to be maintained and for their physical conservation. Unlike the usual nostalgic approach, an objective study of the conversion processes for these buildings enables conversion patterns to be identified. A significant number of the buildings in the study were demolished or gutted as a result of speculative financial ventures, while others were reused. The ultimate purpose of this thesis is to understand the aspects on which the life cycle of a cinema theatre and its permanence in the urban fabric depend, even if it serves a different function.

EPFL2015

Three Essays on Methodologies for Dynamic Modeling of Emerging Socio-technical Systems

Mohammad Amin Dehdarian

Socio-technical energy transitions are long-term and major transformations in incumbent energy infrastructures. They include fundamental changes in technologies as well as institutions and social patterns. Transition studies are primarily focused on frameworks for analyzing the entire transition process by investigating the historical cases of transitions. A multi-phase approach to transition posits this process begins with a pre-development phase characterized by technological and institutional lock-ins, and resistance from incumbent actors. This period is critical for a forward-looking approach to transitions, since early developments shape path-dependent and irreversible processes leading to the emergence of new transition pathways. However, our understanding about the mechanisms and dynamics of this phase is still very limited. This is mainly due to lack of data, weak conceptualization and the necessity of developing new methods proper to deal with these limitations. This dissertation develops methodologies for investigating some complex questions arising in the pre-development phase, by focusing on the case of smart grid development. The first essay uses insights from modeling interventions in complex systems and builds a System Dynamics model to investigate the cost allocation problem of smart metering roll-out. The second essay takes ideas from Technological Innovation System approach and develops a method to analyze the emergence of spatial diversity in smart grid development by combining Social Network Analysis and Agent-Based Modeling. The third essay builds on ideas from network theory and evolutionary modeling to develop a method for identifying the main path of knowledge development and analyzing knowledge trajectories in smart grid initiatives.

EPFL2017

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

EPFL2022