×
Author ID: karpinski.marek Recent zbMATH articles by "Karpinski, Marek"
Published as: Karpinski, Marek; Karpinski, M.; Karpiński, Marek
Homepage: http://theory.cs.uni-bonn.de/~marek/
External Links: MGP · Wikidata · Google Scholar · dblp · GND · IdRef
all top 5

Co-Authors

26 single-authored
19 Grigor’ev, Dmitriĭ Yur’evich
17 Berman, Piotr
11 Fernandez de la Vega, Wenceslas
11 Lingas, Andrzej
8 Dahlhaus, Elias
8 Ivanyos, Gábor
8 Rytter, Wojciech
8 Shparlinski, Igor E.
7 Nekrich, Yakov
6 Ablaev, Farid M.
6 Freivalds, Rūsiņš Mārtiņš
6 Schmied, Richard
6 Verbeek, Rutger
6 Zelikovsky, Alexander Z.
5 Hauptmann, Mathias
5 Macintyre, Angus John
5 Ruciński, Andrzej
5 Saxena, Nitin
5 Szymańska, Edyta
4 Gast, Mikael
4 Kannan, Ravindran
4 Markó, Roland
4 Singer, Michael F.
3 Bazgan, Cristina
3 Bordewich, Magnus
3 Danecki, Ryszard
3 DasGupta, Bhaskar
3 Dyer, Martin E.
3 Hellerstein, Lisa
3 Larmore, Lawrence L.
3 Lickteig, Thomas
3 Manoussakis, Yannis G.
3 Meyer auf der Heide, Friedhelm
3 Santha, Miklos
3 Schudy, Warren
3 Sledneu, Dzmitry
3 Smolensky, Roman
3 Viehmann, Claus
3 Vorob’ëv, Nikolaĭ N. jun.
2 Alon, Noga
2 Ambainis, Andris
2 Anglès d’Auriac, Jean-Alexandre
2 Arora, Sanjeev
2 Bujtás, Csilla
2 Bürgisser, Peter
2 Cardinal, Jean
2 Charikar, Moses S.
2 Ebbers-Baumann, Annette
2 Engebretsen, Lars
2 Evdokimov, Sergeĭ Alekseevich
2 Feige, Uriel
2 Gainutdinova, Aida
2 Goldmann, Mikael
2 Grune, Ansgar
2 Jansen, Klaus
2 Karger, David R.
2 Kenyon, Claire M.
2 Klein, Rolf-Dieter
2 Kleine Büning, Hans
2 Knauer, Christian
2 Lampis, Michael
2 Langberg, Michael
2 Luby, Michael G.
2 Măndoiu, Ion I.
2 Montero, Leandro P.
2 Mubarakzjanov, Rustam
2 Narayanan, Narayanan
2 Odlyzko, Andrew M.
2 Olshevsky, Alexander
2 Plandowski, Wojciech
2 Ponomarenko, Ilya Nikolaevich
2 Qiao, Youming
2 Rosaz, Laurent
2 Seidel, Eike
2 Smith, Carl H.
2 Thapper, Johan
2 Tuza, Zsolt
2 von zur Gathen, Joachim
1 Abouelaoualim, A.
1 Albers, Susanne
1 Angluin, Dana
1 Apsītis, Kalvis
1 Arora, Manuel
1 Bonner, Richard F.
1 Bshouty, Nader H.
1 Calude, Cristian S.
1 Chistov, Alexandre L.
1 Clausen, Michael
1 Csaba, Béla
1 Cucker, Felipe
1 Das, Kinkar Chandra
1 Dress, Andreas W. M.
1 Dudek, Andrzej
1 El Maftouhi, Abdelhakim
1 El Maftouhi, Hakim
1 Flögel, Andreas
1 Gąsieniec, Leszek Antoni
1 Gobleja, Dace
1 Goldberg, Leslie Ann
1 Golovkins, Marats
...and 34 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

