Publication
Rank-Deficient Quadratic-Form Maximization Over M-Phase Alphabet: Polynomial-Complexity Solvability And Algorithmic Developments
Related publications (92)
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 Inc2024Certification 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 ...
2023Extractable 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 ...
Springer2023Discrete 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 ...
2022A PCP Theorem for Interactive Proofs and Applications
The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...
SPRINGER INTERNATIONAL PUBLISHING AG2022Lower Bounds for Unambiguous Automata via Communication Complexity
Mika Tapani Göös, Weiqiang Yuan
We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022Automating cutting planes is NP-hard
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, ...
ACM2021Bayesian Decision Making in Groups is Hard
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 ...
INFORMS2021Beim Wort genommen
Review of the monograph "Projekt ohne Form" by Holger Schurk on OMA’s competition entires from 1989, discussing Koolhaas’ approach to form in architecture. ...
2021New Results in Integer and Lattice Programming
An integer program (IP) is a problem of the form , where , , , and is a separable convex objective function.
The problem o ...
EPFL2020