×

zbMATH — the first resource for mathematics

Karpinski, Marek

Compute Distance To:
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
Documents Indexed: 191 Publications since 1973, including 6 Books
4 Contributions as Editor
all top 5

Co-Authors

26 single-authored
19 Grigor’ev, Dmitriĭ Yur’evich
16 Berman, Piotr
11 Fernandez de la Vega, Wenceslas
11 Lingas, Andrzej
8 Dahlhaus, Elias
8 Ivanyos, Gábor
8 Shparlinski, Igor E.
7 Nekrich, Yakov
6 Ablaev, Farid M.
6 Freivalds, Rūsiņš Mārtiņš
6 Rytter, Wojciech
6 Schmied, Richard
6 Verbeek, Rutger
6 Zelikovsky, Alexander Z.
5 Macintyre, Angus John
5 Ruciński, Andrzej
5 Saxena, Nitin
5 Szymańska, Edyta
4 Kannan, Ravindran
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 M.
2 Ambainis, Andris
2 Anglès d’Auriac, Jean-Alexandre
2 Arora, Sanjeev
2 Bürgisser, Peter
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 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 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 Bujtás, Csilia
1 Calude, Cristian S.
1 Charikar, Moses 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 Gast, Mikael
1 Gobleja, Dace
1 Goldberg, Leslie Ann
1 Golovkins, Marats
1 Grabmeier, Johannes
1 Habasinski, Zdzislaw
1 Hajnal, Péter
1 Hancock, Thomas R.
1 Hannenhalli, Sridhar
1 Hauptmann, Mathias
...and 32 more Co-Authors

Publications by Year

Citations contained in zbMATH Open