158 Publications have been cited 1,416 times in 1,135 Documents Cited by Year
Resolution for quantified Boolean formulas. Zbl 0828.68045
Kleine Büning, Hans; Karpinski, Marek; Flögel, Andreas
94
1995
Learning read-once formulas with queries. Zbl 0764.68139
Angluin, Dana; Hellerstein, Lisa; Karpinski, Marek
52
1993
Polynomial time approximation schemes for dense instances of NP-hard problems. Zbl 0968.68534
Arora, Sanjeev; Karger, David; Karpinski, Marek
49
1995
Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems. Zbl 0937.68160
Arora, Sanjeev; Karger, David; Karpinski, Marek
45
1999
On-line load balancing for related machines. Zbl 0954.68050
Berman, Piotr; Charikar, Moses; Karpinski, Marek
40
2000
1. 375-approximation algorithm for sorting by reversals. Zbl 1019.68817
Berman, Piotr; Hannenhalli, Sridhar; Karpinski, Marek
32
2002
Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. Zbl 1310.68272
Karpinski, Marek; Schudy, Warren
32
2010
\(8/7\)-approximation algorithm for \((1,2)\)-TSP. Zbl 1192.90158
Berman, Piotr; Karpinski, Marek
32
2006
Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks. Zbl 0869.68088
Karpinski, Marek; Macintyre, Angus
31
1997
Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. Zbl 0711.68059
Grigoriev, Dima Yu.; Karpinski, Marek; Singer, Michael F.
27
1990
Polynomial time algorithms for modules over finite dimensional algebras. Zbl 0918.16001
Chistov, Alexander; Ivanyos, Gábor; Karpinski, Marek
26
1997
New approximation algorithms for the Steiner tree problems. Zbl 0895.90171
Karpinski, Marek; Zelikovsky, Alexander
25
1997
An efficient pattern-matching algorithm for strings with short descriptions. Zbl 0874.68087
Karpinski, Marek; Rytter, Wojciech; Shinohara, Ayumi
25
1997
Approximation schemes for clustering problems. Zbl 1192.68894
Fernandez de la Vega, W.; Karpinski, Marek; Kenyon, Claire; Rabani, Yuval
25
2003
New inapproximability bounds for TSP. Zbl 1328.68076
Karpinski, Marek; Lampis, Michael; Schmied, Richard
24
2015
An exponential lower bound for depth 3 arithmetic circuits. Zbl 1028.68069
Grigoriev, Dima; Karpinski, Marek
23
1998
Approximating dense cases of covering problems. Zbl 0896.68078
Karpinski, Marek; Zelikovsky, Alexander
22
1998
Efficient algorithms for Lempel-Ziv encoding (extended abstract). Zbl 1502.68379
Gasieniec, Leszek; Karpinski, Marek; Plandowski, Wojciech; Rytter, Wojciech
20
1996
On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields. Zbl 0737.65002
Clausen, Michael; Dress, Andreas; Grabmeier, Johannes; Karpinski, Marek
20
1991
Matching and multidimensional matching in chordal and strongly chordal graphs. Zbl 0902.68146
Dahlhaus, Elias; Karpinski, Marek
19
1998
Deterministic polynomial time algorithms for matrix completion problems. Zbl 1209.68269
Ivanyos, Gábor; Karpinski, Marek; Saxena, Nitin
19
2010
Random sampling and approximation of MAX-CSPs. Zbl 1160.68537
Alon, Noga; Fernandez de la Vega, W.; Kannan, Ravi; Karpinski, Marek
18
2003
Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. Zbl 1087.90063
Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike
17
2005
On the computational power of probabilistic and quantum branching program. Zbl 1105.68037
Ablayev, Farid; Gainutdinova, Aida; Karpinski, Marek; Moore, Cristopher; Pollett, Christopher
17
2005
Polynomial bounds for VC dimension of sigmoidal neural networks. Zbl 0978.68562
Karpinski, Marek; Macintyre, Angus
16
1995
Cycles and paths in edge-colored graphs with given degrees. Zbl 1202.05067
Abouelaoualim, A.; Das, K. Ch.; de la Vega, W. Fernandez; Karpinski, M.; Manoussakis, Y.; Martinhon, C. A.; Saad, R.
16
2010
On the power of randomized branching programs. Zbl 1046.68531
Ablayev, Farid; Karpinski, Marek
15
1996
Generalized Wong sequences and their applications to Edmonds’ problems. Zbl 1320.68222
Ivanyos, Gábor; Karpinski, Marek; Qiao, Youming; Santha, Miklos
15
2015
Top-\(K\) color queries for document retrieval. Zbl 1373.68197
Karpinski, Marek; Nekrich, Yakov
15
2011
Subtree isomorphism is NC reducible to bipartite perfect matching. Zbl 0664.68072
Lingas, Andrzej; Karpinski, Marek
14
1989
Approximation hardness of TSP with bounded metrics. Zbl 0986.90082
Engebretsen, Lars; Karpinski, Marek
13
2001
New inapproximability bounds for TSP. Zbl 1328.68075
Karpinski, Marek; Lampis, Michael; Schmied, Richard
13
2013
Computational complexity of sparse rational interpolation. Zbl 0802.68060
Grigoriev, Dima; Karpinski, Marek; Singer, Michael F.
12
1994
Simulating threshold circuits by majority circuits. Zbl 0912.68030
Goldmann, Mikael; Karpinski, Marek
12
1998
Fast parallel algorithms for graph matching problems. Zbl 0895.05050
Karpinski, Marek; Rytter, Wojciech
12
1998
On the complexity of pattern matching for highly compressed two-dimensional texts. Zbl 1059.68098
Berman, Piotr; Karpinski, Marek; Larmore, Lawrence L.; Plandowski, Wojciech; Rytter, Wojciech
12
2002
On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes. Zbl 0631.68047
Karpinski, Marek; Verbeek, Rutger
12
1987
Counting curves and their projections. Zbl 0990.68642
von zur Gathen, Joachim; Karpinski, Marek; Shparlinski, Igor
11
1997
Improved approximation of max-cut on graphs of bounded degree. Zbl 1050.68110
Feige, Uriel; Karpinski, Marek; Langberg, Michael
11
2002
On computational power of quantum branching programs. Zbl 0999.68071
Ablayev, Farid; Gainutdinova, Aida; Karpinski, Marek
11
2001
Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. Zbl 1093.68677
Csaba, Béla; Karpinski, Marek; Krysta, Piotr
11
2002
Approximability of the minimum bisection problem: An algorithmic challenge. Zbl 1014.68115
Karpinski, Marek
11
2002
Inapproximability of dominating set on power law graphs. Zbl 1305.05174
Gast, Mikael; Hauptmann, Mathias; Karpinski, Marek
11
2015
Random sampling and approximation of MAX-CSP problems. Zbl 1192.68865
Alon, Noga; Fernandez de la Vega, W.; Kannan, Ravi; Karpinski, Marek
11
2002
A zero-test and an interpolation algorithm for the shifted sparse polynomials. Zbl 0809.68072
Grigoriev, Dima; Karpinski, Marek
10
1993
TSP with bounded metrics. Zbl 1125.90066
Engebretsen, Lars; Karpinski, Marek
10
2006
On real Turing machines that toss coins. Zbl 0938.68648
Cucker, Felipe; Karpinski, Marek; Koiran, Pascal; Lickteig, Thomas; Werther, Kai
10
1995
On a new high dimensional Weisfeiler-Lehman algorithm. Zbl 0936.05070
Evdokimov, Sergei; Karpinski, Marek; Ponomarenko, Ilia
10
1999
Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Zbl 1181.05061
Bordewich, Magnus; Dyer, Martin; Karpinski, Marek
10
2008
Polynomial time approximation schemes for some dense instances of NP-hard optimization problems. Zbl 0985.68089
Karpinski, M.
9
2001
Computational complexity of the perfect matching problem in hypergraphs with subcritical density. Zbl 1206.68147
Karpiński, Marek; Ruciński, Andrzej; Szymańska, Edyta
9
2010
The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators. Zbl 0785.12004
Grigoriev, Dima Yu.; Karpinski, Marek; Singer, Michael F.
9
1991
VC dimension and uniform learnability of sparse polynomials and rational functions. Zbl 0799.68158
Karpinski, Marek; Werther, Thorsten
8
1993
Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. Zbl 0976.68523
Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike
8
2001
A generalization of Wilkie’s theorem of the complement, and an application to Pfaffian closure. Zbl 0953.03046
Karpinski, Marek; Macintyre, Angus
8
1999
Learning read-once formulas using membership queries. Zbl 0747.68046
Hellerstein, Lisa; Karpinski, Marek
8
1989
Tensor decomposition and approximation schemes for constraint satisfaction problems. Zbl 1192.68920
de la Vega, W. Fernandez; Kannan, Ravi; Karpinski, Marek; Vempala, Santosh
8
2005
On some approximation problems concerning sparse polynomials over finite fields. Zbl 0871.11086
Karpinski, Marek; Shparlinski, Igor
7
1996
A fast parallel algorithm for computing all maximal cliques in a graph and the related problems. Zbl 0656.68070
Dahlhaus, Elias; Karpinski, Marek
7
1988
A note on approximating Max-Bisection on regular graphs. Zbl 1032.68119
Feige, U.; Karpinski, M.; Langberg, M.
7
2001
Computational complexity of some restricted instances of 3-SAT. Zbl 1111.68044
Berman, Piotr; Karpinski, Marek; Scott, Alexander D.
7
2007
Approximating the number of zeroes of a \(GF[2]\) polynomial. Zbl 0769.11047
Karpinski, Marek; Luby, Michael
7
1993
Approximation hardness of graphic TSP on cubic graphs. Zbl 1341.68308
Karpinski, Marek; Schmied, Richard
7
2015
The mixing time of Glauber dynamics for coloring regular trees. Zbl 1348.68172
Goldberg, Leslie Ann; Jerrum, Mark; Karpinski, Marek
7
2010
On the parallel complexity of Hamiltonian cycle and matching problem on dense graphs. Zbl 0782.68055
Dahlhaus, Elias; Hajnal, Péter; Karpinski, Marek
6
1993
Lower space bounds for randomized computation. Zbl 1418.68094
Freivalds, Rusins; Karpinski, Marek
6
1994
Improved approximation algorithms for the quality of service multicast tree problem. Zbl 1079.68013
Karpinski, Marek; Măndoiu, Ion I.; Olshevsky, Alexander; Zelikovsky, Alexander
6
2005
A lower bound for integer multiplication on randomized ordered read-once branching programs. Zbl 1059.68045
Ablayev, Farid; Karpinski, Marek
6
2003
Trading GRH for algebra: algorithms for factoring polynomials and related structures. Zbl 1239.68080
Ivanyos, Gábor; Karpinski, Marek; Rónyai, Lajos; Saxena, Nitin
6
2012
Tropical dominating sets in vertex-coloured graphs. Zbl 1475.68229
Anglès d’Auriac, Jean-Alexandre; Bujtás, Csilia; El Maftouhi, Hakim; Karpinski, Marek; Manoussakis, Yannis; Montero, Leandro; Narayanan, Narayanan; Rosaz, Laurent; Thapper, Johan; Tuza, Zsolt
6
2016
1.25-approximation algorithm for Steiner tree problem with distances 1 and 2. Zbl 1253.68355
Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander
6
2009
Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. Zbl 1304.68218
Karpinski, Marek; Schudy, Warren
6
2009
On randomized semi-algebraic test complexity. Zbl 0806.68045
Bürgisser, Peter; Karpinski, Marek; Lickteig, Thomas
5
1993
Algorithms for sparse rational interpolation. Zbl 0920.65004
Grigoriev, Dima Yu.; Karpinski, Marek
5
1991
On the computational hardness of testing square-freeness of sparse polynomials. Zbl 0973.11105
Karpinski, Marek; Shparlinski, Igor
5
1999
Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications. Zbl 1391.68049
Das Gupta, Bhaskar; Karpinski, Marek; Mobasheri, Nasim; Yahyanejad, Farzane
5
2018
Lower bounds on testing membership to a polyhedron by algebraic decision trees. Zbl 1345.68158
Grigoriev, Dima; Karpinski, Marek; Vorobjov, Nicolai
5
1994
Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem. Zbl 0743.68072
Dahlhaus, Elias; Karpinski, Marek
5
1992
An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3. Zbl 0764.68048
Dahlhaus, Elias; Karpinski, Marek; Kelsen, Pierre
5
1992
Approximating subdense instances of covering problems. Zbl 1268.68170
Cardinal, Jean; Karpinski, Marek; Schmied, Richard; Viehmann, Claus
5
2011
Deterministic polynomial factoring and association schemes. Zbl 1320.11116
Arora, Manuel; Ivanyos, Gábor; Karpinski, Marek; Saxena, Nitin
5
2014
Schemes for deterministic polynomial factoring. Zbl 1237.68100
Ivanyos, Gábor; Karpinski, Marek; Saxena, Nitin
4
2009
Computational complexity of sparse real algebraic function interpolation. Zbl 0801.68087
Grigoriev, D.; Karpinski, M.; Singer, M. F.
4
1993
Fast parallel algorithms for the clique separator decomposition. Zbl 0800.68623
Dahlhaus, Elias; Karpinski, Marek; Nivick, Mark B.
4
1990
A lower bound for randomized algebraic decision trees. Zbl 0922.68090
Grigoriev, Dima; Karpinski, Marek; Meyer auf der Heide, Friedhelm; Smolensky, Roman
4
1996
Compact cellular algebras and permutation groups. Zbl 0960.20001
Evdokimov, Sergei; Karpinski, Marek; Ponomarenko, Ilia
4
1999
The computational complexity of graph problems with succinct multigraph representation. Zbl 0655.05063
Karpinski, M.; Wagner, K. W.
4
1988
On the computational complexity of quantified Horn clauses. Zbl 0664.03012
Karpinski, Marek; Kleine Büning, Hans; Schmitt, Peter H.
4
1988
Stopping times, metrics and approximate counting. Zbl 1223.68075
Bordewich, Magnus; Dyer, Martin; Karpinski, Marek
4
2006
Space efficient multi-dimensional range reporting. Zbl 1248.68524
Karpinski, Marek; Nekrich, Yakov
4
2009
There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator. Zbl 0588.68026
Karpinski, Marek; Verbeek, Rutger
4
1985
Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION. Zbl 1057.68646
Berman, Piotr; Karpinski, Marek
4
2002
Simulating threshold circuits by majority circuits. Zbl 1310.94242
Goldmann, Mikael; Karpinski, Marek
4
1993
Approximation schemes for the betweenness problem in tournaments and related ranking problems. Zbl 1343.68313
Karpinski, Marek; Schudy, Warren
4
2011
Boolean circuit complexity of algebraic interpolation problems. Zbl 0717.68054
Karpinski, Marek
4
1989
An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph. Zbl 0938.68958
Dahlhaus, Elias; Karpinski, Marek
3
1994
Correctness of constructing optimal alphabetic trees revisited. Zbl 0901.68144
Karpinski, Marek; Larmore, Lawrence L.; Rytter, Wojciech
3
1997
An exponential lower bound on the size of algebraic decision trees for MAX. Zbl 0918.68032
Grigoriev, Dima; Karpinski, Marek; Yao, Andrew C.
3
1998
Improved lower bound on testing membership to a polyhedron by algebraic decision trees. Zbl 0938.68868
Grigoriev, Dima; Karpinski, Marek; Vorobjov, Nicolai
3
1995
Approximating bounded degree instances of NP-hard problems. Zbl 1003.90055
Karpinski, Marek
3
2001
Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications. Zbl 1391.68049
Das Gupta, Bhaskar; Karpinski, Marek; Mobasheri, Nasim; Yahyanejad, Farzane
5
2018
Tropical dominating sets in vertex-coloured graphs. Zbl 1391.05193
Anglès d’Auriac, J.-A.; Bujtás, Cs.; El Maftouhi, A.; Karpinski, M.; Manoussakis, Y.; Montero, L.; Narayanan, N.; Rosaz, L.; Thapper, J.; Tuza, Zs.
2
2018
A QPTAS for the base of the number of crossing-free structures on a planar point set. Zbl 1386.68202
Karpinski, Marek; Lingas, Andrzej; Sledneu, Dzmitry
2
2018
Polynomial interpolation and identity testing from high powers over finite fields. Zbl 1390.11128
Ivanyos, Gábor; Karpinski, Marek; Santha, Miklos; Saxena, Nitin; Shparlinski, Igor E.
2
2018
Tropical dominating sets in vertex-coloured graphs. Zbl 1475.68229
Anglès d’Auriac, Jean-Alexandre; Bujtás, Csilia; El Maftouhi, Hakim; Karpinski, Marek; Manoussakis, Yannis; Montero, Leandro; Narayanan, Narayanan; Rosaz, Laurent; Thapper, Johan; Tuza, Zsolt
6
2016
New inapproximability bounds for TSP. Zbl 1328.68076
Karpinski, Marek; Lampis, Michael; Schmied, Richard
24
2015
Generalized Wong sequences and their applications to Edmonds’ problems. Zbl 1320.68222
Ivanyos, Gábor; Karpinski, Marek; Qiao, Youming; Santha, Miklos
15
2015
Inapproximability of dominating set on power law graphs. Zbl 1305.05174
Gast, Mikael; Hauptmann, Mathias; Karpinski, Marek
11
2015
Approximation hardness of graphic TSP on cubic graphs. Zbl 1341.68308
Karpinski, Marek; Schmied, Richard
7
2015
Deterministic polynomial factoring and association schemes. Zbl 1320.11116
Arora, Manuel; Ivanyos, Gábor; Karpinski, Marek; Saxena, Nitin
5
2014
Approximate counting of matchings in \((3,3)\)-hypergraphs. Zbl 1416.68205
Dudek, Andrzej; Karpinski, Marek; Ruciński, Andrzej; Szymańska, Edyta
2
2014
Generalized Wong sequences and their applications to Edmonds’ problems. Zbl 1359.68328
Ivanyos, Gábor; Karpinski, Marek; Qiao, Youming; Santha, Miklos
2
2014
On the computational complexity of measuring global stability of banking networks. Zbl 1307.91197
Berman, Piotr; DasGupta, Bhaskar; Kaligounder, Lakshmi; Karpinski, Marek
1
2014
New inapproximability bounds for TSP. Zbl 1328.68075
Karpinski, Marek; Lampis, Michael; Schmied, Richard
13
2013
Approximate counting of matchings in sparse uniform hypergraphs. Zbl 1430.68450
Karpiński, Marek; Ruciński, Andrzej; Szymańska, Edyta
1
2013
Trading GRH for algebra: algorithms for factoring polynomials and related structures. Zbl 1239.68080
Ivanyos, Gábor; Karpinski, Marek; Rónyai, Lajos; Saxena, Nitin
6
2012
Approximating vertex cover in dense hypergraphs. Zbl 1252.68135
Cardinal, Jean; Karpinski, Marek; Schmied, Richard; Viehmann, Claus
2
2012
Exact and approximation algorithms for geometric and capacitated set cover problems. Zbl 1252.68347
Berman, Piotr; Karpinski, Marek; Lingas, Andrzej
2
2012
Top-\(K\) color queries for document retrieval. Zbl 1373.68197
Karpinski, Marek; Nekrich, Yakov
15
2011
Approximating subdense instances of covering problems. Zbl 1268.68170
Cardinal, Jean; Karpinski, Marek; Schmied, Richard; Viehmann, Claus
5
2011
Approximation schemes for the betweenness problem in tournaments and related ranking problems. Zbl 1343.68313
Karpinski, Marek; Schudy, Warren
4
2011
Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. Zbl 1310.68272
Karpinski, Marek; Schudy, Warren
32
2010
Deterministic polynomial time algorithms for matrix completion problems. Zbl 1209.68269
Ivanyos, Gábor; Karpinski, Marek; Saxena, Nitin
19
2010
Cycles and paths in edge-colored graphs with given degrees. Zbl 1202.05067
Abouelaoualim, A.; Das, K. Ch.; de la Vega, W. Fernandez; Karpinski, M.; Manoussakis, Y.; Martinhon, C. A.; Saad, R.
16
2010
Computational complexity of the perfect matching problem in hypergraphs with subcritical density. Zbl 1206.68147
Karpiński, Marek; Ruciński, Andrzej; Szymańska, Edyta
9
2010
The mixing time of Glauber dynamics for coloring regular trees. Zbl 1348.68172
Goldberg, Leslie Ann; Jerrum, Mark; Karpinski, Marek
7
2010
Computational complexity of the Hamiltonian cycle problem in dense hypergraphs. Zbl 1283.05155
Karpiński, Marek; Ruciński, Andrzej; Szymańska, Edyta
2
2010
Exact and approximation algorithms for geometric and capacitated set cover problems. Zbl 1286.68461
Berman, Piotr; Karpinski, Marek; Lingas, Andrzej
1
2010
1.25-approximation algorithm for Steiner tree problem with distances 1 and 2. Zbl 1253.68355
Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander
6
2009
Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. Zbl 1304.68218
Karpinski, Marek; Schudy, Warren
6
2009
Schemes for deterministic polynomial factoring. Zbl 1237.68100
Ivanyos, Gábor; Karpinski, Marek; Saxena, Nitin
4
2009
Space efficient multi-dimensional range reporting. Zbl 1248.68524
Karpinski, Marek; Nekrich, Yakov
4
2009
A fast algorithm for adaptive prefix coding. Zbl 1172.94005
Karpinski, Marek; Nekrich, Yakov
3
2009
Approximating transitive reductions for directed networks. Zbl 1253.68354
Berman, Piotr; DasGupta, Bhaskar; Karpinski, Marek
3
2009
The complexity of perfect matching problems on dense hypergraphs. Zbl 1273.68180
Karpiński, Marek; Ruciński, Andrzej; Szymańska, Edyta
3
2009
Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Zbl 1181.05061
Bordewich, Magnus; Dyer, Martin; Karpinski, Marek
10
2008
Computational complexity of some restricted instances of 3-SAT. Zbl 1111.68044
Berman, Piotr; Karpinski, Marek; Scott, Alexander D.
7
2007
Optimal trade-off for Merkle tree traversal. Zbl 1108.68047
Berman, Piotr; Karpinski, Marek; Nekrich, Yakov
2
2007
Embedding point sets into plane graphs of small dilation. Zbl 1185.68775
Ebbers-Baumann, Annette; Grüne, Ansgar; Klein, Rolf; Karpinski, Marek; Knauer, Christian; Lingas, Andrzej
2
2007
1.0957-approximation algorithm for random MAX-3SAT. Zbl 1377.68323
Fernandez de la Vega, Wenceslas; Karpinski, Marek
1
2007
\(8/7\)-approximation algorithm for \((1,2)\)-TSP. Zbl 1192.90158
Berman, Piotr; Karpinski, Marek
32
2006
TSP with bounded metrics. Zbl 1125.90066
Engebretsen, Lars; Karpinski, Marek
10
2006
Stopping times, metrics and approximate counting. Zbl 1223.68075
Bordewich, Magnus; Dyer, Martin; Karpinski, Marek
4
2006
Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. Zbl 1087.90063
Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike
17
2005
On the computational power of probabilistic and quantum branching program. Zbl 1105.68037
Ablayev, Farid; Gainutdinova, Aida; Karpinski, Marek; Moore, Cristopher; Pollett, Christopher
17
2005
Tensor decomposition and approximation schemes for constraint satisfaction problems. Zbl 1192.68920
de la Vega, W. Fernandez; Kannan, Ravi; Karpinski, Marek; Vempala, Santosh
8
2005
Improved approximation algorithms for the quality of service multicast tree problem. Zbl 1079.68013
Karpinski, Marek; Măndoiu, Ion I.; Olshevsky, Alexander; Zelikovsky, Alexander
6
2005
On the complexity of global constraint satisfaction. (Extended abstract). Zbl 1175.68194
Bazgan, Cristina; Karpinski, Marek
2
2005
Predecessor queries in constant time? Zbl 1162.68408
Karpinski, Marek; Nekrich, Yakov
1
2005
Embedding point sets into plane graphs of small dilation. Zbl 1173.68603
Ebbers-Baumann, Annette; Grüne, Ansgar; Karpinski, Marek; Klein, Rolf; Knauer, Christian; Lingas, Andrzej
1
2005
Approximation algorithms for max-bisection on low degree regular graphs. Zbl 1102.68095
Karpinski, Marek; Kowaluk, Miroslaw; Lingas, Andrzej
3
2004
Approximation schemes for metric bisection and partitioning. Zbl 1317.68276
Fernandez de la Vega, W.; Karpinski, Marek; Kenyon, Claire
3
2004
Approximation algorithms for NP-hard problems. Zbl 1078.90500
1
2004
Approximation schemes for clustering problems. Zbl 1192.68894
Fernandez de la Vega, W.; Karpinski, Marek; Kenyon, Claire; Rabani, Yuval
25
2003
Random sampling and approximation of MAX-CSPs. Zbl 1160.68537
Alon, Noga; Fernandez de la Vega, W.; Kannan, Ravi; Karpinski, Marek
18
2003
A lower bound for integer multiplication on randomized ordered read-once branching programs. Zbl 1059.68045
Ablayev, Farid; Karpinski, Marek
6
2003
Polynomial time approximation schemes for dense instances of minimum constraint satisfaction. Zbl 1023.68093
Bazgan, Cristina; Fernandez de la Vega, W.; Karpinski, Marek
1
2003
1. 375-approximation algorithm for sorting by reversals. Zbl 1019.68817
Berman, Piotr; Hannenhalli, Sridhar; Karpinski, Marek
32
2002
On the complexity of pattern matching for highly compressed two-dimensional texts. Zbl 1059.68098
Berman, Piotr; Karpinski, Marek; Larmore, Lawrence L.; Plandowski, Wojciech; Rytter, Wojciech
12
2002
Improved approximation of max-cut on graphs of bounded degree. Zbl 1050.68110
Feige, Uriel; Karpinski, Marek; Langberg, Michael
11
2002
Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. Zbl 1093.68677
Csaba, Béla; Karpinski, Marek; Krysta, Piotr
11
2002
Approximability of the minimum bisection problem: An algorithmic challenge. Zbl 1014.68115
Karpinski, Marek
11
2002
Random sampling and approximation of MAX-CSP problems. Zbl 1192.68865
Alon, Noga; Fernandez de la Vega, W.; Kannan, Ravi; Karpinski, Marek
11
2002
Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION. Zbl 1057.68646
Berman, Piotr; Karpinski, Marek
4
2002
Approximating minimum unsatisfiability of linear equations. Zbl 1254.68348
Berman, Piotr; Karpinski, Marek
3
2002
Learning by the process of elimination. Zbl 1012.68092
Freivalds, Rūsiņš; Karpinski, Marek; Smith, Carl H.; Wiehagen, Rolf
2
2002
Randomized splay trees: Theoretical and experimental results. Zbl 1052.68021
Albers, Susanne; Karpinski, Marek
1
2002
Approximation hardness of TSP with bounded metrics. Zbl 0986.90082
Engebretsen, Lars; Karpinski, Marek
13
2001
On computational power of quantum branching programs. Zbl 0999.68071
Ablayev, Farid; Gainutdinova, Aida; Karpinski, Marek
11
2001
Polynomial time approximation schemes for some dense instances of NP-hard optimization problems. Zbl 0985.68089
Karpinski, M.
9
2001
Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. Zbl 0976.68523
Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike
8
2001
A note on approximating Max-Bisection on regular graphs. Zbl 1032.68119
Feige, U.; Karpinski, M.; Langberg, M.
7
2001
Approximating bounded degree instances of NP-hard problems. Zbl 1003.90055
Karpinski, Marek
3
2001
On BPP versus \(NP\cup coNP\) for ordered read-once branching programs. Zbl 0972.68091
Ablayev, F.; Karpinski, M.; Mubarakzjanov, R.
1
2001
On-line load balancing for related machines. Zbl 0954.68050
Berman, Piotr; Charikar, Moses; Karpinski, Marek
40
2000
Polynomial time approximation of dense weighted instances of MAX-CUT. Zbl 0965.68072
Fernandez de la Vega, W.; Karpinski, M.
2
2000
Approximating volumes and integrals in o-minimal and p-minimal theories. Zbl 1003.03037
Karpinski, Marek; Macintyre, Angus
2
2000
Zero testing of \(p\)-adic and modular polynomials. Zbl 1012.11111
Karpinski, Marek; van der Poorten, Alf; Shparlinski, Igor
1
2000
Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems. Zbl 0937.68160
Arora, Sanjeev; Karger, David; Karpinski, Marek
45
1999
On a new high dimensional Weisfeiler-Lehman algorithm. Zbl 0936.05070
Evdokimov, Sergei; Karpinski, Marek; Ponomarenko, Ilia
10
1999
A generalization of Wilkie’s theorem of the complement, and an application to Pfaffian closure. Zbl 0953.03046
Karpinski, Marek; Macintyre, Angus
8
1999
On the computational hardness of testing square-freeness of sparse polynomials. Zbl 0973.11105
Karpinski, Marek; Shparlinski, Igor
5
1999
Compact cellular algebras and permutation groups. Zbl 0960.20001
Evdokimov, Sergei; Karpinski, Marek; Ponomarenko, Ilia
4
1999
On the approximation hardness of dense TSP and other path problems. Zbl 1002.68062
Fernandez de la Vega, W.; Karpinski, M.
2
1999
Quantum finite multitape automata. Zbl 0971.68088
Ambainis, Andris; Bonner, Richard; Freivalds, Rūsiņš; Golovkins, Marats; Karpinski, Marek
1
1999
An exponential lower bound for depth 3 arithmetic circuits. Zbl 1028.68069
Grigoriev, Dima; Karpinski, Marek
23
1998
Approximating dense cases of covering problems. Zbl 0896.68078
Karpinski, Marek; Zelikovsky, Alexander
22
1998
Matching and multidimensional matching in chordal and strongly chordal graphs. Zbl 0902.68146
Dahlhaus, Elias; Karpinski, Marek
19
1998
Simulating threshold circuits by majority circuits. Zbl 0912.68030
Goldmann, Mikael; Karpinski, Marek
12
1998
Fast parallel algorithms for graph matching problems. Zbl 0895.05050
Karpinski, Marek; Rytter, Wojciech
12
1998
An exponential lower bound on the size of algebraic decision trees for MAX. Zbl 0918.68032
Grigoriev, Dima; Karpinski, Marek; Yao, Andrew C.
3
1998
On the computation power of randomized branching programs. Zbl 0922.68063
Karpinski, Marek
2
1998
On BPP versus \(\text{NP}\cup \text{coNP}\) for ordered read-once branching programs. Zbl 0922.68061
Ablayev, Farid; Karpinski, Marek; Mubarakzjanov, Rustam
1
1998
Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks. Zbl 0869.68088
Karpinski, Marek; Macintyre, Angus
31
1997
Polynomial time algorithms for modules over finite dimensional algebras. Zbl 0918.16001
Chistov, Alexander; Ivanyos, Gábor; Karpinski, Marek
26
1997
New approximation algorithms for the Steiner tree problems. Zbl 0895.90171
Karpinski, Marek; Zelikovsky, Alexander
25
1997
An efficient pattern-matching algorithm for strings with short descriptions. Zbl 0874.68087
Karpinski, Marek; Rytter, Wojciech; Shinohara, Ayumi
25
1997
Counting curves and their projections. Zbl 0990.68642
von zur Gathen, Joachim; Karpinski, Marek; Shparlinski, Igor
11
1997
Correctness of constructing optimal alphabetic trees revisited. Zbl 0901.68144
Karpinski, Marek; Larmore, Lawrence L.; Rytter, Wojciech
3
1997
Approximating the volume of general Pfaffian bodies. Zbl 0884.68108
Karpinski, Marek; Macintyre, Angus
2
1997
...and 58 more Documents
all top 5

