Search Results

Documents authored by Karpinski, Marek

Document
DOI: 10.4230/DagRep.5.6.28
Complexity of Symbolic and Numerical Problems (Dagstuhl Seminar 15242)

Authors: Peter Bürgisser, Felipe Cucker, Marek Karpinski, and Nicolai Vorobjov

Published in: Dagstuhl Reports, Volume 5, Issue 6 (2016)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15242 "Complexity of Symbolic and Numerical Problems".
Cite as

Peter Bürgisser, Felipe Cucker, Marek Karpinski, and Nicolai Vorobjov. Complexity of Symbolic and Numerical Problems (Dagstuhl Seminar 15242). In Dagstuhl Reports, Volume 5, Issue 6, pp. 28-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{burgisser_et_al:DagRep.5.6.28,
  author =	{B\"{u}rgisser, Peter and Cucker, Felipe and Karpinski, Marek and Vorobjov, Nicolai},
  title =	{{Complexity of Symbolic and Numerical Problems (Dagstuhl Seminar 15242)}},
  pages =	{28--47},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{6},
  editor =	{B\"{u}rgisser, Peter and Cucker, Felipe and Karpinski, Marek and Vorobjov, Nicolai},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.6.28},
  URN =		{urn:nbn:de:0030-drops-55066},
  doi =		{10.4230/DagRep.5.6.28},
  annote =	{Keywords: Symbolic computation, Algorithms in real algebraic geometry, Complexity lower bounds, Geometry of numerical algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.397
Generalized Wong sequences and their applications to Edmonds' problems

Authors: Gábor Ivanyos, Marek Karpinski, Youming Qiao, and Miklos Santha

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix M whose entries are homogeneous linear polynomials over the integers. Given a linear subspace B of the nxn matrices over some field F, we consider the following problems: symbolic matrix rank (SMR) is the problem to determine the maximum rank among matrices in B, while symbolic determinant identity testing (SDIT) is the question to decide whether there exists a nonsingular matrix in B. The constructive versions of these problems are asking to find a matrix of maximum rank, respectively a nonsingular matrix, if there exists one. Our first algorithm solves the constructive SMR when B is spanned by unknown rank one matrices, answering an open question of Gurvits. Our second algorithm solves the constructive SDIT when B is spanned by triangularizable matrices, but the triangularization is not given explicitly. Both algorithms work over finite fields of size at least n+1 and over the rational numbers, and the first algorithm actually solves (the non-constructive) SMR independent of the field size. Our main tool to obtain these results is to generalize Wong sequences, a classical method to deal with pairs of matrices, to the case of pairs of matrix spaces.
Cite as

Gábor Ivanyos, Marek Karpinski, Youming Qiao, and Miklos Santha. Generalized Wong sequences and their applications to Edmonds' problems. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 397-408, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{ivanyos_et_al:LIPIcs.STACS.2014.397,
  author =	{Ivanyos, G\'{a}bor and Karpinski, Marek and Qiao, Youming and Santha, Miklos},
  title =	{{Generalized Wong sequences and their applications to Edmonds' problems}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{397--408},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.397},
  URN =		{urn:nbn:de:0030-drops-44741},
  doi =		{10.4230/LIPIcs.STACS.2014.397},
  annote =	{Keywords: symbolic determinantal identity testing, Edmonds' problem, maximum rank matrix completion, derandomization, Wong sequences}
}
Document
DOI: 10.4230/DagRep.1.6.24
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241)

Authors: Martin Dyer, Uriel Feige, Alan M. Frieze, and Marek Karpinski

Published in: Dagstuhl Reports, Volume 1, Issue 6 (2011)

Abstract
The Dagstuhl Seminar on ``Design and Analysis of Randomized and Approximation Algorithms'' (Seminar 11241) was held at Schloss Dagstuhl between June 13--17, 2011. There were 26 regular talks and several informal and open problem session contributions presented during this seminar. Abstracts of the presentations have been put together in this seminar proceedings document together with some links to extended abstracts and full papers.
Cite as

Martin Dyer, Uriel Feige, Alan M. Frieze, and Marek Karpinski. Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). In Dagstuhl Reports, Volume 1, Issue 6, pp. 24-53, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@Article{dyer_et_al:DagRep.1.6.24,
  author =	{Dyer, Martin and Feige, Uriel and Frieze, Alan M. and Karpinski, Marek},
  title =	{{Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241)}},
  pages =	{24--53},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{6},
  editor =	{Dyer, Martin and Feige, Uriel and Frieze, Alan M. and Karpinski, Marek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.6.24},
  URN =		{urn:nbn:de:0030-drops-32585},
  doi =		{10.4230/DagRep.1.6.24},
  annote =	{Keywords: Randomized Algorithms, Approximation Algorithms, Probabilistically Checkable Proofs, Approximation Hardness, Optimization Problems, Counting Problems, Streaming Algorithms, Random Graphs, Hypergraphs, Probabilistic Method, Networks, Linear Programs, Semidefinite Programs}
}
Document
DOI: 10.4230/DagSemProc.08201.1
08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms

Authors: Martin E. Dyer, Mark Jerrum, and Marek Karpinski

Published in: Dagstuhl Seminar Proceedings, Volume 8201, Design and Analysis of Randomized and Approximation Algorithms (2008)

Abstract
From 11.05.08 to 16.05.08, the Dagstuhl Seminar 08201 ``Design and Analysis of Randomized and Approximation Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research work, and ongoing work and open problems were discussed. Abstracts of the presentations which were given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full paper are provided, if available.
Cite as

Martin E. Dyer, Mark Jerrum, and Marek Karpinski. 08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms. In Design and Analysis of Randomized and Approximation Algorithms. Dagstuhl Seminar Proceedings, Volume 8201, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{dyer_et_al:DagSemProc.08201.1,
  author =	{Dyer, Martin E. and Jerrum, Mark and Karpinski, Marek},
  title =	{{08201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms}},
  booktitle =	{Design and Analysis of Randomized and Approximation Algorithms},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8201},
  editor =	{Martin E. Dyer and Mark Jerrum and Marek Karpinski},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08201.1},
  URN =		{urn:nbn:de:0030-drops-15518},
  doi =		{10.4230/DagSemProc.08201.1},
  annote =	{Keywords: Randomized Algorithms, Approximation Algorithms, Optimization Problems, Measurement Problems, Approximation Complexity, Algorithmic Game Theory, Internet, Decentralized Networks, Network Design}
}
Document
DOI: 10.4230/DagSemProc.05201.1
05201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms

Authors: Martin Dyer, Mark Jerrum, and Marek Karpinski

Published in: Dagstuhl Seminar Proceedings, Volume 5201, Design and Analysis of Randomized and Approximation Algorithms (2005)

Abstract
From 15.05.05 to 20.05.05, the Dagstuhl Seminar 05201 ``Design and Analysis of Randomized and Approximation Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Martin Dyer, Mark Jerrum, and Marek Karpinski. 05201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms. In Design and Analysis of Randomized and Approximation Algorithms. Dagstuhl Seminar Proceedings, Volume 5201, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{dyer_et_al:DagSemProc.05201.1,
  author =	{Dyer, Martin and Jerrum, Mark and Karpinski, Marek},
  title =	{{05201 Abstracts Collection – Design and Analysis of Randomized and Approximation Algorithms}},
  booktitle =	{Design and Analysis of Randomized and Approximation Algorithms},
  pages =	{1--21},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5201},
  editor =	{Martin Dyer and Mark Jerrum and Marek Karpinski},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05201.1},
  URN =		{urn:nbn:de:0030-drops-3191},
  doi =		{10.4230/DagSemProc.05201.1},
  annote =	{Keywords: Randomized Algorithms, Approximation Algorithms, Optimization Problems, Measurement Problems, Decentralized Networks}
}
Document
DOI: 10.4230/DagSemRep.386
Algorithmic Game Theory and the Internet (Dagstuhl Seminar 03291)