148 Publications have been cited 1,109 times in 898 Documents Cited by Year
Resolution for quantified Boolean formulas. Zbl 0828.68045
Kleine Büning, Hans; Karpinski, Marek; Flögel, Andreas
66
1995
Learning read-once formulas with queries. Zbl 0764.68139
Angluin, Dana; Hellerstein, Lisa; Karpinski, Marek
49
1993
Polynomial time approximation schemes for dense instances of NP-hard problems. Zbl 0968.68534
Arora, Sanjeev; Karger, David; Karpinski, Marek
42
1995
Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems. Zbl 0937.68160
Arora, Sanjeev; Karger, David; Karpinski, Marek
35
1999
On-line load balancing for related machines. Zbl 0954.68050
Berman, Piotr; Charikar, Moses; Karpinski, Marek
33
2000
\(8/7\)-approximation algorithm for \((1,2)\)-TSP. Zbl 1192.90158
Berman, Piotr; Karpinski, Marek
28
2006
Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. Zbl 1310.68272
Karpinski, Marek; Schudy, Warren
28
2010
Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks. Zbl 0869.68088
Karpinski, Marek; Macintyre, Angus
27
1997
Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. Zbl 0711.68059
Grigoriev, Dima Yu.; Karpinski, Marek; Singer, Michael F.
24
1990
1. 375-approximation algorithm for sorting by reversals. Zbl 1019.68817
Berman, Piotr; Hannenhalli, Sridhar; Karpinski, Marek
23
2002
An efficient pattern-matching algorithm for strings with short descriptions. Zbl 0874.68087
Karpinski, Marek; Rytter, Wojciech; Shinohara, Ayumi
22
1997
Approximation schemes for clustering problems. Zbl 1192.68894
Fernandez de la Vega, W.; Karpinski, Marek; Kenyon Claire; Rabani, Yuval
21
2003
New approximation algorithms for the Steiner tree problems. Zbl 0895.90171
Karpinski, Marek; Zelikovsky, Alexander
20
1997
Approximating dense cases of covering problems. Zbl 0896.68078
Karpinski, Marek; Zelikovsky, Alexander
18
1998
Polynomial time algorithms for modules over finite dimensional algebras. Zbl 0918.16001
Chistov, Alexander; Ivanyos, Gábor; Karpinski, Marek
17
1997
On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields. Zbl 0737.65002
Clausen, Michael; Dress, Andreas; Grabmeier, Johannes; Karpinski, Marek
16
1991
An exponential lower bound for depth 3 arithmetic circuits. Zbl 1028.68069
Grigoriev, Dima; Karpinski, Marek
16
1998
Random sampling and approximation of MAX-CSPs. Zbl 1160.68537
Alon, Noga; Fernandez de la Vega, W.; Kannan, Ravi; Karpinski, Marek
16
2003
Polynomial bounds for VC dimension of sigmoidal neural networks. Zbl 0978.68562
Karpinski, Marek; Macintyre, Angus
15
1995
Matching and multidimensional matching in chordal and strongly chordal graphs. Zbl 0902.68146
Dahlhaus, Elias; Karpinski, Marek
15
1998
Top-\(K\) color queries for document retrieval. Zbl 1373.68197
Karpinski, Marek; Nekrich, Yakov
14
2011
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.
14
2010
Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. Zbl 1087.90063
Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike
14
2005
Deterministic polynomial time algorithms for matrix completion problems. Zbl 1209.68269
Ivanyos, Gábor; Karpinski, Marek; Saxena, Nitin
13
2010
New inapproximability bounds for TSP. Zbl 1328.68076
Karpinski, Marek; Lampis, Michael; Schmied, Richard
13
2015
Approximation hardness of TSP with bounded metrics. Zbl 0986.90082
Engebretsen, Lars; Karpinski, Marek
12
2001
On the power of randomized branching programs. Zbl 1046.68531
Ablayev, Farid; Karpinski, Marek
11
1996
On the computational power of probabilistic and quantum branching program. Zbl 1105.68037
Ablayev, Farid; Gainutdinova, Aida; Karpinski, Marek; Moore, Cristopher; Pollett, Christopher
11
2005
Random sampling and approximation of MAX-CSP problems. Zbl 1192.68865
Alon, Noga; Fernandez de la Vega, W.; Kannan, Ravi; Karpinski, Marek
10
2002
On real Turing machines that toss coins. Zbl 0938.68648
Cucker, Felipe; Karpinski, Marek; Koiran, Pascal; Lickteig, Thomas; Werther, Kai
10
1995
Improved approximation of max-cut on graphs of bounded degree. Zbl 1050.68110
Feige, Uriel; Karpinski, Marek; Langberg, Michael
10
2002
A zero-test and an interpolation algorithm for the shifted sparse polynomials. Zbl 0809.68072
Grigoriev, Dima; Karpinski, Marek
10
1993
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
10
2002
Approximability of the minimum bisection problem: An algorithmic challenge. Zbl 1014.68115
Karpinski, Marek
10
2002
Counting curves and their projections. Zbl 0990.68642
von zur Gathen, Joachim; Karpinski, Marek; Shparlinski, Igor
10
1997
New inapproximability bounds for TSP. Zbl 1328.68075
Karpinski, Marek; Lampis, Michael; Schmied, Richard
10
2013
On a new high dimensional Weisfeiler-Lehman algorithm. Zbl 0936.05070
Evdokimov, Sergei; Karpinski, Marek; Ponomarenko, Ilia
9
1999
Simulating threshold circuits by majority circuits. Zbl 0912.68030
Goldmann, Mikael; Karpinski, Marek
9
1998
Computational complexity of sparse rational interpolation. Zbl 0802.68060
Grigoriev, Dima; Karpinski, Marek; Singer, Michael F.
9
1994
Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. Zbl 1093.68677
Csaba, Béla; Karpinski, Marek; Krysta, Piotr
9
2002
On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes. Zbl 0631.68047
Karpinski, Marek; Verbeek, Rutger
9
1987
Subtree isomorphism is NC reducible to bipartite perfect matching. Zbl 0664.68072
Lingas, Andrzej; Karpinski, Marek
9
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
Fast parallel algorithms for graph matching problems. Zbl 0895.05050
Karpinski, Marek; Rytter, Wojciech
8
1998
Polynomial time approximation schemes for some dense instances of NP-hard optimization problems. Zbl 0985.68089
Karpinski, M.
8
2001
VC dimension and uniform learnability of sparse polynomials and rational functions. Zbl 0799.68158
Karpinski, Marek; Werther, Thorsten
8
1993
On computational power of quantum branching programs. Zbl 0999.68071
Ablayev, Farid; Gainutdinova, Aida; Karpinski, Marek
8
2001
Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Zbl 1181.05061
Bordewich, Magnus; Dyer, Martin; Karpinski, Marek
8
2008
Generalized Wong sequences and their applications to Edmonds’ problems. Zbl 1320.68222
Ivanyos, Gábor; Karpinski, Marek; Qiao, Youming; Santha, Miklos
8
2015
Inapproximability of dominating set on power law graphs. Zbl 1305.05174
Gast, Mikael; Hauptmann, Mathias; Karpinski, Marek
8
2015
Computational complexity of the perfect matching problem in hypergraphs with subcritical density. Zbl 1206.68147
Karpiński, Marek; Ruciński, Andrzej; Szymańska, Edyta
7
2010
Learning read-once formulas using membership queries. Zbl 0747.68046
Hellerstein, Lisa; Karpinski, Marek
7
1989
A generalization of Wilkie’s theorem of the complement, and an application to Pfaffian closure. Zbl 0953.03046
Karpinski, Marek; Macintyre, Angus
7
1999
On some approximation problems concerning sparse polynomials over finite fields. Zbl 0871.11086
Karpinski, Marek; Shparlinski, Igor
7
1996
TSP with bounded metrics. Zbl 1125.90066
Engebretsen, Lars; Karpinski, Marek
7
2006
The mixing time of Glauber dynamics for coloring regular trees. Zbl 1348.68172
Goldberg, Leslie Ann; Jerrum, Mark; Karpinski, Marek
6
2010
The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators. Zbl 0785.12004
Grigoriev, Dima Yu.; Karpinski, Marek; Singer, Michael F.
6
1991
Approximating the number of zeroes of a \(GF[2]\) polynomial. Zbl 0769.11047
Karpinski, Marek; Luby, Michael
6
1993
Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. Zbl 0976.68523
Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike
6
2001
A note on approximating Max-Bisection on regular graphs. Zbl 1032.68119
Feige, U.; Karpinski, M.; Langberg, M.
6
2001
A fast parallel algorithm for computing all maximal cliques in a graph and the related problems. Zbl 0656.68070
Dahlhaus, Elias; Karpinski, Marek
6
1988
Computational complexity of some restricted instances of 3-SAT. Zbl 1111.68044
Berman, Piotr; Karpinski, Marek; Scott, Alexander D.
6
2007
A lower bound for integer multiplication on randomized ordered read-once branching programs. Zbl 1059.68045
Ablayev, Farid; Karpinski, Marek
6
2003
Lower bounds on testing membership to a polyhedron by algebraic decision trees. Zbl 1345.68158
Grigoriev, Dima; Karpinski, Marek; Vorobjov, Nicolai
5
1994
Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. Zbl 1304.68218
Karpinski, Marek; Schudy, Warren
5
2009
Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem. Zbl 0743.68072
Dahlhaus, Elias; Karpinski, Marek
5
1992
On the parallel complexity of Hamiltonian cycle and matching problem on dense graphs. Zbl 0782.68055
Dahlhaus, Elias; Hajnal, Péter; Karpinski, Marek
5
1993
On randomized semi-algebraic test complexity. Zbl 0806.68045
Bürgisser, Peter; Karpinski, Marek; Lickteig, Thomas
5
1993
Approximating subdense instances of covering problems. Zbl 1268.68170
Cardinal, Jean; Karpinski, Marek; Schmied, Richard; Viehmann, Claus
5
2011
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
4
2016
Algorithms for sparse rational interpolation. Zbl 0920.65004
Grigoriev, Dima Yu.; Karpinski, Marek
4
1991
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
The computational complexity of graph problems with succinct multigraph representation. Zbl 0655.05063
Karpinski, M.; Wagner, K. W.
4
1988
Approximation hardness of bounded degree MIN-CSP and MIN-BISECTION. Zbl 1057.68646
Berman, Piotr; Karpinski, Marek
4
2002
Boolean circuit complexity of algebraic interpolation problems. Zbl 0717.68054
Karpinski, Marek
4
1989
Trading GRH for algebra: algorithms for factoring polynomials and related structures. Zbl 1239.68080
Ivanyos, Gábor; Karpinski, Marek; Rónyai, Lajos; Saxena, Nitin
4
2012
1.25-approximation algorithm for Steiner tree problem with distances 1 and 2. Zbl 1253.68355
Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander
4
2009
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
3
1992
Compact cellular algebras and permutation groups. Zbl 0960.20001
Evdokimov, Sergei; Karpinski, Marek; Ponomarenko, Ilia
3
1999
On the computational hardness of testing square-freeness of sparse polynomials. Zbl 0973.11105
Karpinski, Marek; Shparlinski, Igor
3
1999
Approximation algorithms for max-bisection on low degree regular graphs. Zbl 1102.68095
Karpinski, Marek; Kowaluk, Miroslaw; Lingas, Andrzej
3
2004
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
3
2018
There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator. Zbl 0588.68026
Karpinski, Marek; Verbeek, Rutger
3
1985
Co-learnability and FIN-identifiability of enumerable classes of total recursive functions. Zbl 1044.68641
Freivalds, Rūsiņš; Gobleja, Dace; Karpinski, Marek; Smith, Carl H.
3
1994
Stopping times, metrics and approximate counting. Zbl 1223.68075
Bordewich, Magnus; Dyer, Martin; Karpinski, Marek
3
2006
Simulating threshold circuits by majority circuits. Zbl 1310.94242
Goldmann, Mikael; Karpinski, Marek
3
1993
Counting curves and their projections. Zbl 1310.68263
von zur Gathen, Joachim; Karpinski, Marek; Shparlinski, Igor
3
1993
Approximation schemes for metric bisection and partitioning. Zbl 1317.68276
Fernandez de la Vega, W.; Karpinski, Marek; Kenyon, Claire
3
2004
The complexity of perfect matching problems on dense hypergraphs. Zbl 1273.68180
Karpiński, Marek; Ruciński, Andrzej; Szymańska, Edyta
3
2009
Deterministic polynomial factoring and association schemes. Zbl 1320.11116
Arora, Manuel; Ivanyos, Gábor; Karpinski, Marek; Saxena, Nitin
3
2014
Schemes for deterministic polynomial factoring. Zbl 1237.68100
Ivanyos, Gábor; Karpinski, Marek; Saxena, Nitin
3
2009
Approximation schemes for the betweenness problem in tournaments and related ranking problems. Zbl 1343.68313
Karpinski, Marek; Schudy, Warren
3
2011
Approximating vertex cover in dense hypergraphs. Zbl 1252.68135
Cardinal, Jean; Karpinski, Marek; Schmied, Richard; Viehmann, Claus
2
2012
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 computation power of randomized branching programs. Zbl 0922.68063
Karpinski, Marek
2
1998
Improved lower bound on testing membership to a polyhedron by algebraic decision trees. Zbl 0938.68868
Grigoriev, Dima; Karpinski, Marek; Vorobjov, Nicolai
2
1995
Polynomial time approximation of dense weighted instances of MAX-CUT. Zbl 0965.68072
Fernandez de la Vega, W.; Karpinski, M.
2
2000
Approximating the volume of general Pfaffian bodies. Zbl 0884.68108
Karpinski, Marek; Macintyre, Angus
2
1997
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
3
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
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
1
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
4
2016
New inapproximability bounds for TSP. Zbl 1328.68076
Karpinski, Marek; Lampis, Michael; Schmied, Richard
13
2015
Generalized Wong sequences and their applications to Edmonds’ problems. Zbl 1320.68222
Ivanyos, Gábor; Karpinski, Marek; Qiao, Youming; Santha, Miklos
8
2015
Inapproximability of dominating set on power law graphs. Zbl 1305.05174
Gast, Mikael; Hauptmann, Mathias; Karpinski, Marek
8
2015
Approximation hardness of graphic TSP on cubic graphs. Zbl 1341.68308
Karpinski, Marek; Schmied, Richard
2
2015
Deterministic polynomial factoring and association schemes. Zbl 1320.11116
Arora, Manuel; Ivanyos, Gábor; Karpinski, Marek; Saxena, Nitin
3
2014
Generalized Wong sequences and their applications to Edmonds’ problems. Zbl 1359.68328
Ivanyos, Gábor; Karpinski, Marek; Qiao, Youming; Santha, Miklos
2
2014
Approximate counting of matchings in \((3,3)\)-hypergraphs. Zbl 1416.68205
Dudek, Andrzej; Karpinski, Marek; Ruciński, Andrzej; Szymańska, Edyta
1
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
10
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
4
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
1
2012
Top-\(K\) color queries for document retrieval. Zbl 1373.68197
Karpinski, Marek; Nekrich, Yakov
14
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
3
2011
Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. Zbl 1310.68272
Karpinski, Marek; Schudy, Warren
28
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.
14
2010
Deterministic polynomial time algorithms for matrix completion problems. Zbl 1209.68269
Ivanyos, Gábor; Karpinski, Marek; Saxena, Nitin
13
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
7
2010
The mixing time of Glauber dynamics for coloring regular trees. Zbl 1348.68172
Goldberg, Leslie Ann; Jerrum, Mark; Karpinski, Marek
6
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
Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. Zbl 1304.68218
Karpinski, Marek; Schudy, Warren
5
2009
1.25-approximation algorithm for Steiner tree problem with distances 1 and 2. Zbl 1253.68355
Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander
4
2009
The complexity of perfect matching problems on dense hypergraphs. Zbl 1273.68180
Karpiński, Marek; Ruciński, Andrzej; Szymańska, Edyta
3
2009
Schemes for deterministic polynomial factoring. Zbl 1237.68100
Ivanyos, Gábor; Karpinski, Marek; Saxena, Nitin
3
2009
Space efficient multi-dimensional range reporting. Zbl 1248.68524
Karpinski, Marek; Nekrich, Yakov
2
2009
A fast algorithm for adaptive prefix coding. Zbl 1172.94005
Karpinski, Marek; Nekrich, Yakov
2
2009
Approximating transitive reductions for directed networks. Zbl 1253.68354
Berman, Piotr; DasGupta, Bhaskar; Karpinski, Marek
2
2009
Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Zbl 1181.05061
Bordewich, Magnus; Dyer, Martin; Karpinski, Marek
8
2008
Computational complexity of some restricted instances of 3-SAT. Zbl 1111.68044
Berman, Piotr; Karpinski, Marek; Scott, Alexander D.
6
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
Optimal trade-off for Merkle tree traversal. Zbl 1108.68047
Berman, Piotr; Karpinski, Marek; Nekrich, Yakov
2
2007
\(8/7\)-approximation algorithm for \((1,2)\)-TSP. Zbl 1192.90158
Berman, Piotr; Karpinski, Marek
28
2006
TSP with bounded metrics. Zbl 1125.90066
Engebretsen, Lars; Karpinski, Marek
7
2006
Stopping times, metrics and approximate counting. Zbl 1223.68075
Bordewich, Magnus; Dyer, Martin; Karpinski, Marek
3
2006
Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. Zbl 1087.90063
Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike
14
2005
On the computational power of probabilistic and quantum branching program. Zbl 1105.68037
Ablayev, Farid; Gainutdinova, Aida; Karpinski, Marek; Moore, Cristopher; Pollett, Christopher
11
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
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
On the complexity of global constraint satisfaction. (Extended abstract). Zbl 1175.68194
Bazgan, Cristina; Karpinski, Marek
1
2005
Predecessor queries in constant time? Zbl 1162.68408
Karpinski, Marek; Nekrich, Yakov
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 schemes for clustering problems. Zbl 1192.68894
Fernandez de la Vega, W.; Karpinski, Marek; Kenyon Claire; Rabani, Yuval
21
2003
Random sampling and approximation of MAX-CSPs. Zbl 1160.68537
Alon, Noga; Fernandez de la Vega, W.; Kannan, Ravi; Karpinski, Marek
16
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
23
2002
Random sampling and approximation of MAX-CSP problems. Zbl 1192.68865
Alon, Noga; Fernandez de la Vega, W.; Kannan, Ravi; Karpinski, Marek
10
2002
Improved approximation of max-cut on graphs of bounded degree. Zbl 1050.68110
Feige, Uriel; Karpinski, Marek; Langberg, Michael
10
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
10
2002
Approximability of the minimum bisection problem: An algorithmic challenge. Zbl 1014.68115
Karpinski, Marek
10
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
9
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
2
2002
Learning by the process of elimination. Zbl 1012.68092
Freivalds, Rūsiņš; Karpinski, Marek; Smith, Carl H.; Wiehagen, Rolf
1
2002
Approximation hardness of TSP with bounded metrics. Zbl 0986.90082
Engebretsen, Lars; Karpinski, Marek
12
2001
Polynomial time approximation schemes for some dense instances of NP-hard optimization problems. Zbl 0985.68089
Karpinski, M.
8
2001
On computational power of quantum branching programs. Zbl 0999.68071
Ablayev, Farid; Gainutdinova, Aida; Karpinski, Marek
8
2001
Polynomial time approximation schemes for MAX-BISECTION on planar and geometric graphs. Zbl 0976.68523
Jansen, Klaus; Karpinski, Marek; Lingas, Andrzej; Seidel, Eike
6
2001
A note on approximating Max-Bisection on regular graphs. Zbl 1032.68119
Feige, U.; Karpinski, M.; Langberg, M.
6
2001
Approximating bounded degree instances of NP-hard problems. Zbl 1003.90055
Karpinski, Marek
2
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
33
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
Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems. Zbl 0937.68160
Arora, Sanjeev; Karger, David; Karpinski, Marek
35
1999
On a new high dimensional Weisfeiler-Lehman algorithm. Zbl 0936.05070
Evdokimov, Sergei; Karpinski, Marek; Ponomarenko, Ilia
9
1999
A generalization of Wilkie’s theorem of the complement, and an application to Pfaffian closure. Zbl 0953.03046
Karpinski, Marek; Macintyre, Angus
7
1999
Compact cellular algebras and permutation groups. Zbl 0960.20001
Evdokimov, Sergei; Karpinski, Marek; Ponomarenko, Ilia
3
1999
On the computational hardness of testing square-freeness of sparse polynomials. Zbl 0973.11105
Karpinski, Marek; Shparlinski, Igor
3
1999
Quantum finite multitape automata. Zbl 0971.68088
Ambainis, Andris; Bonner, Richard; Freivalds, Rūsiņš; Golovkins, Marats; Karpinski, Marek
1
1999
Approximating dense cases of covering problems. Zbl 0896.68078
Karpinski, Marek; Zelikovsky, Alexander
18
1998
An exponential lower bound for depth 3 arithmetic circuits. Zbl 1028.68069
Grigoriev, Dima; Karpinski, Marek
16
1998
Matching and multidimensional matching in chordal and strongly chordal graphs. Zbl 0902.68146
Dahlhaus, Elias; Karpinski, Marek
15
1998
Simulating threshold circuits by majority circuits. Zbl 0912.68030
Goldmann, Mikael; Karpinski, Marek
9
1998
Fast parallel algorithms for graph matching problems. Zbl 0895.05050
Karpinski, Marek; Rytter, Wojciech
8
1998
On the computation power of randomized branching programs. Zbl 0922.68063
Karpinski, Marek
2
1998
An exponential lower bound on the size of algebraic decision trees for MAX. Zbl 0918.68032
Grigoriev, Dima; Karpinski, Marek; Yao, Andrew C.
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
27
1997
An efficient pattern-matching algorithm for strings with short descriptions. Zbl 0874.68087
Karpinski, Marek; Rytter, Wojciech; Shinohara, Ayumi
22
1997
New approximation algorithms for the Steiner tree problems. Zbl 0895.90171
Karpinski, Marek; Zelikovsky, Alexander
20
1997
Polynomial time algorithms for modules over finite dimensional algebras. Zbl 0918.16001
Chistov, Alexander; Ivanyos, Gábor; Karpinski, Marek
17
1997
Counting curves and their projections. Zbl 0990.68642
von zur Gathen, Joachim; Karpinski, Marek; Shparlinski, Igor
10
1997
Approximating the volume of general Pfaffian bodies. Zbl 0884.68108
Karpinski, Marek; Macintyre, Angus
2
1997
Correctness of constructing optimal alphabetic trees revisited. Zbl 0901.68144
Karpinski, Marek; Larmore, Lawrence L.; Rytter, Wojciech
2
1997
Effects of Kolmogorov complexity present in inductive inference as well. Zbl 0885.03040
Ambainis, Andris; Apsītis, Kalvis; Calude, Cristian; Freivalds, Rūsiņš; Karpinski, Marek; Larfeldt, Tomas; Sala, Iveta; Smotrovs, Juris
1
1997
A lower bound for randomized algebraic decision trees. Zbl 0895.68049
Grigoriev, Dima; Karpinski, Marek; Meyer auf der Heide, Friedhelm; Smolensky, Roman
1
1997
Randomization and the computational power of analytic and algebraic decision trees. Zbl 0895.68050
Grigoriev, Dima; Karpinski, Marek; Smolensky, Roman
1
1997
Lower bound on testing membership to a polyhedron by algebraic decision and computation trees. Zbl 0871.68176
Grigoriev, D.; Karpinski, M.; Vorobjov, N.
1
1997
On the power of randomized branching programs. Zbl 1046.68531
Ablayev, Farid; Karpinski, Marek
11
1996
On some approximation problems concerning sparse polynomials over finite fields. Zbl 0871.11086
Karpinski, Marek; Shparlinski, Igor
7
1996
A lower bound for randomized algebraic decision trees. Zbl 0922.68090
Grigoriev, Dima; Karpinski, Marek; Meyer auf der Heide, Friedhelm; Smolensky, Roman
4
1996
...and 48 more Documents
all top 5