Cited by 1,741 Authors

43 Karpinski, Marek
21 Beyersdorff, Olaf
13 Qiao, Youming
12 Saurabh, Saket
11 Grigor’ev, Dmitriĭ Yur’evich
10 Blinkhorn, Joshua
10 Epstein, Leah
10 Koiran, Pascal
10 Mahajan, Meena
9 Ablaev, Farid M.
9 Chew, Leroy
9 Fomin, Fedor V.
9 Ivanyos, Gábor
9 Lingas, Andrzej
9 Lonsing, Florian
9 Monnot, Jérôme
9 Navarro, Gonzalo
9 Saha, Chandan
9 Schmied, Richard
9 Shparlinski, Igor E.
9 Thankachan, Sharma V.
9 Yakaryılmaz, Abuzer
8 Bshouty, Nader H.
8 Dias, Zanoni
8 Kayal, Neeraj
8 Khadiev, Kamil
8 Manoussakis, Yannis G.
8 Seidl, Martina
8 Sgall, Jiří
8 Zhu, Daming
7 Alon, Noga
7 Ducoffe, Guillaume
7 Inenaga, Shunsuke
7 Khadieva, Aliya
7 Nekrich, Yakov
7 Paschos, Vangelis Th.
7 Shah, Rahul
7 Slivovsky, Friedrich
7 Szeider, Stefan
7 Viehmann, Claus
7 Zehavi, Meirav
6 Biere, Armin
6 Dahlhaus, Elias
6 Elbassioni, Khaled M.
6 Gutin, Gregory Z.
6 Könemann, Jochen
6 Lokshtanov, Daniel
6 Niedermeier, Rolf
6 Saptharishi, Ramprasad
6 Takeda, Masayuki
6 Xu, Baogang
6 Yu, Xingxing
6 Zhang, Zhongzhi
5 Abu-Affash, A. Karim
5 Bannai, Hideo
5 Bazgan, Cristina
5 Cardinal, Jean
5 Carmi, Paz
5 Casel, Katrin
5 Díaz, Josep
5 Egly, Uwe
5 Feldmann, Andreas Emil
5 Gainutdinova, Aida
5 Golovach, Petr A.
5 Han, Jie
5 Hellerstein, Lisa
5 Jiang, Haitao
5 Kobourov, Stephen G.
5 Komusiewicz, Christian
5 Kumar, Mrinal
5 Lintzmayer, Carla Negri
5 Lohrey, Markus
5 Ponomarenko, Ilya Nikolaevich
5 Rojas, J. Maurice
5 Rytter, Wojciech
5 Sahneh, Faryad Darabi
5 Saxena, Nitin
5 Spence, Richard
5 Tuza, Zsolt
5 van Bevern, René
5 Vasil’ev, Aleksandr Valer’evich
5 Vygen, Jens
4 Ahmed, Reyan
4 Borozan, Valentin
4 Boyd, Sylvia C.
4 Chattopadhyay, Arkadev
4 Chen, Hubie
4 Chen, Zhizhong
4 Clementi, Andrea E. F.
4 Czumaj, Artur
4 Dósa, György
4 Evdokimov, Sergeĭ Alekseevich
4 Fernandez de la Vega, Wenceslas
4 Fernau, Henning
4 Fertin, Guillaume
4 Freivalds, Rūsiņš Mārtiņš
4 Friedrich, Tobias
4 Grigorescu, Elena
4 Guo, Jiong
4 Gupta, Arvind Kumar
...and 1,641 more Authors
all top 5