Authors: Marek Karpinski, Christos H. Papadimitriou, and Vijay V. Vazirani

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Marek Karpinski, Christos H. Papadimitriou, and Vijay V. Vazirani. Algorithmic Game Theory and the Internet (Dagstuhl Seminar 03291). Dagstuhl Seminar Report 386, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{karpinski_et_al:DagSemRep.386,
  author =	{Karpinski, Marek and Papadimitriou, Christos H. and Vazirani, Vijay V.},
  title =	{{Algorithmic Game Theory and the Internet (Dagstuhl Seminar 03291)}},
  pages =	{1--9},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{386},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.386},
  URN =		{urn:nbn:de:0030-drops-152660},
  doi =		{10.4230/DagSemRep.386},
}
Document
DOI: 10.4230/DagSemRep.309
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231)

Authors: Martin Dyer, Mark Jerrum, and Marek Karpinski

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Martin Dyer, Mark Jerrum, and Marek Karpinski. Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231). Dagstuhl Seminar Report 309, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{dyer_et_al:DagSemRep.309,
  author =	{Dyer, Martin and Jerrum, Mark and Karpinski, Marek},
  title =	{{Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231)}},
  pages =	{1--28},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{309},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.309},
  URN =		{urn:nbn:de:0030-drops-151930},
  doi =		{10.4230/DagSemRep.309},
}
Document
DOI: 10.4230/DagSemRep.41
Algebraic Complexity and Parallelism (Dagstuhl Seminar 9230)

