@article{50271, author = {{Gharibian, Sevag and Le Gall, François}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, keywords = {{General Mathematics, General Computer Science}}, number = {{4}}, pages = {{1009--1038}}, publisher = {{Society for Industrial & Applied Mathematics (SIAM)}}, title = {{{Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture}}}, doi = {{10.1137/22m1513721}}, volume = {{52}}, year = {{2023}}, } @article{8175, abstract = {{Approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem (where QMA stands for Quantum Merlin Arthur) and initiate its study. We present two main results. The first shows that a nontrivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one) gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the “exhaustive sampling method” by Arora, Karger, and Karpinski [J. Comput. System Sci., 58 (1999), p. 193] to the quantum setting and might be of independent interest.}}, author = {{Gharibian, Sevag and Kempe, Julia}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, number = {{4}}, pages = {{1028--1050}}, publisher = {{Society for Industrial & Applied Mathematics (SIAM)}}, title = {{{Approximation Algorithms for QMA-Complete Problems}}}, doi = {{10.1137/110842272}}, volume = {{41}}, year = {{2012}}, } @article{23739, abstract = {{This paper deals with the design of efficiently computable incentive-compatible mechanisms for combinatorial optimization problems with single-minded agents each possibly having multiple private parameters. We focus on approximation algorithms for NP-hard mechanism design problems. These algorithms need to satisfy certain monotonicity properties to ensure truthfulness. Since most of the known approximation techniques do not fulfill these properties, we study alternative techniques. Our first contribution is a quite general method to transform a pseudopolynomial algorithm into a monotone fully polynomial time approximation scheme (FPTAS). This can be applied to various problems like, e.g., knapsack, constrained shortest path, or job scheduling with deadlines. For example, the monotone FPTAS for the knapsack problem gives a very efficient, truthful mechanism for single-minded multiunit auctions. The best previous result for such auctions was a 2-appro-xi-ma-tion. In addition, we present a monotone PTAS for the generalized assignment problem with any constant number of private parameters per agent. The most efficient way to solve packing integer programs (PIPs) is linear programming–based randomized rounding, which also is in general not monotone. We show that primal-dual greedy algorithms achieve almost the same approximation ratios for PIPs as randomized rounding. The advantage is that these algorithms are inherently monotone. This way, we can significantly improve the approximation ratios of truthful mechanisms for various fundamental mechanism design problems like single-minded combinatorial auctions (CAs), unsplittable flow routing, and multicast routing. Our primal-dual approximation algorithms can also be used for the winner determination in CAs with general bidders specifying their bids through an oracle. }}, author = {{Briest, Patrick and Krysta, Piotr and Vöcking, Berthold}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{1587--1622}}, title = {{{Approximation Techniques for Utilitarian Mechanism Design}}}, doi = {{10.1137/090772988}}, year = {{2011}}, } @article{23740, abstract = {{We investigate nonparametric multiproduct pricing problems, in which we want to find revenue maximizing prices for products $\mathcal{P}$ based on a set of customer samples $\mathcal{C}$. We mostly focus on the unit-demand case, in which products constitute strict substitutes and each customer aims to purchase a single product. In this setting a customer sample consists of a number of nonzero values for different products and possibly an additional product ranking. Once prices are fixed, each customer chooses to buy one of the products she can afford based on some predefined selection rule. We distinguish between the min-buying, max-buying, and rank-buying models. Some of our results also extend to single-minded pricing, in which case products are strict complements and every customer seeks to buy a single set of products, which she purchases if the sum of prices is below her valuation for that set. For the min-buying model we show that the revenue maximization problem is not approximable within factor $\mathcal{O}(\log^{\varepsilon}|\mathcal{C}|)$ for some constant $\varepsilon>0$, unless $\mathrm{NP}\subseteq\mathrm{DTIME}(n^{\mathcal{O}(\log\log n)})$, thereby almost closing the gap between the known algorithmic results and previous lower bounds. We also prove inapproximability within $\mathcal{O}(\ell^{\varepsilon})$, $\ell$ being an upper bound on the number of nonzero values per customer, and $\mathcal{O}(|\mathcal{P}|^{\varepsilon})$ under slightly stronger assumptions and provide matching upper bounds. Surprisingly, these hardness results hold even if a price ladder constraint, i.e., a predefined order on the prices of all products, is given. Without the price ladder constraint we obtain similar hardness results for the special case of uniform valuations, i.e., the case that every customer has identical values for all the products she is interested in, assuming specific hardness of the balanced bipartite independent set problem in constant degree graphs or hardness of refuting random 3CNF formulas. Introducing a slightly more general problem definition in which customers are given as an explicit probability distribution, we obtain inapproximability within $\mathcal{O}(|\mathcal{P}|^{\varepsilon})$ assuming $\mathrm{NP}\nsubseteq\bigcap_{\delta>0}\mathrm{BPTIME}(2^{\mathcal{O}(n^{\delta})})$. These results apply to single-minded pricing as well. For the max-buying model a polynomial-time approximation scheme exists if a price ladder is given. We give a matching lower bound by proving strong NP-hardness. Assuming limited product supply, we analyze a generic local search algorithm and prove that it is 2-approximate. Finally, we discuss implications for the rank-buying model. }}, author = {{Briest, Patrick and Krysta, Piotr}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{1554--1586}}, title = {{{Buying Cheap Is Expensive: Approximability of Combinatorial Pricing Problems}}}, doi = {{10.1137/090752353}}, year = {{2011}}, } @article{42803, abstract = {{We provide algorithms to count and enumerate representatives of the (right) ideal classes of an Eichler order in a quaternion algebra defined over a number field. We analyze the run time of these algorithms and consider several related problems, including the computation of two-sided ideal classes, isomorphism classes of orders, connecting ideals for orders, and ideal principalization. We conclude by giving the complete list of definite Eichler orders with class number at most 2.}}, author = {{Kirschmer, Markus and Voight, John}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, keywords = {{General Mathematics, General Computer Science}}, number = {{5}}, pages = {{1714--1747}}, publisher = {{Society for Industrial & Applied Mathematics (SIAM)}}, title = {{{Algorithmic Enumeration of Ideal Classes for Quaternion Orders}}}, doi = {{10.1137/080734467}}, volume = {{39}}, year = {{2010}}, } @article{18763, abstract = {{Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs . We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension , then the property has an efficient tester. We apply our framework to a variety of problems. We present efficient property testing algorithms for geometric clustering problems, for the reversal distance problem, and for graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way, and the obtained complexity bounds either match or improve the previously known bounds. Furthermore, even if the asymptotic complexity of the testers is not improved, the obtained proofs are significantly simpler than the previous ones. We believe that our framework will help to understand the structure of efficiently testable properties.}}, author = {{Czumaj, Artur and Sohler, Christian}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, number = {{3}}, pages = {{580--615}}, title = {{{Abstract Combinatorial Programs and Efficient Property Testers}}}, doi = {{10.1137/s009753970444199x}}, volume = {{34}}, year = {{2005}}, } @article{18855, abstract = {{We consider the problem of computing the weight of a Euclidean minimum spanning tree for a set of n points in $\mathbb R^d$. We focus on the setting where the input point set is supported by certain basic (and commonly used) geometric data structures that can provide efficient access to the input in a structured way. We present an algorithm that estimates with high probability the weight of a Euclidean minimum spanning tree of a set of points to within $1 + \eps$ using only $\widetilde{\O}(\sqrt{n} \, \text{poly} (1/\eps))$ queries for constant d. The algorithm assumes that the input is supported by a minimal bounding cube enclosing it, by orthogonal range queries, and by cone approximate nearest neighbor queries. Read More: https://epubs.siam.org/doi/10.1137/S0097539703435297 }}, author = {{Czumaj, Artur and Ergün, Funda and Fortnow, Lance and Magen, Avner and Newman, Ilan and Rubinfeld, Ronitt and Sohler, Christian}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, number = {{1}}, pages = {{91--109}}, title = {{{Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time}}}, doi = {{10.1137/s0097539703435297}}, volume = {{35}}, year = {{2005}}, } @inproceedings{19952, abstract = {{Graph minors theory, developed by Robertson & Seymour, provides a list of powerful theoretical results and tools. However, the wide spread opinion in Graph Algorithms community about this theory is that it is mainly of theoretical importance. The main purpose of this paper is to show how very deep min-max and duality theorems from Graph Minors can be used to obtain essential speed-up to many known algorithms on different domination problems.}}, author = {{Fomin, Fedor V. and Thilikos, Dimitrios M.}}, booktitle = {{Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003)}}, issn = {{0097-5397}}, title = {{{Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up}}}, doi = {{10.1137/s0097539702419649}}, year = {{2003}}, } @article{17010, author = {{Czumaj, Artur and Meyer auf der Heide, Friedhelm and Stemann, Volker}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{1703--1739}}, title = {{{Contention Resolution in Hashing Based Shared Memory Simulations}}}, doi = {{10.1137/s009753979529564x}}, year = {{2000}}, } @article{16701, author = {{Gil, Joseph and Meyer auf der Heide, Friedhelm and Wigderson, Avi}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{936--955}}, title = {{{The Tree Model for Hashing: Lower and Upper Bounds}}}, doi = {{10.1137/s0097539793255722}}, year = {{1996}}, } @article{16728, author = {{Dietzfelbinger, Martin and Karlin, Anna and Mehlhorn, Kurt and Meyer auf der Heide, Friedhelm and Rohnert, Hans and Tarjan, Robert E.}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{738--761}}, title = {{{Dynamic Perfect Hashing: Upper and Lower Bounds}}}, doi = {{10.1137/s0097539791194094}}, year = {{1994}}, } @article{16772, author = {{Borodin, A. and Fich, F. and Meyer auf der Heide, Friedhelm and Upfal, E. and Wigderson, A.}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{97--99}}, title = {{{A Time-Space Tradeoff for Element Distinctness}}}, doi = {{10.1137/0216007}}, year = {{1987}}, } @article{16773, author = {{Meyer auf der Heide, Friedhelm and Wigderson, Avi}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{100--107}}, title = {{{The Complexity of Parallel Sorting}}}, doi = {{10.1137/0216008}}, year = {{1987}}, } @article{16771, author = {{Meyer auf der Heide, Friedhelm}}, issn = {{0097-5397}}, journal = {{SIAM Journal on Computing}}, pages = {{106--119}}, title = {{{Efficient Simulations among Several Models of Parallel Computers}}}, doi = {{10.1137/0215008}}, year = {{1986}}, }