Cited in 192 Serials

119 Theoretical Computer Science
52 Discrete Applied Mathematics
51 Journal of Computer and System Sciences
43 Information Processing Letters
43 Algorithmica
33 Information and Computation
28 SIAM Journal on Computing
21 Journal of Combinatorial Optimization
17 Journal of Discrete Algorithms
16 Computational Complexity
15 SIAM Journal on Discrete Mathematics
13 Random Structures & Algorithms
13 Theory of Computing Systems
12 Journal of Symbolic Computation
12 Journal of Complexity
11 Discrete Mathematics
10 Mathematical Programming. Series A. Series B
10 Annals of Mathematics and Artificial Intelligence
9 Discrete & Computational Geometry
8 Artificial Intelligence
8 Journal of Algebra
8 Operations Research Letters
8 Journal of Automated Reasoning
7 Advances in Applied Mathematics
7 Computers & Operations Research
7 European Journal of Operational Research
7 Journal of Scheduling
7 Lobachevskii Journal of Mathematics
7 Foundations of Computational Mathematics
6 Journal of Combinatorial Theory. Series B
6 European Journal of Combinatorics
5 Journal of Pure and Applied Algebra
5 Combinatorica
5 Neural Computation
5 Computational Geometry
5 International Journal of Foundations of Computer Science
5 Quantum Information Processing
5 Algorithms
4 Automatica
4 Information Sciences
4 Graphs and Combinatorics
4 Machine Learning
4 Applicable Algebra in Engineering, Communication and Computing
4 Finite Fields and their Applications
4 The Electronic Journal of Combinatorics
4 Discrete Optimization
4 Optimization Letters
4 Logical Methods in Computer Science
3 Mathematics of Computation
3 Advances in Mathematics
3 Mathematics of Operations Research
3 Networks
3 Transactions of the American Mathematical Society
3 Systems & Control Letters
3 Neural Networks
3 Annals of Operations Research
3 Japan Journal of Industrial and Applied Mathematics
3 Discrete Mathematics and Applications
3 Linear Algebra and its Applications
3 Russian Mathematics
3 Advances in Computational Mathematics
3 Constraints
3 Journal of the ACM
3 RAIRO. Theoretical Informatics and Applications
3 ACM Journal of Experimental Algorithmics
3 ACM Transactions on Algorithms
2 Computer Physics Communications
2 Applied Mathematics and Computation
2 Duke Mathematical Journal
2 Journal of Graph Theory
2 International Journal of Computational Geometry & Applications
2 Differential Geometry and its Applications
2 Journal of Global Optimization
2 Geometric and Functional Analysis. GAFA
2 International Journal of Computer Mathematics
2 Formal Methods in System Design
2 Journal of Mathematical Sciences (New York)
2 St. Petersburg Mathematical Journal
2 Fractals
2 CEJOR. Central European Journal of Operations Research
2 RAIRO. Operations Research
2 Journal of Systems Science and Complexity
2 Journal of Satisfiability, Boolean Modeling and Computation
2 Science China. Mathematics
2 Theory of Computing
2 Computability
2 Journal of the Operations Research Society of China
1 ACM Computing Surveys
1 Communications in Mathematical Physics
1 Computer Methods in Applied Mechanics and Engineering
1 Communications on Pure and Applied Mathematics
1 International Journal of Theoretical Physics
1 Israel Journal of Mathematics
1 Journal of Computational Physics
1 Journal of the Franklin Institute
1 Journal of Mathematical Analysis and Applications
1 Letters in Mathematical Physics
1 Nuclear Physics. B
1 Reviews of Modern Physics
1 ACM Transactions on Database Systems
...and 92 more Serials
all top 5