Cited by 1,449 Authors

42 Karpinski, Marek
13 Beyersdorff, Olaf
11 Grigor’ev, Dmitriĭ Yur’evich
10 Koiran, Pascal
9 Epstein, Leah
9 Ivanyos, Gábor
9 Lonsing, Florian
9 Monnot, Jérôme
9 Qiao, Youming
9 Schmied, Richard
8 Fomin, Fedor V.
8 Manoussakis, Yannis G.
8 Saurabh, Saket
8 Sgall, Jiří
8 Shparlinski, Igor E.
7 Ablaev, Farid M.
7 Bshouty, Nader H.
7 Mahajan, Meena
7 Navarro, Gonzalo
7 Paschos, Vangelis Th.
7 Szeider, Stefan
7 Thankachan, Sharma V.
7 Viehmann, Claus
6 Alon, Noga M.
6 Biere, Armin
6 Blinkhorn, Joshua
6 Elbassioni, Khaled M.
6 Gutin, Gregory Z.
6 Könemann, Jochen
6 Lingas, Andrzej
6 Niedermeier, Rolf
6 Seidl, Martina
6 Xu, Baogang
6 Zhu, Daming
5 Abu-Affash, A. Karim
5 Bazgan, Cristina
5 Chew, Leroy
5 Dahlhaus, Elias
5 Dias, Zanoni
5 Díaz, Josep
5 Egly, Uwe
5 Feldmann, Andreas Emil
5 Hellerstein, Lisa
5 Kayal, Neeraj
5 Komusiewicz, Christian
5 Lokshtanov, Daniel
5 Nekrich, Yakov
5 Ponomarenko, Ilya Nikolaevich
5 Saha, Chandan
5 Saptharishi, Ramprasad
5 Shah, Rahul
5 Tuza, Zsolt
5 Yu, Xingxing
4 Borozan, Valentin
4 Boyd, Sylvia C.
4 Carmi, Paz
4 Chen, Zhizhong
4 Czumaj, Artur
4 Dósa, György
4 Ducoffe, Guillaume
4 Evdokimov, Sergeĭ Alekseevich
4 Fernandez de la Vega, Wenceslas
4 Fernau, Henning
4 Fertin, Guillaume
4 Freivalds, Rūsiņš Mārtiņš
4 Gainutdinova, Aida
4 Golovach, Petr A.
4 Hamel, Sylvie
4 Hinde, Luke
4 Inenaga, Shunsuke
4 Inoue, Katsushi
4 Ito, Akira
4 Janota, Mikoláš
4 Jiang, Haitao
4 Khadiev, Kamil
4 Kleine Büning, Hans
4 Kumar, Mrinal
4 Lee, Wen-shin
4 Mertzios, George B.
4 Milis, Ioannis
4 Montero, Leandro P.
4 Rojas, J. Maurice
4 Rytter, Wojciech
4 Saxena, Nitin
4 Schmidt-Schauß, Manfred
4 Schmitt, Michael
4 Serna, Maria José
4 Shapira, Asaf
4 Slivovsky, Friedrich
4 Sohler, Christian
4 Subramani, Krishnan
4 Takeda, Masayuki
4 Toulouse, Sophie
4 van Bevern, René
4 Wang, Lusheng
4 Wang, Yue
4 Yakaryılmaz, Abuzer
4 Yeo, Anders
4 Zhang, Zhongzhi
3 Águeda, Raquel
...and 1,349 more Authors
all top 5

