Publications related to P versus NP problem

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

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

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

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

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

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

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

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

Kim-Manuel Klein, Klaus Jansen, 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

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 ...

2023

Particle Size Effects in Ru/CNF Catalysts during Supercritical Water Gasification of Glycerol

Oliver Kröcher, Frédéric Vogel, David Baudouin, Ayush Agarwal

Ru/CNF catalysts of different Ru nanoparticle (NP) sizes (0.9-2.7 nm) were assessed for their performance in continuous supercritical water gasification (SCWG) of glycerol. A structure sensitivity of Ru was demonstrated, with high initial turnover frequenc ...

2022

Minimum Cost Intervention Design for Causal Effect Identification

Negar Kiyavash, Sina Akbari, Seyed Jalal Etesami

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

On Succinct Non-interactive Arguments in Relativized Worlds

Alessandro Chiesa

Succinct non-interactive arguments of knowledge (SNARKs) are cryptographic proofs with strong efficiency properties. Applications of SNARKs often involve proving computations that include the SNARK verifier, a technique called recursive composition. Unfort ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

NP Satisfiability for Arrays as Powers

Viktor Kuncak, Rodrigo Raya

We show that the satisfiability problem for the quantifier-free theory of product structures with the equicardinality relation is inNP. As an application, we extend the combinatory array logic fragmentto handle cardinality constraints. The resulting fragme ...

Springer, Cham2022

Automating cutting planes is NP-hard

Mika Tapani Göös

We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula F, It is -hard to find a CP refutation of F in time polynomial in the length of the shortest such refutation; and unless Gap-Hitting-Set admits a nontrivial algorithm, ...

ACM2021

Knapsack and Subset Sum with Small Items

Adam Teodor Polak, Lars Rohwedder

Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Uniform parsing for hyperedge replacement grammars

Petter Harald Ericson

It is well known that hyperedge-replacement grammars can generate NP-complete graph languages even under seemingly harsh restrictions. This means that the parsing problem is difficult even in the non-uniform setting, in which the grammar is considered to b ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2021

Bayesian Decision Making in Groups is Hard

Jan Hazla

We study the computations that Bayesian agents undertake when exchanging opinions over a network. The agents act repeatedly on their private information and take myopic actions that maximize their expected utility according to a fully rational posterior be ...

INFORMS2021

Adaptation in Stochastic Algorithms: From Nonsmooth Optimization to Min-Max Problems and Beyond

Ahmet Alacaoglu

Stochastic gradient descent (SGD) and randomized coordinate descent (RCD) are two of the workhorses for training modern automated decision systems. Intriguingly, convergence properties of these methods are not well-established as we move away from the spec ...

EPFL2021

Robust Learning-Augmented Caching: An Experimental Study

Adam Teodor Polak

Effective caching is crucial for performance of modern-day computing systems. A key optimization problem arising in caching – which item to evict to make room for a new item – cannot be optimally solved without knowing the future. There are many classical ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2021

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Lars Rohwedder

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. ...

ASSOC COMPUTING MACHINERY2021