Concept

Descriptive complexity theory

Related publications (49)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Operando X-ray diffraction during laser 3D printing: from machine design to experiments and computer simulations

Samy Hocine

The importance of additive manufacturing, also known as 3D printing, has grown exponentially in the recent years thanks to its high flexibility to manufacture intricate parts. This process can be divided into many different sub-categories, depending on the ...

EPFL2020

On the relation between transversal and longitudinal scaling in cities

João Vitor Meirelles de Miranda

Does the scaling relationship between population sizes of cities with urban metrics like economic output and infrastructure (transversal scaling) mirror the evolution of individual cities in time (longitudinal scaling)? The answer to this question has impo ...

2020

A Complexity Analysis Approach for Model-based System Engineering

Dimitrios Kyritsis, Jinzhi Lu, Xiaochen Zheng, Jinwei Chen

With the increasing complexity of the highly engineered products, Model-based Systems Engineering (MBSE) is proposed to support the complexity management of the product development. As the basic of complexity management, complexity analysis is used to meas ...

IEEE2020

, , , ,

We propose a practical inexact augmented Lagrangian method (iALM) for nonconvex problems with nonlinear constraints. We characterize the total computational complexity of our method subject to a verifiable geometric condition, which is closely related to t ...

2019

A novel manifold learning approach is presented to incorporate computationally efficient obstacle avoidance constraints in optimal control algorithms. The method presented provides a significant computational benefit by reducing the number of constraints r ...

2019

Adventures in Monotone Complexity and TFNP

Mika Tapani Göös, Dmitrii Sokolov

Separations: We introduce a monotone variant of Xor-Sat and show it has exponential monotone circuit complexity. Since Xor-Sat is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone ...

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany2018

MATHICSE Technical Report : Analysis of stochastic gradient methods for PDE-constrained optimal control problems with uncertain parameters

Fabio Nobile, Sebastian Krumscheid, Matthieu Claude Martin

We consider the numerical approximation of a risk-averse optimal control problem for an elliptic partial differential equation (PDE) with random coefficients. Specifically, the control function is a deterministic, dis- tributed forcing term that minimizes ...

MATHICSE2018

Ramsey-Turan numbers for semi-algebraic graphs

János Pach

A semi-algebraic graph G = (V, E) is a graph where the vertices are points in R-d, and the edge set E is defined by a semi-algebraic relation of constant complexity on V. In this note, we establish the following Ramsey-Turan theorem: for every integer p >= ...

ELECTRONIC JOURNAL OF COMBINATORICS2018

Business Models and Complexity

Christopher Tucci, Gianluigi Viscusi, Lorenzo Massa

Purpose: To offer a -necessarily non-exhaustive- analysis of the meaning and significance of the notion of a complex system for research on the Business Model (BM). Design/Methodology/Approach: Conceptual paper Findings: Drawing from early research in comp ...

2018

Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward

Michael Christoph Gastpar, Saeid Sahraei

A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order O(nψlog(nψ)) , where ψ=sqrt(P ||h||^2+1) ...

Institute of Electrical and Electronics Engineers2017