Cited in 165 Serials

112 Theoretical Computer Science
52 Discrete Applied Mathematics
48 Journal of Computer and System Sciences
39 Information Processing Letters
37 Algorithmica
29 Information and Computation
23 SIAM Journal on Computing
19 Journal of Combinatorial Optimization
17 Journal of Discrete Algorithms
16 Computational Complexity
12 Journal of Symbolic Computation
12 Theory of Computing Systems
11 Discrete Mathematics
11 Journal of Complexity
10 SIAM Journal on Discrete Mathematics
10 Mathematical Programming. Series A. Series B
9 Discrete & Computational Geometry
9 Random Structures & Algorithms
9 Annals of Mathematics and Artificial Intelligence
8 Artificial Intelligence
7 Operations Research Letters
7 Journal of Automated Reasoning
7 European Journal of Operational Research
6 Journal of Algebra
6 European Journal of Combinatorics
6 Advances in Applied Mathematics
6 Foundations of Computational Mathematics
5 Journal of Combinatorial Theory. Series B
5 Combinatorica
5 Computers & Operations Research
5 Neural Computation
5 Journal of Scheduling
5 Lobachevskii Journal of Mathematics
5 Algorithms
4 Automatica
4 Information Sciences
4 Journal of Pure and Applied Algebra
4 Machine Learning
4 Computational Geometry
4 International Journal of Foundations of Computer Science
4 Applicable Algebra in Engineering, Communication and Computing
4 Discrete Optimization
3 Transactions of the American Mathematical Society
3 Systems & Control Letters
3 Graphs and Combinatorics
3 Neural Networks
3 Japan Journal of Industrial and Applied Mathematics
3 Discrete Mathematics and Applications
3 Linear Algebra and its Applications
3 Russian Mathematics
3 Finite Fields and their Applications
3 The Electronic Journal of Combinatorics
3 Advances in Computational Mathematics
3 RAIRO. Theoretical Informatics and Applications
3 Quantum Information Processing
3 Optimization Letters
2 Mathematics of Computation
2 Advances in Mathematics
2 Applied Mathematics and Computation
2 Duke Mathematical Journal
2 Journal of Graph Theory
2 Mathematics of Operations Research
2 Annals of Operations Research
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 Constraints
2 Journal of the ACM
2 CEJOR. Central European Journal of Operations Research
2 RAIRO. Operations Research
2 Journal of Systems Science and Complexity
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 Journal of Computational Physics
1 Journal of the Franklin Institute
1 Journal of Mathematical Analysis and Applications
1 Letters in Mathematical Physics
1 Reviews of Modern Physics
1 ACM Transactions on Database Systems
1 Algebra Universalis
1 The Annals of Statistics
1 Annales Polonici Mathematici
1 Illinois Journal of Mathematics
1 Journal of Approximation Theory
1 Journal of Combinatorial Theory. Series A
1 Journal of Computational and Applied Mathematics
1 Journal of Number Theory
1 Journal of Soviet Mathematics
1 The Journal of Symbolic Logic
1 Memoirs of the American Mathematical Society
1 Nagoya Mathematical Journal
...and 65 more Serials
all top 5