Authors: Joachim von zur Gathen, Marek Karpinski, and Dexter Kozen

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Joachim von zur Gathen, Marek Karpinski, and Dexter Kozen. Algebraic Complexity and Parallelism (Dagstuhl Seminar 9230). Dagstuhl Seminar Report 41, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1992)

Copy BibTex To Clipboard

@TechReport{vonzurgathen_et_al:DagSemRep.41,
  author =	{von zur Gathen, Joachim and Karpinski, Marek and Kozen, Dexter},
  title =	{{Algebraic Complexity and Parallelism (Dagstuhl Seminar 9230)}},
  pages =	{1--16},
  ISSN =	{1619-0203},
  year =	{1992},
  type = 	{Dagstuhl Seminar Report},
  number =	{41},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.41},
  URN =		{urn:nbn:de:0030-drops-149291},
  doi =		{10.4230/DagSemRep.41},
}
Document
DOI: 10.4230/DagSemRep.26
Efficient Interpolation Algorithms (Dagstuhl Seminar 9149)

Authors: Andreas Dress, Marek Karpinski, and Michael Singer

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Andreas Dress, Marek Karpinski, and Michael Singer. Efficient Interpolation Algorithms (Dagstuhl Seminar 9149). Dagstuhl Seminar Report 26, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1992)

Copy BibTex To Clipboard

@TechReport{dress_et_al:DagSemRep.26,
  author =	{Dress, Andreas and Karpinski, Marek and Singer, Michael},
  title =	{{Efficient Interpolation Algorithms (Dagstuhl Seminar 9149)}},
  pages =	{1--15},
  ISSN =	{1619-0203},
  year =	{1992},
  type = 	{Dagstuhl Seminar Report},
  number =	{26},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.26},
  URN =		{urn:nbn:de:0030-drops-149141},
  doi =		{10.4230/DagSemRep.26},
}
Document
DOI: 10.4230/DagSemRep.14
Randomized Algorithms (Dagstuhl Seminar 9124)

Authors: Marek Karpinski, Michael Luby, and Umesh Vazirani

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Marek Karpinski, Michael Luby, and Umesh Vazirani. Randomized Algorithms (Dagstuhl Seminar 9124). Dagstuhl Seminar Report 14, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1991)

Copy BibTex To Clipboard

@TechReport{karpinski_et_al:DagSemRep.14,
  author =	{Karpinski, Marek and Luby, Michael and Vazirani, Umesh},
  title =	{{Randomized Algorithms (Dagstuhl Seminar 9124)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{1991},
  type = 	{Dagstuhl Seminar Report},
  number =	{14},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.14},
  URN =		{urn:nbn:de:0030-drops-149022},
  doi =		{10.4230/DagSemRep.14},
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact