~~NOCACHE~~ /* DO NOT EDIT THIS FILE */ /* THIS FILE WAS GENERATED */ /* EDIT THE FILE "indexheader" INSTEAD */ /* OR ACCESS THE DATABASE */ {{page>.:indexheader}} \\ ==== Next talks ==== [[en:seminaires:algocomp:index|Algorithms and complexity]]\\ Tuesday April 30, 2024, 11AM, Salle 3052\\ **André Chailloux** (INRIA Paris) //The Quantum Decoding Problem// \\ One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution (SIS) problem to the Learning with Errors (LWE) problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry [CLZ22] that this reduction can be made more powerful by replacing the LWE problem with a quantum equivalent, where the errors are given in quantum superposition. In parallel, Regev’s reduction has recently been adapted in the context of code-based cryptography by Debris, Remaud and Tillich [DRT23], who showed a reduction between the Short Codeword Problem and the Decoding Problem (the DRT reduction). This motivates the study of the Quantum Decoding Problem (QDP), which is the Decoding Problem but with errors in quantum superposition and see how it behaves in the DRT reduction. The purpose of this paper is to introduce and to lay a firm foundation for QDP. We first show QDP is likely to be easier than classical decoding, by proving that it can be solved in quantum polynomial time in a large regime of noise whereas no non-exponential quantum algorithm is known for the classical decoding problem. Then, we show that QDP can even be solved (albeit not necessarily efficiently) beyond the information theoretic Shannon limit for classical decoding. We give precisely the largest noise level where we can solve QDP giving the information theoretic limit for this new problem. Finally, we study how QDP can be used in the DRT reduction. First, we show that our algorithms can be properly used in the DRT reduction showing that our quantum algorithms for QDP beyond Shannon capacity can be used to find minimal weight codewords in a random code. On the negative side, we show that the DRT reduction cannot be, in all generality, a reduction between finding small codewords and QDP by exhibiting quantum algorithms for QDP where this reduction entirely fails. Our proof techniques include the use of specific quantum measurements, such as q-ary unambiguous state discrimination and pretty good measurements as well as strong concentration bounds on weight distribution of random shifted dual codes, which we relate using quantum Fourier analysis. [[en:seminaires:algocomp:index|Algorithms and complexity]]\\ Tuesday May 21, 2024, 11AM, Salle 3052\\ **Galina Pass** (QuSoft, University of Amsterdam) //Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer// \\ [[en:seminaires:algocomp:index|Algorithms and complexity]]\\ Tuesday May 28, 2024, 11AM, Salle 3052\\ **Nikolas Melissaris** (Aarhus University) //To be announced.// \\ [[en:seminaires:algocomp:index|Algorithms and complexity]]\\ Tuesday June 11, 2024, 11AM, Salle 3052\\ **Divyarthi Mohan** (Tel-Aviv University) //Optimal Stopping with Interdependent Values// \\ Consider the problem of selling a single item to one of n buyers arriving sequentially, whereupon the arrival of each buyer we need to decide whether to accept this value and stop the process (before seeing the values of the future bidders), or irrevocably and irreversibly reject this bidder and continue on to the next. The objective is to maximize the accepted value, which poses a fundamental question: how effectively can an online algorithm perform compared to the offline optimal solution? Further, adding to the challenge in many scenarios a bidder's value for the item may depend on private information of other bidders. For example, in an art auction, a buyer's value for the item may be influenced by how other buyer's so far have liked it, and in fact, may even depend on how the future buyers will value the item as that would affect its resale value. We study online selection problems in both the prophet and secretary settings, when arriving agents have interdependent values. In the interdependent values model, introduced in the seminal work of Milgrom and Weber [1982], each agent has a private signal and the value of an agent is a function of the signals held by all agents. Results in online selection crucially rely on some degree of independence of values, which is conceptually at odds with the interdependent values model. For prophet and secretary models under the standard independent values assumption, prior works provide constant factor approximations to the welfare. On the other hand, when agents have interdependent values, prior works in Economics and Computer Science provide truthful mechanisms that obtain optimal and approximately optimal welfare under certain assumptions on the valuation functions. We bring together these two important lines of work and provide the first constant factor approximations for prophet and secretary problems with interdependent values. We consider both the algorithmic setting, where agents are non-strategic (but have interdependent values), and the mechanism design setting with strategic agents. All our results are constructive and use simple stopping rules. Joint work with Simon Mauras and Rebecca Reiffenhäuser. [[en:seminaires:algocomp:index|Algorithms and complexity]]\\ Tuesday June 18, 2024, 11AM, Salle 3052\\ **Sebastian Zur** (QuSoft, University of Amsterdam) //Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems// \\ \\ ==== Previous talks ==== \\ === Year 2024 === {{page>.:algocomp2024}} \\ === Year 2023 === {{page>.:algocomp2023}} \\ === Year 2022 === {{page>.:algocomp2022}} \\ === Year 2021 === {{page>.:algocomp2021}} \\ === Year 2020 === {{page>.:algocomp2020}} \\ === Year 2019 === {{page>.:algocomp2019}} \\ === Year 2018 === {{page>.:algocomp2018}} \\ === Year 2017 === {{page>.:algocomp2017}} \\ === Year 2016 === {{page>.:algocomp2016}}