Cited in 44 Fields

648 Computer science (68-XX)
253 Combinatorics (05-XX)
172 Operations research, mathematical programming (90-XX)
54 Mathematical logic and foundations (03-XX)
31 Information and communication theory, circuits (94-XX)
29 Number theory (11-XX)
27 Numerical analysis (65-XX)
25 Linear and multilinear algebra; matrix theory (15-XX)
22 Quantum theory (81-XX)
21 Statistics (62-XX)
21 Biology and other natural sciences (92-XX)
19 Field theory and polynomials (12-XX)
18 Algebraic geometry (14-XX)
17 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
12 Commutative algebra (13-XX)
12 Associative rings and algebras (16-XX)
12 Approximations and expansions (41-XX)
11 Probability theory and stochastic processes (60-XX)
10 Order, lattices, ordered algebraic structures (06-XX)
10 Convex and discrete geometry (52-XX)
9 Systems theory; control (93-XX)
8 Group theory and generalizations (20-XX)
4 Several complex variables and analytic spaces (32-XX)
4 Statistical mechanics, structure of matter (82-XX)
3 Measure and integration (28-XX)
3 Dynamical systems and ergodic theory (37-XX)
3 Functional analysis (46-XX)
3 Calculus of variations and optimal control; optimization (49-XX)
3 Algebraic topology (55-XX)
2 Operator theory (47-XX)
2 Geometry (51-XX)
2 Global analysis, analysis on manifolds (58-XX)
2 Mechanics of deformable solids (74-XX)
1 General and overarching topics; collections (00-XX)
1 History and biography (01-XX)
1 General algebraic systems (08-XX)
1 Topological groups, Lie groups (22-XX)
1 Special functions (33-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 General topology (54-XX)
1 Manifolds and cell complexes (57-XX)

Citations by Year

Wikidata Timeline

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