---
_id: '50271'
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: François
full_name: Le Gall, François
last_name: Le Gall
citation:
ama: 'Gharibian S, Le Gall F. Dequantizing the Quantum Singular Value Transformation:
Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.
SIAM Journal on Computing. 2023;52(4):1009-1038. doi:10.1137/22m1513721'
apa: 'Gharibian, S., & Le Gall, F. (2023). Dequantizing the Quantum Singular
Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum
PCP Conjecture. SIAM Journal on Computing, 52(4), 1009–1038. https://doi.org/10.1137/22m1513721'
bibtex: '@article{Gharibian_Le Gall_2023, title={Dequantizing the Quantum Singular
Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum
PCP Conjecture}, volume={52}, DOI={10.1137/22m1513721},
number={4}, journal={SIAM Journal on Computing}, publisher={Society for Industrial
& Applied Mathematics (SIAM)}, author={Gharibian, Sevag and Le Gall, François},
year={2023}, pages={1009–1038} }'
chicago: 'Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular
Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum
PCP Conjecture.” SIAM Journal on Computing 52, no. 4 (2023): 1009–38. https://doi.org/10.1137/22m1513721.'
ieee: 'S. Gharibian and F. Le Gall, “Dequantizing the Quantum Singular Value Transformation:
Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture,”
SIAM Journal on Computing, vol. 52, no. 4, pp. 1009–1038, 2023, doi: 10.1137/22m1513721.'
mla: 'Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular
Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum
PCP Conjecture.” SIAM Journal on Computing, vol. 52, no. 4, Society for
Industrial & Applied Mathematics (SIAM), 2023, pp. 1009–38, doi:10.1137/22m1513721.'
short: S. Gharibian, F. Le Gall, SIAM Journal on Computing 52 (2023) 1009–1038.
date_created: 2024-01-07T18:19:42Z
date_updated: 2026-05-15T08:42:17Z
department:
- _id: '7'
- _id: '623'
doi: 10.1137/22m1513721
intvolume: ' 52'
issue: '4'
keyword:
- General Mathematics
- General Computer Science
language:
- iso: eng
page: 1009-1038
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
publisher: Society for Industrial & Applied Mathematics (SIAM)
status: public
title: 'Dequantizing the Quantum Singular Value Transformation: Hardness and Applications
to Quantum Chemistry and the Quantum PCP Conjecture'
type: journal_article
user_id: '71541'
volume: 52
year: '2023'
...
---
_id: '8175'
abstract:
- lang: eng
text: 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.
article_type: original
author:
- first_name: Sevag
full_name: Gharibian, Sevag
id: '71541'
last_name: Gharibian
orcid: 0000-0002-9992-3379
- first_name: Julia
full_name: Kempe, Julia
last_name: Kempe
citation:
ama: Gharibian S, Kempe J. Approximation Algorithms for QMA-Complete Problems. SIAM
Journal on Computing. 2012;41(4):1028-1050. doi:10.1137/110842272
apa: Gharibian, S., & Kempe, J. (2012). Approximation Algorithms for QMA-Complete
Problems. SIAM Journal on Computing, 41(4), 1028–1050. https://doi.org/10.1137/110842272
bibtex: '@article{Gharibian_Kempe_2012, title={Approximation Algorithms for QMA-Complete
Problems}, volume={41}, DOI={10.1137/110842272},
number={4}, journal={SIAM Journal on Computing}, publisher={Society for Industrial
& Applied Mathematics (SIAM)}, author={Gharibian, Sevag and Kempe, Julia},
year={2012}, pages={1028–1050} }'
chicago: 'Gharibian, Sevag, and Julia Kempe. “Approximation Algorithms for QMA-Complete
Problems.” SIAM Journal on Computing 41, no. 4 (2012): 1028–50. https://doi.org/10.1137/110842272.'
ieee: 'S. Gharibian and J. Kempe, “Approximation Algorithms for QMA-Complete Problems,”
SIAM Journal on Computing, vol. 41, no. 4, pp. 1028–1050, 2012, doi: 10.1137/110842272.'
mla: Gharibian, Sevag, and Julia Kempe. “Approximation Algorithms for QMA-Complete
Problems.” SIAM Journal on Computing, vol. 41, no. 4, Society for Industrial
& Applied Mathematics (SIAM), 2012, pp. 1028–50, doi:10.1137/110842272.
short: S. Gharibian, J. Kempe, SIAM Journal on Computing 41 (2012) 1028–1050.
date_created: 2019-03-01T12:04:03Z
date_updated: 2023-02-28T11:03:50Z
department:
- _id: '623'
- _id: '7'
doi: 10.1137/110842272
extern: '1'
external_id:
arxiv:
- '1101.3884'
intvolume: ' 41'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1101.3884
oa: '1'
page: 1028-1050
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
publisher: Society for Industrial & Applied Mathematics (SIAM)
status: public
title: Approximation Algorithms for QMA-Complete Problems
type: journal_article
user_id: '71541'
volume: 41
year: '2012'
...
---
_id: '23739'
abstract:
- lang: eng
text: "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.\r\n"
author:
- first_name: Patrick
full_name: Briest, Patrick
last_name: Briest
- first_name: Piotr
full_name: Krysta, Piotr
last_name: Krysta
- first_name: Berthold
full_name: Vöcking, Berthold
last_name: Vöcking
citation:
ama: Briest P, Krysta P, Vöcking B. Approximation Techniques for Utilitarian Mechanism
Design. SIAM Journal on Computing. 2011:1587-1622. doi:10.1137/090772988
apa: Briest, P., Krysta, P., & Vöcking, B. (2011). Approximation Techniques
for Utilitarian Mechanism Design. SIAM Journal on Computing, 1587–1622.
https://doi.org/10.1137/090772988
bibtex: '@article{Briest_Krysta_Vöcking_2011, title={Approximation Techniques for
Utilitarian Mechanism Design}, DOI={10.1137/090772988},
journal={SIAM Journal on Computing}, author={Briest, Patrick and Krysta, Piotr
and Vöcking, Berthold}, year={2011}, pages={1587–1622} }'
chicago: Briest, Patrick, Piotr Krysta, and Berthold Vöcking. “Approximation Techniques
for Utilitarian Mechanism Design.” SIAM Journal on Computing, 2011, 1587–1622.
https://doi.org/10.1137/090772988.
ieee: P. Briest, P. Krysta, and B. Vöcking, “Approximation Techniques for Utilitarian
Mechanism Design,” SIAM Journal on Computing, pp. 1587–1622, 2011.
mla: Briest, Patrick, et al. “Approximation Techniques for Utilitarian Mechanism
Design.” SIAM Journal on Computing, 2011, pp. 1587–622, doi:10.1137/090772988.
short: P. Briest, P. Krysta, B. Vöcking, SIAM Journal on Computing (2011) 1587–1622.
date_created: 2021-09-03T10:41:04Z
date_updated: 2022-01-06T06:55:59Z
department:
- _id: '63'
doi: 10.1137/090772988
language:
- iso: eng
page: 1587-1622
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: Approximation Techniques for Utilitarian Mechanism Design
type: journal_article
user_id: '15415'
year: '2011'
...
---
_id: '23740'
abstract:
- lang: eng
text: "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.\r\n"
author:
- first_name: Patrick
full_name: Briest, Patrick
last_name: Briest
- first_name: Piotr
full_name: Krysta, Piotr
last_name: Krysta
citation:
ama: 'Briest P, Krysta P. Buying Cheap Is Expensive: Approximability of Combinatorial
Pricing Problems. SIAM Journal on Computing. 2011:1554-1586. doi:10.1137/090752353'
apa: 'Briest, P., & Krysta, P. (2011). Buying Cheap Is Expensive: Approximability
of Combinatorial Pricing Problems. SIAM Journal on Computing, 1554–1586.
https://doi.org/10.1137/090752353'
bibtex: '@article{Briest_Krysta_2011, title={Buying Cheap Is Expensive: Approximability
of Combinatorial Pricing Problems}, DOI={10.1137/090752353},
journal={SIAM Journal on Computing}, author={Briest, Patrick and Krysta, Piotr},
year={2011}, pages={1554–1586} }'
chicago: 'Briest, Patrick, and Piotr Krysta. “Buying Cheap Is Expensive: Approximability
of Combinatorial Pricing Problems.” SIAM Journal on Computing, 2011, 1554–86.
https://doi.org/10.1137/090752353.'
ieee: 'P. Briest and P. Krysta, “Buying Cheap Is Expensive: Approximability of Combinatorial
Pricing Problems,” SIAM Journal on Computing, pp. 1554–1586, 2011.'
mla: 'Briest, Patrick, and Piotr Krysta. “Buying Cheap Is Expensive: Approximability
of Combinatorial Pricing Problems.” SIAM Journal on Computing, 2011, pp.
1554–86, doi:10.1137/090752353.'
short: P. Briest, P. Krysta, SIAM Journal on Computing (2011) 1554–1586.
date_created: 2021-09-03T10:48:52Z
date_updated: 2022-01-06T06:55:59Z
department:
- _id: '63'
doi: 10.1137/090752353
language:
- iso: eng
page: 1554-1586
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: 'Buying Cheap Is Expensive: Approximability of Combinatorial Pricing Problems'
type: journal_article
user_id: '15415'
year: '2011'
...
---
_id: '42803'
abstract:
- lang: eng
text: 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:
- first_name: Markus
full_name: Kirschmer, Markus
id: '82258'
last_name: Kirschmer
- first_name: John
full_name: Voight, John
last_name: Voight
citation:
ama: Kirschmer M, Voight J. Algorithmic Enumeration of Ideal Classes for Quaternion
Orders. SIAM Journal on Computing. 2010;39(5):1714-1747. doi:10.1137/080734467
apa: Kirschmer, M., & Voight, J. (2010). Algorithmic Enumeration of Ideal Classes
for Quaternion Orders. SIAM Journal on Computing, 39(5), 1714–1747.
https://doi.org/10.1137/080734467
bibtex: '@article{Kirschmer_Voight_2010, title={Algorithmic Enumeration of Ideal
Classes for Quaternion Orders}, volume={39}, DOI={10.1137/080734467},
number={5}, journal={SIAM Journal on Computing}, publisher={Society for Industrial
& Applied Mathematics (SIAM)}, author={Kirschmer, Markus and Voight, John},
year={2010}, pages={1714–1747} }'
chicago: 'Kirschmer, Markus, and John Voight. “Algorithmic Enumeration of Ideal
Classes for Quaternion Orders.” SIAM Journal on Computing 39, no. 5 (2010):
1714–47. https://doi.org/10.1137/080734467.'
ieee: 'M. Kirschmer and J. Voight, “Algorithmic Enumeration of Ideal Classes for
Quaternion Orders,” SIAM Journal on Computing, vol. 39, no. 5, pp. 1714–1747,
2010, doi: 10.1137/080734467.'
mla: Kirschmer, Markus, and John Voight. “Algorithmic Enumeration of Ideal Classes
for Quaternion Orders.” SIAM Journal on Computing, vol. 39, no. 5, Society
for Industrial & Applied Mathematics (SIAM), 2010, pp. 1714–47, doi:10.1137/080734467.
short: M. Kirschmer, J. Voight, SIAM Journal on Computing 39 (2010) 1714–1747.
date_created: 2023-03-07T08:49:35Z
date_updated: 2023-04-04T09:25:08Z
department:
- _id: '102'
doi: 10.1137/080734467
extern: '1'
intvolume: ' 39'
issue: '5'
keyword:
- General Mathematics
- General Computer Science
language:
- iso: eng
page: 1714-1747
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
publisher: Society for Industrial & Applied Mathematics (SIAM)
status: public
title: Algorithmic Enumeration of Ideal Classes for Quaternion Orders
type: journal_article
user_id: '93826'
volume: 39
year: '2010'
...
---
_id: '18763'
abstract:
- lang: eng
text: "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.\r\n\r\nWe 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.\r\n\r\nOur 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:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
citation:
ama: Czumaj A, Sohler C. Abstract Combinatorial Programs and Efficient Property
Testers. SIAM Journal on Computing. 2005;34(3):580-615. doi:10.1137/s009753970444199x
apa: Czumaj, A., & Sohler, C. (2005). Abstract Combinatorial Programs and Efficient
Property Testers. SIAM Journal on Computing, 34(3), 580–615. https://doi.org/10.1137/s009753970444199x
bibtex: '@article{Czumaj_Sohler_2005, title={Abstract Combinatorial Programs and
Efficient Property Testers}, volume={34}, DOI={10.1137/s009753970444199x},
number={3}, journal={SIAM Journal on Computing}, author={Czumaj, Artur and Sohler,
Christian}, year={2005}, pages={580–615} }'
chicago: 'Czumaj, Artur, and Christian Sohler. “Abstract Combinatorial Programs
and Efficient Property Testers.” SIAM Journal on Computing 34, no. 3 (2005):
580–615. https://doi.org/10.1137/s009753970444199x.'
ieee: A. Czumaj and C. Sohler, “Abstract Combinatorial Programs and Efficient Property
Testers,” SIAM Journal on Computing, vol. 34, no. 3, pp. 580–615, 2005.
mla: Czumaj, Artur, and Christian Sohler. “Abstract Combinatorial Programs and Efficient
Property Testers.” SIAM Journal on Computing, vol. 34, no. 3, 2005, pp.
580–615, doi:10.1137/s009753970444199x.
short: A. Czumaj, C. Sohler, SIAM Journal on Computing 34 (2005) 580–615.
date_created: 2020-09-01T11:35:41Z
date_updated: 2022-01-06T06:53:52Z
department:
- _id: '63'
doi: 10.1137/s009753970444199x
intvolume: ' 34'
issue: '3'
language:
- iso: eng
page: 580-615
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: Abstract Combinatorial Programs and Efficient Property Testers
type: journal_article
user_id: '15415'
volume: 34
year: '2005'
...
---
_id: '18855'
abstract:
- lang: eng
text: "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.\r\n\r\n\r\nRead
More: https://epubs.siam.org/doi/10.1137/S0097539703435297\r\n"
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Funda
full_name: Ergün, Funda
last_name: Ergün
- first_name: Lance
full_name: Fortnow, Lance
last_name: Fortnow
- first_name: Avner
full_name: Magen, Avner
last_name: Magen
- first_name: Ilan
full_name: Newman, Ilan
last_name: Newman
- first_name: Ronitt
full_name: Rubinfeld, Ronitt
last_name: Rubinfeld
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
citation:
ama: Czumaj A, Ergün F, Fortnow L, et al. Approximating the Weight of the Euclidean
Minimum Spanning Tree in Sublinear Time. SIAM Journal on Computing. 2005;35(1):91-109.
doi:10.1137/s0097539703435297
apa: Czumaj, A., Ergün, F., Fortnow, L., Magen, A., Newman, I., Rubinfeld, R., &
Sohler, C. (2005). Approximating the Weight of the Euclidean Minimum Spanning
Tree in Sublinear Time. SIAM Journal on Computing, 35(1), 91–109.
https://doi.org/10.1137/s0097539703435297
bibtex: '@article{Czumaj_Ergün_Fortnow_Magen_Newman_Rubinfeld_Sohler_2005, title={Approximating
the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time}, volume={35},
DOI={10.1137/s0097539703435297},
number={1}, journal={SIAM Journal on Computing}, author={Czumaj, Artur and Ergün,
Funda and Fortnow, Lance and Magen, Avner and Newman, Ilan and Rubinfeld, Ronitt
and Sohler, Christian}, year={2005}, pages={91–109} }'
chicago: 'Czumaj, Artur, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt
Rubinfeld, and Christian Sohler. “Approximating the Weight of the Euclidean Minimum
Spanning Tree in Sublinear Time.” SIAM Journal on Computing 35, no. 1 (2005):
91–109. https://doi.org/10.1137/s0097539703435297.'
ieee: A. Czumaj et al., “Approximating the Weight of the Euclidean Minimum
Spanning Tree in Sublinear Time,” SIAM Journal on Computing, vol. 35, no.
1, pp. 91–109, 2005.
mla: Czumaj, Artur, et al. “Approximating the Weight of the Euclidean Minimum Spanning
Tree in Sublinear Time.” SIAM Journal on Computing, vol. 35, no. 1, 2005,
pp. 91–109, doi:10.1137/s0097539703435297.
short: A. Czumaj, F. Ergün, L. Fortnow, A. Magen, I. Newman, R. Rubinfeld, C. Sohler,
SIAM Journal on Computing 35 (2005) 91–109.
date_created: 2020-09-02T12:13:26Z
date_updated: 2022-01-06T06:53:53Z
department:
- _id: '63'
doi: 10.1137/s0097539703435297
intvolume: ' 35'
issue: '1'
language:
- iso: eng
page: 91-109
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear
Time
type: journal_article
user_id: '15415'
volume: 35
year: '2005'
...
---
_id: '19952'
abstract:
- lang: eng
text: 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:
- first_name: Fedor V.
full_name: Fomin, Fedor V.
last_name: Fomin
- first_name: Dimitrios M.
full_name: Thilikos, Dimitrios M.
last_name: Thilikos
citation:
ama: 'Fomin FV, Thilikos DM. Dominating Sets in Planar Graphs: Branch-Width and
Exponential Speed-Up. In: Proceedings of the 14th ACM-SIAM Symposium on Discrete
Algorithms (SODA 2003). ; 2003. doi:10.1137/s0097539702419649'
apa: 'Fomin, F. V., & Thilikos, D. M. (2003). Dominating Sets in Planar Graphs:
Branch-Width and Exponential Speed-Up. In Proceedings of the 14th ACM-SIAM
Symposium on Discrete Algorithms (SODA 2003). https://doi.org/10.1137/s0097539702419649'
bibtex: '@inproceedings{Fomin_Thilikos_2003, title={Dominating Sets in Planar Graphs:
Branch-Width and Exponential Speed-Up}, DOI={10.1137/s0097539702419649},
booktitle={Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA
2003)}, author={Fomin, Fedor V. and Thilikos, Dimitrios M.}, year={2003} }'
chicago: 'Fomin, Fedor V., and Dimitrios M. Thilikos. “Dominating Sets in Planar
Graphs: Branch-Width and Exponential Speed-Up.” In Proceedings of the 14th
ACM-SIAM Symposium on Discrete Algorithms (SODA 2003), 2003. https://doi.org/10.1137/s0097539702419649.'
ieee: 'F. V. Fomin and D. M. Thilikos, “Dominating Sets in Planar Graphs: Branch-Width
and Exponential Speed-Up,” in Proceedings of the 14th ACM-SIAM Symposium on
Discrete Algorithms (SODA 2003), 2003.'
mla: 'Fomin, Fedor V., and Dimitrios M. Thilikos. “Dominating Sets in Planar Graphs:
Branch-Width and Exponential Speed-Up.” Proceedings of the 14th ACM-SIAM Symposium
on Discrete Algorithms (SODA 2003), 2003, doi:10.1137/s0097539702419649.'
short: 'F.V. Fomin, D.M. Thilikos, in: Proceedings of the 14th ACM-SIAM Symposium
on Discrete Algorithms (SODA 2003), 2003.'
date_created: 2020-10-08T10:31:48Z
date_updated: 2022-01-06T06:54:16Z
department:
- _id: '63'
doi: 10.1137/s0097539702419649
language:
- iso: eng
publication: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA
2003)
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: 'Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up'
type: conference
user_id: '15415'
year: '2003'
...
---
_id: '17010'
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Volker
full_name: Stemann, Volker
last_name: Stemann
citation:
ama: Czumaj A, Meyer auf der Heide F, Stemann V. Contention Resolution in Hashing
Based Shared Memory Simulations. SIAM Journal on Computing. 2000:1703-1739.
doi:10.1137/s009753979529564x
apa: Czumaj, A., Meyer auf der Heide, F., & Stemann, V. (2000). Contention Resolution
in Hashing Based Shared Memory Simulations. SIAM Journal on Computing,
1703–1739. https://doi.org/10.1137/s009753979529564x
bibtex: '@article{Czumaj_Meyer auf der Heide_Stemann_2000, title={Contention Resolution
in Hashing Based Shared Memory Simulations}, DOI={10.1137/s009753979529564x},
journal={SIAM Journal on Computing}, author={Czumaj, Artur and Meyer auf der Heide,
Friedhelm and Stemann, Volker}, year={2000}, pages={1703–1739} }'
chicago: Czumaj, Artur, Friedhelm Meyer auf der Heide, and Volker Stemann. “Contention
Resolution in Hashing Based Shared Memory Simulations.” SIAM Journal on Computing,
2000, 1703–39. https://doi.org/10.1137/s009753979529564x.
ieee: A. Czumaj, F. Meyer auf der Heide, and V. Stemann, “Contention Resolution
in Hashing Based Shared Memory Simulations,” SIAM Journal on Computing,
pp. 1703–1739, 2000.
mla: Czumaj, Artur, et al. “Contention Resolution in Hashing Based Shared Memory
Simulations.” SIAM Journal on Computing, 2000, pp. 1703–39, doi:10.1137/s009753979529564x.
short: A. Czumaj, F. Meyer auf der Heide, V. Stemann, SIAM Journal on Computing
(2000) 1703–1739.
date_created: 2020-05-18T13:47:36Z
date_updated: 2022-01-06T06:53:01Z
department:
- _id: '63'
doi: 10.1137/s009753979529564x
language:
- iso: eng
page: 1703-1739
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: Contention Resolution in Hashing Based Shared Memory Simulations
type: journal_article
user_id: '15415'
year: '2000'
...
---
_id: '16701'
author:
- first_name: Joseph
full_name: Gil, Joseph
last_name: Gil
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Avi
full_name: Wigderson, Avi
last_name: Wigderson
citation:
ama: 'Gil J, Meyer auf der Heide F, Wigderson A. The Tree Model for Hashing: Lower
and Upper Bounds. SIAM Journal on Computing. 1996:936-955. doi:10.1137/s0097539793255722'
apa: 'Gil, J., Meyer auf der Heide, F., & Wigderson, A. (1996). The Tree Model
for Hashing: Lower and Upper Bounds. SIAM Journal on Computing, 936–955.
https://doi.org/10.1137/s0097539793255722'
bibtex: '@article{Gil_Meyer auf der Heide_Wigderson_1996, title={The Tree Model
for Hashing: Lower and Upper Bounds}, DOI={10.1137/s0097539793255722},
journal={SIAM Journal on Computing}, author={Gil, Joseph and Meyer auf der Heide,
Friedhelm and Wigderson, Avi}, year={1996}, pages={936–955} }'
chicago: 'Gil, Joseph, Friedhelm Meyer auf der Heide, and Avi Wigderson. “The Tree
Model for Hashing: Lower and Upper Bounds.” SIAM Journal on Computing,
1996, 936–55. https://doi.org/10.1137/s0097539793255722.'
ieee: 'J. Gil, F. Meyer auf der Heide, and A. Wigderson, “The Tree Model for Hashing:
Lower and Upper Bounds,” SIAM Journal on Computing, pp. 936–955, 1996.'
mla: 'Gil, Joseph, et al. “The Tree Model for Hashing: Lower and Upper Bounds.”
SIAM Journal on Computing, 1996, pp. 936–55, doi:10.1137/s0097539793255722.'
short: J. Gil, F. Meyer auf der Heide, A. Wigderson, SIAM Journal on Computing (1996)
936–955.
date_created: 2020-04-16T11:53:57Z
date_updated: 2022-01-06T06:52:54Z
department:
- _id: '63'
doi: 10.1137/s0097539793255722
language:
- iso: eng
page: 936-955
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: 'The Tree Model for Hashing: Lower and Upper Bounds'
type: journal_article
user_id: '15415'
year: '1996'
...
---
_id: '16728'
author:
- first_name: Martin
full_name: Dietzfelbinger, Martin
last_name: Dietzfelbinger
- first_name: Anna
full_name: Karlin, Anna
last_name: Karlin
- first_name: Kurt
full_name: Mehlhorn, Kurt
last_name: Mehlhorn
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Hans
full_name: Rohnert, Hans
last_name: Rohnert
- first_name: Robert E.
full_name: Tarjan, Robert E.
last_name: Tarjan
citation:
ama: 'Dietzfelbinger M, Karlin A, Mehlhorn K, Meyer auf der Heide F, Rohnert H,
Tarjan RE. Dynamic Perfect Hashing: Upper and Lower Bounds. SIAM Journal on
Computing. 1994:738-761. doi:10.1137/s0097539791194094'
apa: 'Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert,
H., & Tarjan, R. E. (1994). Dynamic Perfect Hashing: Upper and Lower Bounds.
SIAM Journal on Computing, 738–761. https://doi.org/10.1137/s0097539791194094'
bibtex: '@article{Dietzfelbinger_Karlin_Mehlhorn_Meyer auf der Heide_Rohnert_Tarjan_1994,
title={Dynamic Perfect Hashing: Upper and Lower Bounds}, DOI={10.1137/s0097539791194094},
journal={SIAM Journal on Computing}, author={Dietzfelbinger, Martin and Karlin,
Anna and Mehlhorn, Kurt and Meyer auf der Heide, Friedhelm and Rohnert, Hans and
Tarjan, Robert E.}, year={1994}, pages={738–761} }'
chicago: 'Dietzfelbinger, Martin, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer auf
der Heide, Hans Rohnert, and Robert E. Tarjan. “Dynamic Perfect Hashing: Upper
and Lower Bounds.” SIAM Journal on Computing, 1994, 738–61. https://doi.org/10.1137/s0097539791194094.'
ieee: 'M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert,
and R. E. Tarjan, “Dynamic Perfect Hashing: Upper and Lower Bounds,” SIAM Journal
on Computing, pp. 738–761, 1994.'
mla: 'Dietzfelbinger, Martin, et al. “Dynamic Perfect Hashing: Upper and Lower Bounds.”
SIAM Journal on Computing, 1994, pp. 738–61, doi:10.1137/s0097539791194094.'
short: M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert,
R.E. Tarjan, SIAM Journal on Computing (1994) 738–761.
date_created: 2020-04-20T10:19:33Z
date_updated: 2022-01-06T06:52:55Z
department:
- _id: '63'
doi: 10.1137/s0097539791194094
language:
- iso: eng
page: 738-761
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: 'Dynamic Perfect Hashing: Upper and Lower Bounds'
type: journal_article
user_id: '15415'
year: '1994'
...
---
_id: '16772'
author:
- first_name: A.
full_name: Borodin, A.
last_name: Borodin
- first_name: F.
full_name: Fich, F.
last_name: Fich
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: E.
full_name: Upfal, E.
last_name: Upfal
- first_name: A.
full_name: Wigderson, A.
last_name: Wigderson
citation:
ama: Borodin A, Fich F, Meyer auf der Heide F, Upfal E, Wigderson A. A Time-Space
Tradeoff for Element Distinctness. SIAM Journal on Computing. 1987:97-99.
doi:10.1137/0216007
apa: Borodin, A., Fich, F., Meyer auf der Heide, F., Upfal, E., & Wigderson,
A. (1987). A Time-Space Tradeoff for Element Distinctness. SIAM Journal on
Computing, 97–99. https://doi.org/10.1137/0216007
bibtex: '@article{Borodin_Fich_Meyer auf der Heide_Upfal_Wigderson_1987, title={A
Time-Space Tradeoff for Element Distinctness}, DOI={10.1137/0216007},
journal={SIAM Journal on Computing}, author={Borodin, A. and Fich, F. and Meyer
auf der Heide, Friedhelm and Upfal, E. and Wigderson, A.}, year={1987}, pages={97–99}
}'
chicago: Borodin, A., F. Fich, Friedhelm Meyer auf der Heide, E. Upfal, and A. Wigderson.
“A Time-Space Tradeoff for Element Distinctness.” SIAM Journal on Computing,
1987, 97–99. https://doi.org/10.1137/0216007.
ieee: A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, and A. Wigderson, “A
Time-Space Tradeoff for Element Distinctness,” SIAM Journal on Computing,
pp. 97–99, 1987.
mla: Borodin, A., et al. “A Time-Space Tradeoff for Element Distinctness.” SIAM
Journal on Computing, 1987, pp. 97–99, doi:10.1137/0216007.
short: A. Borodin, F. Fich, F. Meyer auf der Heide, E. Upfal, A. Wigderson, SIAM
Journal on Computing (1987) 97–99.
date_created: 2020-04-21T10:00:29Z
date_updated: 2022-01-06T06:52:55Z
department:
- _id: '63'
doi: 10.1137/0216007
language:
- iso: eng
page: 97-99
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: A Time-Space Tradeoff for Element Distinctness
type: journal_article
user_id: '15415'
year: '1987'
...
---
_id: '16773'
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Avi
full_name: Wigderson, Avi
last_name: Wigderson
citation:
ama: Meyer auf der Heide F, Wigderson A. The Complexity of Parallel Sorting. SIAM
Journal on Computing. 1987:100-107. doi:10.1137/0216008
apa: Meyer auf der Heide, F., & Wigderson, A. (1987). The Complexity of Parallel
Sorting. SIAM Journal on Computing, 100–107. https://doi.org/10.1137/0216008
bibtex: '@article{Meyer auf der Heide_Wigderson_1987, title={The Complexity of Parallel
Sorting}, DOI={10.1137/0216008},
journal={SIAM Journal on Computing}, author={Meyer auf der Heide, Friedhelm and
Wigderson, Avi}, year={1987}, pages={100–107} }'
chicago: Meyer auf der Heide, Friedhelm, and Avi Wigderson. “The Complexity of Parallel
Sorting.” SIAM Journal on Computing, 1987, 100–107. https://doi.org/10.1137/0216008.
ieee: F. Meyer auf der Heide and A. Wigderson, “The Complexity of Parallel Sorting,”
SIAM Journal on Computing, pp. 100–107, 1987.
mla: Meyer auf der Heide, Friedhelm, and Avi Wigderson. “The Complexity of Parallel
Sorting.” SIAM Journal on Computing, 1987, pp. 100–07, doi:10.1137/0216008.
short: F. Meyer auf der Heide, A. Wigderson, SIAM Journal on Computing (1987) 100–107.
date_created: 2020-04-21T10:01:37Z
date_updated: 2022-01-06T06:52:55Z
department:
- _id: '63'
doi: 10.1137/0216008
language:
- iso: eng
page: 100-107
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: The Complexity of Parallel Sorting
type: journal_article
user_id: '15415'
year: '1987'
...
---
_id: '16771'
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: Meyer auf der Heide F. Efficient Simulations among Several Models of Parallel
Computers. SIAM Journal on Computing. 1986:106-119. doi:10.1137/0215008
apa: Meyer auf der Heide, F. (1986). Efficient Simulations among Several Models
of Parallel Computers. SIAM Journal on Computing, 106–119. https://doi.org/10.1137/0215008
bibtex: '@article{Meyer auf der Heide_1986, title={Efficient Simulations among Several
Models of Parallel Computers}, DOI={10.1137/0215008},
journal={SIAM Journal on Computing}, author={Meyer auf der Heide, Friedhelm},
year={1986}, pages={106–119} }'
chicago: Meyer auf der Heide, Friedhelm. “Efficient Simulations among Several Models
of Parallel Computers.” SIAM Journal on Computing, 1986, 106–19. https://doi.org/10.1137/0215008.
ieee: F. Meyer auf der Heide, “Efficient Simulations among Several Models of Parallel
Computers,” SIAM Journal on Computing, pp. 106–119, 1986.
mla: Meyer auf der Heide, Friedhelm. “Efficient Simulations among Several Models
of Parallel Computers.” SIAM Journal on Computing, 1986, pp. 106–19, doi:10.1137/0215008.
short: F. Meyer auf der Heide, SIAM Journal on Computing (1986) 106–119.
date_created: 2020-04-21T09:59:29Z
date_updated: 2022-01-06T06:52:55Z
department:
- _id: '63'
doi: 10.1137/0215008
language:
- iso: eng
page: 106-119
publication: SIAM Journal on Computing
publication_identifier:
issn:
- 0097-5397
- 1095-7111
publication_status: published
status: public
title: Efficient Simulations among Several Models of Parallel Computers
type: journal_article
user_id: '15415'
year: '1986'
...