Publications associées à Complexité descriptive

Efficient Continual Finite-Sum Minimization

Volkan Cevher, Efstratios Panteleimon Skoulakis, Leello Tadesse Dadi

Given a sequence of functions

f_1,\ldots,f_n

with

f_i:\mathcal{D}\mapsto \mathbb{R}

, finite-sum minimization seeks a point

{x}^\star \in \mathcal{D}

minimizing

\sum_{j=1}^nf_j(x)/n

. In this work, we propose a key twist into the finite-sum minimizat ...

2024

A Streamline Upwind Petrov-Galerkin Reduced Order Method for Advection-Dominated Partial Differential Equations Under Optimal Control

Fabio Zoccolan, Gianluigi Rozza

In this paper we will consider distributed Linear-Quadratic Optimal Control Problems dealing with Advection-Diffusion PDEs for high values of the Peclet number. In this situation, computational instabilities occur, both for steady and unsteady cases. A Str ...

Walter De Gruyter Gmbh2024

Linear Complexity Self-Attention With 3rd Order Polynomials

Grigorios Chrysos, Filippos Kokkinos

Self-attention mechanisms and non-local blocks have become crucial building blocks for state-of-the-art neural architectures thanks to their unparalleled ability in capturing long-range dependencies in the input. However their cost is quadratic with the nu ...

Ieee Computer Soc2023

On Semi-Algebraic Proofs and Algorithms

Mika Tapani Göös

We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-d Sherali-Adams refutation of an unsatisfiable CNF formula C if and only if there is an ε > 0 and a degree-d conical junta J such that viol_C(x) - ε = J, where ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

Proofs, Circuits, and Communication

Mika Tapani Göös

We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and query/communication complexity. We advocate for the theory of total search prob ...

2022

A Toolbox for Barriers on Interactive Oracle Proofs

Alessandro Chiesa

Interactive oracle proofs (IOPs) are a proof system model that combines features of interactive proofs (IPs) and probabilistically checkable proofs (PCPs). IOPs have prominent applications in complexity theory and cryptography, most notably to constructing ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Time Dependent Image Generation of Plants from Incomplete Sequences with CNN-Transformer

Marc Conrad Russwurm

Data imputation of incomplete image sequences is an essential prerequisite for analyzing and monitoring all development stages of plants in precision agriculture. For this purpose, we propose a conditional Wasserstein generative adversarial network TransGr ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Adversarial training with informed data selection

Pascal Frossard, Javier Alejandro Maroto Morales, Marcele Oliveira Kuhfuss de Mendonça

With the increasing amount of available data and advances in computing capabilities, deep neural networks (DNNs) have been successfully employed to solve challenging tasks in various areas, including healthcare, climate, and finance. Nevertheless, state-of ...

IEEE2022

Relaxed Locally Correctable Codes With Nearly-Linear Block Length And Constant Query Complexity

Alessandro Chiesa

Locally correctable codes (LCCs) are error correcting codes C : \Sigmak \rightarrow \Sigman which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. For systematic codes, this notion is stro ...

SIAM PUBLICATIONS2022

Complexity 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 an optimal control problem for an elliptic Partial Differential Equation (PDE) with random coefficients. Specifically, the control function is a deterministic, distributed forcing term that minimizes the expected ...

2021

Towards Tight Bounds for Spectral Sparsification of Hypergraphs

Mikhail Kapralov, Jakab Tardos

Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applicati ...

ASSOC COMPUTING MACHINERY2021

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

An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints

Volkan Cevher, Mehmet Fatih Sahin, Ahmet Alacaoglu, Armin Eftekhari, Fabian Ricardo Latorre Gomez

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

Manifold Learning and Optimal Control for Obstacle Avoidance in Autonomous Driving

Colin Neil Jones, Sanket Sanjay Diwale

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

Optimal Stochastic Sensor Error Modeling based on Actual Impact on Quality of GNSS-INS Integrated Navigation

Jan Skaloud, Stéphane Guerrier, Mehran Khaghani

Proper modeling of stochastic errors in inertial sensors plays a crucial role in the achievable quality of GNSS-INS integration especially with low-cost inertial sensors. Generalized Method of Wavelet Moments (GMWM) can model the underlying process for suc ...

2019

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