Cited in 49 Fields

837 Computer science (68-XX)
309 Combinatorics (05-XX)
208 Operations research, mathematical programming (90-XX)
69 Mathematical logic and foundations (03-XX)
40 Information and communication theory, circuits (94-XX)
37 Number theory (11-XX)
35 Quantum theory (81-XX)
33 Linear and multilinear algebra; matrix theory (15-XX)
31 Numerical analysis (65-XX)
27 Biology and other natural sciences (92-XX)
24 Algebraic geometry (14-XX)
24 Statistics (62-XX)
22 Field theory and polynomials (12-XX)
20 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
18 Commutative algebra (13-XX)
17 Associative rings and algebras (16-XX)
17 Probability theory and stochastic processes (60-XX)
15 Order, lattices, ordered algebraic structures (06-XX)
14 Group theory and generalizations (20-XX)
14 Approximations and expansions (41-XX)
11 Convex and discrete geometry (52-XX)
9 Systems theory; control (93-XX)
7 Several complex variables and analytic spaces (32-XX)
6 Statistical mechanics, structure of matter (82-XX)
5 Measure and integration (28-XX)
4 Functional analysis (46-XX)
4 Operator theory (47-XX)
3 General algebraic systems (08-XX)
3 Functions of a complex variable (30-XX)
3 Dynamical systems and ergodic theory (37-XX)
3 Calculus of variations and optimal control; optimization (49-XX)
3 General topology (54-XX)
3 Algebraic topology (55-XX)
3 Global analysis, analysis on manifolds (58-XX)
2 History and biography (01-XX)
2 Topological groups, Lie groups (22-XX)
2 Special functions (33-XX)
2 Geometry (51-XX)
2 Mechanics of deformable solids (74-XX)
1 General and overarching topics; collections (00-XX)
1 Nonassociative rings and algebras (17-XX)
1 Ordinary differential equations (34-XX)
1 Partial differential equations (35-XX)
1 Difference and functional equations (39-XX)
1 Integral equations (45-XX)
1 Differential geometry (53-XX)
1 Manifolds and cell complexes (57-XX)
1 Classical thermodynamics, heat transfer (80-XX)
1 Mathematics education (97-XX)

Citations by Year

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.