Publications related to Rank-Deficient Quadratic-Form Maximization Over M-Phase Alphabet: Polynomial-Complexity Solvability And Algorithmic Developments

Related publications (29)

Succinct ordering and aggregation constraints in algebraic array theories

We discuss two extensions to a recently introduced theory of arrays, which are based on considerations coming from the model theory of power structures. First, we discuss how the ordering relation on the index set can be expressed succinctly by referring t ...

Elsevier Science Inc2024

Biobased surfactant

Jeremy Luterbacher, Stefania Bertella, Songlan Sun, Anastasiia Komarova

The present invention relates to a compound of the general formula (I), (II) and (III), more specifically of formula (Ia), (Ib), (Ic)wherein R11 and R12 or R21 and R22 or R31 and R32 are both hydrogen or form together with CHR50 a cyclic moiety or one of R ...

2024

Orthologic with Axioms

Viktor Kuncak, Simon Guilloud

We study the proof theory and algorithms for orthologic, a logical system based on ortholattices, which have shown practical relevance in simplification and normalization of verification conditions. Ortholattices weaken Boolean algebras while having polyno ...

Association for Computing Machinery2024

Unlabeled Principal Component Analysis and Matrix Completion

Yunzhen Yao

We introduce robust principal component analysis from a data matrix in which the entries of its columns have been corrupted by permutations, termed Unlabeled Principal Component Analysis (UPCA). Using algebraic geometry, we establish that UPCA is a well-de ...

Microtome Publishing2024

Anomalous dissipation and other non-smooth phenomena in fluids

Massimo Sorella

The thesis is dedicated to the study of two main partial differential equations (PDEs) in fluid dynamics: the Navier-Stokes equations, which describe the motion of incompressible fluids, and the transport equation with divergence-free velocity fields, whic ...

EPFL2024

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Maryam Kamgarpour, Tony Alan Wood

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...

2023

Results on Sparse Integer Programming and Geometric Independent Sets

Jana Tabea Cslovjecsek

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

EPFL2023

Extractable Witness Encryption for the Homogeneous Linear Equations Problem

Serge Vaudenay, Bénédikt Minh Dang Tran

Witness encryption is a cryptographic primitive which encrypts a message under an instance of an NP language and decrypts the ciphertext using a witness associated with that instance. In the current state of the art, most of the witness encryption construc ...

Springer2023

The multivariate Serre conjecture ring

Luc Guyot

It is well-known that for any integral domain R, the Serre conjecture ring R(X), i.e., the localization of the univariate polynomial ring R[X] at monic polynomials, is a Bezout domain of Krull dimension

Academic Press Inc Elsevier Science2023

Linear Complexity Self-Attention With 3rd Order Polynomials

Grigorios Chrysos

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

Worst-Case Delay Analysis of Time-Sensitive Networks with Network Calculus

Seyed Mohammadhossein Tabatabaee

Time-sensitive networks, as in the context of IEEE Time-Sensitive Networking (TSN) and IETF Deterministic Networking (DetNet), offer deterministic services with guaranteed bounded latency in order to support safety-critical applications. In this thesis, we ...

EPFL2023

Biobased surfactants

Jeremy Luterbacher, Stefania Bertella, Songlan Sun, Anastasiia Komarova

Compound of the general formula (Ia), (Ib) and (Ic) R50 and R60 are different form each other and are selected from the group consisting of -R70, -ZR70, -Z-OH, -Z-NH2, -Z-SH, -Z-OC(O)R70, -OC(O)R70, - COOH and its corresponding salts, -C(O)NH2, -C(O)NH-R70 ...

2023

Better Trees for Santa Claus

Etienne Michel François Bamas, Lars Rohwedder

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

Assoc Computing Machinery2023

Structural impact of the start-up sequence on Pelton turbines lifetime: Analytical prediction and polynomial optimization

Mario Paolone, Elena Vagnoni, Aldo Leonardo Alerci

Hydropower plants play a crucial role in the power system facing ambitious renewable energy targets. Due to their inherent controllability, they are well suited to provide flexibility to the grid. However, an increased flexibility provision leads to a prol ...

Pergamon-Elsevier Science Ltd2023

Design Space Exploration for Partitioning Dataflow Program on CPU-GPU Heterogeneous System

Marco Mattavelli, Simone Casale Brunet, Aurélien François Gilbert Bloch

Dataflow programming is a methodology that enables the development of high-level, parametric programs that are independent of the underlying platform. This approach is particularly useful for heterogeneous platforms, as it eliminates the need to rewrite ap ...

SPRINGER2023

Discrete Optimal Transport with Independent Marginals is #P-Hard

Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

SIAM Publications2023

Fast deterministic and randomized algorithms for low-rank approximation, matrix functions, and trace estimation

Alice Cortinovis

In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices. In the first part, we consider algorithms for building ...

EPFL2022

Minimum Cost Intervention Design for Causal Effect Identification

Negar Kiyavash, Seyed Jalal Etesami, Sina Akbari

Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the ...

PMLR2022

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

SPRINGER HEIDELBERG2022