- CSB - MetaPress - Google - Bing - Yahoo
 | 2013 | |
|---|---|---|
| j83 |      | Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu: Optimal cuts and partitions in tree metrics in polynomial time. Inf. Process. Lett. 113(12): 447-451 (2013) |
| c99 | | Edyta Szymanska, Marek Karpinski, Andrzej Rucinski: Approximate Counting of Matchings in Sparse Uniform Hypergraphs. ANALCO 2013: 72-79 |
| i106 | | Marek Karpinski, Michael Lampis, Richard Schmied: New Inapproximability Bounds for TSP. CoRR abs/1303.6437 (2013) |
| i105 | | Marek Karpinski, Richard Schmied: Approximation Hardness of Graphic TSP on Cubic Graphs. CoRR abs/1304.6800 (2013) |
| i104 | | Marek Karpinski, Michael Lampis, Richard Schmied: New Inapproximability Bounds for TSP. Electronic Colloquium on Computational Complexity (ECCC) 20: 45 (2013) |
| i103 | | Marek Karpinski, Richard Schmied: Approximation Hardness of Graphic TSP on Cubic Graphs. Electronic Colloquium on Computational Complexity (ECCC) 20: 66 (2013) |
| 2012 | ||
| j82 | | Piotr Berman, Marek Karpinski, Andrzej Lingas: Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. Algorithmica 64(2): 295-310 (2012) |
| j81 | | Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann: Approximating vertex cover in dense hypergraphs. J. Discrete Algorithms 13: 67-77 (2012) |
| j80 | | Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena: Trading GRH for algebra: Algorithms for factoring polynomials and related structures. Math. Comput. 81(277) (2012) |
| i102 | | Marek Karpinski, Richard Schmied: On Approximation Lower Bounds for TSP with Bounded Metrics. CoRR abs/1201.5821 (2012) |
| i101 | | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska: Approximate Counting of Matchings in Sparse Hypergraphs. CoRR abs/1202.5885 (2012) |
| i100 | | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska: Approximate Counting of Matchings in Sparse Uniform Hypergraphs. CoRR abs/1204.5335 (2012) |
| i99 | | Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Deterministic Polynomial Factoring and Association Schemes. CoRR abs/1205.5653 (2012) |
| i98 | | Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu: Optimal Cuts and Bisections on the Real Line in Polynomial Time. CoRR abs/1207.0933 (2012) |
| i97 | | Mikael Gast, Mathias Hauptmann, Marek Karpinski: Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations. CoRR abs/1210.2698 (2012) |
| i96 | | Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu: Optimal Cuts and Partitions in Tree Metrics in Polynomial Time. CoRR abs/1212.3471 (2012) |
| i95 | | Mikael Gast, Mathias Hauptmann, Marek Karpinski: Inapproximability of Dominating Set in Power Law Graphs. CoRR abs/1212.3517 (2012) |
| i94 | | Marek Karpinski, Richard Schmied: On Approximation Lower Bounds for TSP with Bounded Metrics. Electronic Colloquium on Computational Complexity (ECCC) 19: 8 (2012) |
| i93 | | Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Deterministic Polynomial Factoring and Association Schemes. Electronic Colloquium on Computational Complexity (ECCC) 19: 68 (2012) |
| i92 | | Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu: Optimal Cuts and Partitions in Tree Metrics in Polynomial Time. Electronic Colloquium on Computational Complexity (ECCC) 19: 176 (2012) |
| 2011 | ||
| j79 | | Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann: Approximating Subdense Instances of Covering Problems. Electronic Notes in Discrete Mathematics 37: 297-302 (2011) |
| c98 | | Marek Karpinski, Warren Schudy: Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems. APPROX-RANDOM 2011: 277-288 |
| c97 | | |
| i91 | | Marek Karpinski, Richard Schmied, Claus Viehmann: Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs. CoRR abs/1107.2000 (2011) |
| i90 | | Piotr Berman, Bhaskar DasGupta, Lakshmi Kaligounder, Marek Karpinski: On Systemic Stability of Banking Networks. CoRR abs/1110.3546 (2011) |
| i89 | | Marek Karpinski, Richard Schmied: Improved Lower Bounds for the Shortest Superstring and Related Problems. CoRR abs/1111.5442 (2011) |
| i88 | | Martin E. Dyer, Uriel Feige, Alan M. Frieze, Marek Karpinski: Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). Dagstuhl Reports 1(6): 24-53 (2011) |
| i87 | | Marek Karpinski, Richard Schmied, Claus Viehmann: Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs. Electronic Colloquium on Computational Complexity (ECCC) 18: 98 (2011) |
| i86 | | Marek Karpinski, Richard Schmied: Improved Lower Bounds for the Shortest Superstring and Related Problems. Electronic Colloquium on Computational Complexity (ECCC) 18: 156 (2011) |
| 2010 | ||
| j78 | | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska: Computational Complexity of the Perfect Matching Problem in Hypergraphs with Subcritical Density. Int. J. Found. Comput. Sci. 21(6): 905-924 (2010) |
| j77 | | A. Abouelaoualim, Kinkar Chandra Das, Wenceslas Fernandez de la Vega, Marek Karpinski, Yannis Manoussakis, Carlos A. J. Martinhon, Rachid Saad: Cycles and paths in edge-colored graphs with given degrees. Journal of Graph Theory 64(1): 63-86 (2010) |
| j76 | | Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski: The mixing time of Glauber dynamics for coloring regular trees. Random Struct. Algorithms 36(4): 464-476 (2010) |
| j75 | | Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Deterministic Polynomial Time Algorithms for Matrix Completion Problems. SIAM J. Comput. 39(8): 3736-3751 (2010) |
| c96 | | Piotr Berman, Marek Karpinski, Andrzej Lingas: Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. COCOON 2010: 226-234 |
| c95 | | Marek Karpinski, Warren Schudy: Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. ISAAC (1) 2010: 3-14 |
| c94 | | Piotr Berman, Marek Karpinski, Alexander Zelikovsky: A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2. ISAAC (1) 2010: 15-24 |
| c93 | | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska: Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs. LATIN 2010: 662-673 |
| i85 | | Marek Karpinski, J. Ian Munro, Yakov Nekrich: Range Reporting for Moving Points on a Grid. CoRR abs/1002.3511 (2010) |
| i84 | | Marek Karpinski, Warren Schudy: Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. CoRR abs/1006.4396 (2010) |
| i83 | | Marek Karpinski, Yakov Nekrich: Top-K Color Queries for Document Retrieval. CoRR abs/1007.1361 (2010) |
| i82 | | Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann: Approximating Subdense Instances of Covering Problems. CoRR abs/1011.0078 (2010) |
| i81 | | Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann: Approximating Vertex Cover in Dense Hypergraphs. CoRR abs/1012.2573 (2010) |
| 2009 | ||
| j74 | | Marek Karpinski, Yakov Nekrich: A Fast Algorithm for Adaptive Prefix Coding. Algorithmica 55(1): 29-41 (2009) |
| c92 | | Marek Karpinski, Yakov Nekrich: Space Efficient Multi-dimensional Range Reporting. COCOON 2009: 215-224 |
| c91 | | |
| c90 | | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska: The Complexity of Perfect Matching Problems on Dense Hypergraphs. ISAAC 2009: 626-636 |
| c89 | | Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Schemes for deterministic polynomial factoring. ISSAC 2009: 191-198 |
| c88 | | Marek Karpinski, Warren Schudy: Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. STOC 2009: 313-322 |
| c87 | | Piotr Berman, Bhaskar DasGupta, Marek Karpinski: Approximating Transitive Reductions for Directed Networks. WADS 2009: 74-85 |
| c86 | | Piotr Berman, Marek Karpinski, Alexander Zelikovsky: 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2. WADS 2009: 86-97 |
| i80 | | Piotr Berman, Marek Karpinski, Andrzej Lingas: Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications. CoRR abs/0904.2310 (2009) |
| i79 | | Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Deterministic Polynomial Time Algorithms for Matrix Completion Problems. CoRR abs/0907.0774 (2009) |
| i78 | | Marek Karpinski, Warren Schudy: Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems. CoRR abs/0911.2214 (2009) |
| i77 | | Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Deterministic Polynomial Time Algorithms for Matrix Completion Problems. Electronic Colloquium on Computational Complexity (ECCC) 16: 58 (2009) |
| 2008 | ||
| j73 | | Magnus Bordewich, Martin E. Dyer, Marek Karpinski: Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Random Struct. Algorithms 32(3): 375-399 (2008) |
| c85 |  | |
| i76 | | Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Schemes for Deterministic Polynomial Factoring. CoRR abs/0804.1974 (2008) |
| i75 | | Marek Karpinski, Yakov Nekrich: Searching for Frequent Colors in Rectangles. CoRR abs/0805.1348 (2008) |
| i74 | | Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski: The Mixing Time of Glauber Dynamics for Colouring Regular Trees. CoRR abs/0806.0921 (2008) |
| i73 | | Marek Karpinski, Yakov Nekrich: Space-Efficient Multi-Dimensional Range Reporting. CoRR abs/0806.4361 (2008) |
| i72 | | Piotr Berman, Bhaskar DasGupta, Marek Karpinski: Approximating Transitivity in Directed Networks. CoRR abs/0809.0188 (2008) |
| i71 | | Piotr Berman, Marek Karpinski, Alexander Zelikovsky: 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two. CoRR abs/0810.1851 (2008) |
| i70 | | Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena: Trading GRH for algebra: algorithms for factoring polynomials and related structures. CoRR abs/0811.3165 (2008) |
| i69 | | Marek Karpinski, Warren Schudy: Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems. CoRR abs/0811.3244 (2008) |
| i68 | | Travis Gagie, Marek Karpinski, Yakov Nekrich: Low-Memory Adaptive Prefix Coding. CoRR abs/0811.3602 (2008) |
| i67 | | Piotr Berman, Marek Karpinski, Alexander Zelikovsky: A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two. CoRR abs/0812.2137 (2008) |
| i66 | | Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Schemes for Deterministic Polynomial Factoring. Electronic Colloquium on Computational Complexity (ECCC) 15(043) (2008) |
| i65 | | Piotr Berman, Marek Karpinski, Alexander Zelikovsky: 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two. Electronic Colloquium on Computational Complexity (ECCC) 15(094) (2008) |
| i64 | | Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena: Trading GRH for algebra: algorithms for factoring polynomials and related structures. Electronic Colloquium on Computational Complexity (ECCC) 15(099) (2008) |
| i63 | | Marek Karpinski, Warren Schudy: Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems. Electronic Colloquium on Computational Complexity (ECCC) 15(101) (2008) |
| 2007 | ||
| j72 | | Piotr Berman, Marek Karpinski, Alexander D. Scott: Computational complexity of some restricted instances of 3-SAT. Discrete Applied Mathematics 155(5): 649-653 (2007) |
| j71 | | Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, Marek Karpinski, Christian Knauer, Andrzej Lingas: Embedding Point Sets into Plane Graphs of Small Dilation. Int. J. Comput. Geometry Appl. 17(3): 201-230 (2007) |
| j70 | | Piotr Berman, Marek Karpinski, Yakov Nekrich: Approximating Huffman codes in parallel. J. Discrete Algorithms 5(3): 479-490 (2007) |
| j69 | | Wenceslas Fernandez de la Vega, Marek Karpinski: 1.0957-Approximation Algorithm for Random MAX-3SAT. RAIRO - Operations Research 41(1): 95-103 (2007) |
| j68 | | Piotr Berman, Marek Karpinski, Yakov Nekrich: Optimal trade-off for Merkle tree traversal. Theor. Comput. Sci. 372(1): 26-36 (2007) |
| i62 | | Piotr Berman, Bhaskar DasGupta, Marek Karpinski: Approximating Transitive Reductions for Directed Networks. Electronic Colloquium on Computational Complexity (ECCC) 14(119) (2007) |
| 2006 | ||
| j67 | | Lars Engebretsen, Marek Karpinski: TSP with bounded metrics. J. Comput. Syst. Sci. 72(4): 509-546 (2006) |
| j66 | | Marek Karpinski, Yakov Nekrich: Algorithms for Construction of Optimal and Almost-optimal Length-restricted Codes. Parallel Processing Letters 16(1): 81-92 (2006) |
| c84 | | Magnus Bordewich, Martin E. Dyer, Marek Karpinski: Stopping Times, Metrics and Approximate Counting. ICALP (1) 2006: 108-119 |
| c83 | | |
| i61 | | Wenceslas Fernandez de la Vega, Marek Karpinski: Approximation Complexity of Nondense Instances of MAX-CUT. Electronic Colloquium on Computational Complexity (ECCC) 13(101) (2006) |
| i60 | | Wenceslas Fernandez de la Vega, Marek Karpinski: On the Sample Complexity of MAX-CUT. Electronic Colloquium on Computational Complexity (ECCC) 13(104) (2006) |
| i59 | | Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Approximation of Global MAX-CSP Problems. Electronic Colloquium on Computational Complexity (ECCC) 13(124) (2006) |
| i58 | | Wenceslas Fernandez de la Vega, Marek Karpinski: Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP. Electronic Colloquium on Computational Complexity (ECCC) 13(155) (2006) |
| 2005 | ||
| j65 | | Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky: Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem. Algorithmica 42(2): 109-120 (2005) |
| j64 | | Farid M. Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, Chris Pollett: On the computational power of probabilistic and quantum branching program. Inf. Comput. 203(2): 145-162 (2005) |
| j63 | | Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel: Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. SIAM J. Comput. 35(1): 110-119 (2005) |
| c82 | | Marek Karpinski, Yakov Nekrich: Algorithms for Construction of Optimal and Almost-Optimal Length-Restricted Codes. DCC 2005: 464 |
| c81 | | |
| c80 | | Magnus Bordewich, Martin E. Dyer, Marek Karpinski: Path Coupling Using Stopping Times. FCT 2005: 19-31 |
| c79 | | |
| c78 | | Annette Ebbers-Baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas: Embedding Point Sets into Plane Graphs of Small Dilation. ISAAC 2005: 5-16 |
| c77 | | Cristina Bazgan, Marek Karpinski: On the Complexity of Global Constraint Satisfaction. ISAAC 2005: 624-633 |
| c76 | | Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala: Tensor decomposition and approximation schemes for constraint satisfaction problems. STOC 2005: 747-754 |
| i57 | | Magnus Bordewich, Martin E. Dyer, Marek Karpinski: Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs. Electronic Colloquium on Computational Complexity (ECCC)(002) (2005) |
| i56 | | Piotr Berman, Marek Karpinski: 8/7-Approximation Algorithm for (1,2)-TSP. Electronic Colloquium on Computational Complexity (ECCC)(069) (2005) |
| i55 | | Magnus Bordewich, Martin E. Dyer, Marek Karpinski: Metric Construction, Stopping Times and Path Coupling. Electronic Colloquium on Computational Complexity (ECCC)(151) (2005) |
| 2004 | ||
| j62 | | Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas: Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs. Fundam. Inform. 62(3-4): 369-375 (2004) |
| j61 | | Marek Karpinski, Lawrence L. Larmore, Yakov Nekrich: Work-Efficient Algorithms For The Construction Of Length-Limited Huffman Codes. Parallel Processing Letters 14(1): 99-105 (2004) |
| c75 | | Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon: Approximation schemes for Metric Bisection and partitioning. SODA 2004: 506-515 |
| i54 | | Piotr Berman, Marek Karpinski, Yakov Nekrich: Optimal Trade-Off for Merkle Tree Traversal. Electronic Colloquium on Computational Complexity (ECCC)(049) (2004) |
| i53 | | Piotr Berman, Marek Karpinski, Alexander D. Scott: Computational Complexity of Some Restricted Instances of 3SAT. Electronic Colloquium on Computational Complexity (ECCC)(111) (2004) |
| i52 | | Marek Karpinski, Yakov Nekrich: A Note on Traversing Skew Merkle Trees. Electronic Colloquium on Computational Complexity (ECCC)(118) (2004) |
| 2003 | ||
| j60 | | Farid M. Ablayev, Marek Karpinski: A lower bound for integer multiplication on randomized ordered read-once branching programs. Inf. Comput. 186(1): 78-89 (2003) |
| j59 | | Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Random sampling and approximation of MAX-CSPs. J. Comput. Syst. Sci. 67(2): 212-243 (2003) |
| j58 | | Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski: Polynomial time approximation schemes for dense instances of minimum constraint satisfaction. Random Struct. Algorithms 23(1): 73-91 (2003) |
| c74 | | Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani: Approximation schemes for clustering problems. STOC 2003: 50-58 |
| c73 | | Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky: Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem. WADS 2003: 401-411 |
| i51 | | Piotr Berman, Marek Karpinski: Improved Approximation Lower Bounds on Small Occurrence Optimization. Electronic Colloquium on Computational Complexity (ECCC) 10(008) (2003) |
| i50 | | Piotr Berman, Marek Karpinski, Alex D. Scott: Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT. Electronic Colloquium on Computational Complexity (ECCC) 10(022) (2003) |
| i49 | | Piotr Berman, Marek Karpinski, Alex D. Scott: Approximation Hardness of Short Symmetric Instances of MAX-3SAT . Electronic Colloquium on Computational Complexity (ECCC)(049) (2003) |
| i48 | | Piotr Berman, Marek Karpinski: Approximability of Hypergraph Minimum Bisection . Electronic Colloquium on Computational Complexity (ECCC)(056) (2003) |
| 2002 | ||
| j57 | | Rusins Freivalds, Marek Karpinski, Carl H. Smith, Rolf Wiehagen: Learning by the Process of Elimination. Inf. Comput. 176(1): 37-50 (2002) |
| j56 | | Susanne Albers, Marek Karpinski: Randomized splay trees: Theoretical and experimental results. Inf. Process. Lett. 81(4): 213-221 (2002) |
| j55 | | Uriel Feige, Marek Karpinski, Michael Langberg: Improved approximation of Max-Cut on graphs of bounded degree. J. Algorithms 43(2): 201-219 (2002) |
| j54 | | Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter: On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. J. Comput. Syst. Sci. 65(2): 332-350 (2002) |
| c72 | | Piotr Berman, Sridhar Hannenhalli, Marek Karpinski: 1.375-Approximation Algorithm for Sorting by Reversals. ESA 2002: 200-210 |
| c71 | | Piotr Berman, Marek Karpinski: Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION. ICALP 2002: 623-632 |
| c70 | | Piotr Berman, Marek Karpinski, Yakov Nekrich: Approximating Huffman Codes in Parallel. ICALP 2002: 845-855 |
| c69 | | Marek Karpinski: Approximability of the Minimum Bisection Problem: An Algorithmic Challenge. MFCS 2002: 59-67 |
| c68 | | Béla Csaba, Marek Karpinski, Piotr Krysta: Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. SODA 2002: 74-83 |
| c67 | | Piotr Berman, Marek Karpinski: Approximating minimum unsatisfiability of linear equations. SODA 2002: 514-516 |
| c66 | | Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Random sampling and approximation of MAX-CSP problems. STOC 2002: 232-239 |
| c65 | | Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski: Approximability of Dense Instances of NEAREST CODEWORD Problem. SWAT 2002: 298-307 |
| i47 | | Piotr Berman, Marek Karpinski, Yakov Nekrich: Approximating Huffman Codes in Parallel. Electronic Colloquium on Computational Complexity (ECCC)(018) (2002) |
| i46 | | Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani: Polynomial Time Approximation Schemes for Metric Min-Sum Clustering. Electronic Colloquium on Computational Complexity (ECCC)(025) (2002) |
| i45 | | Marek Karpinski, Yakov Nekrich: Parallel Construction of Minimum Redundancy Length-Limited Codes. Electronic Colloquium on Computational Complexity (ECCC)(029) (2002) |
| i44 | | Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon: A Polynomial Time Approximation Scheme for Metric MIN-BISECTION. Electronic Colloquium on Computational Complexity (ECCC)(041) (2002) |
| i43 | | Wenceslas Fernandez de la Vega, Marek Karpinski: A Polynomial Time Approximation Scheme for Subdense MAX-CUT. Electronic Colloquium on Computational Complexity (ECCC)(044) (2002) |
| i42 | | Marek Karpinski: On Approximability of Minimum Bisection Problem. Electronic Colloquium on Computational Complexity (ECCC)(046) (2002) |
| i41 | | Wenceslas Fernandez de la Vega, Marek Karpinski: 9/8-Approximation Algorithm for Random MAX-3SAT. Electronic Colloquium on Computational Complexity (ECCC)(070) (2002) |
| 2001 | ||
| j53 | | Marek Karpinski: Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems. Algorithmica 30(3): 386-397 (2001) |
| j52 | | Uriel Feige, Marek Karpinski, Michael Langberg: A note on approximating Max-Bisection on regular graphs. Inf. Process. Lett. 79(4): 181-188 (2001) |
| j51 | | Farid M. Ablayev, Marek Karpinski, Rustam Mubarakzjanov: On BPP versus NPcoNP for ordered read-once branching programs. Theor. Comput. Sci. 264(1): 127-137 (2001) |
| c64 | | |
| c63 | | Farid M. Ablayev, Aida Gainutdinova, Marek Karpinski: On Computational Power of Quantum Branching Programs. FCT 2001: 59-70 |
| c62 | | Lars Engebretsen, Marek Karpinski: Approximation Hardness of TSP with Bounded Metrics. ICALP 2001: 201-212 |
| c61 | | Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel: Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. STACS 2001: 365-375 |
| i40 | | Piotr Berman, Marek Karpinski: Approximating Minimum Unsatisfiability of Linear Equations. Electronic Colloquium on Computational Complexity (ECCC) 8(25) (2001) |
| i39 | | Piotr Berman, Marek Karpinski: Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION. Electronic Colloquium on Computational Complexity (ECCC) 8(26) (2001) |
| i38 | | Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski: Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction. Electronic Colloquium on Computational Complexity (ECCC) 8(34) (2001) |
| i37 | | Marek Karpinski: Approximating Bounded Degree Instances of NP-Hard Problems. Electronic Colloquium on Computational Complexity (ECCC) 8(42) (2001) |
| i36 | | Piotr Berman, Sridhar Hannenhalli, Marek Karpinski: 1.375-Approximation Algorithm for Sorting by Reversals. Electronic Colloquium on Computational Complexity (ECCC) 8(47) (2001) |
| i35 | | Piotr Berman, Marek Karpinski: Efficient Amplifiers and Bounded Degree Optimization . Electronic Colloquium on Computational Complexity (ECCC) 8(53) (2001) |
| i34 | | Piotr Berman, Marek Karpinski: Improved Approximations for General Minimum Cost Scheduling. Electronic Colloquium on Computational Complexity (ECCC)(097) (2001) |
| i33 | | Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Random Sampling and Approximation of MAX-CSP Problems. Electronic Colloquium on Computational Complexity (ECCC)(100) (2001) |
| 2000 | ||
| j50 | | Piotr Berman, Moses Charikar, Marek Karpinski: On-Line Load Balancing for Related Machines. J. Algorithms 35(1): 108-121 (2000) |
| j49 | | Wenceslas Fernandez de la Vega, Marek Karpinski: Polynomial time approximation of dense weighted instances of MAX-CUT. Random Struct. Algorithms 16(4): 314-332 (2000) |
| j48 | | Marek Karpinski, Alfred J. van der Poorten, Igor Shparlinski: Zero testing of p-adic and modular polynomials. Theor. Comput. Sci. 233(1-2): 309-317 (2000) |
| i32 | | Piotr Berman, Moses Charikar, Marek Karpinski: On-Line Load Balancing for Related Machines. Electronic Colloquium on Computational Complexity (ECCC) 7(1) (2000) |
| i31 | | Uriel Feige, Marek Karpinski, Michael Langberg: Improved Approximation of MAX-CUT on Graphs of Bounded Degree. Electronic Colloquium on Computational Complexity (ECCC) 7(21) (2000) |
| i30 | | Uriel Feige, Marek Karpinski, Michael Langberg: A Note on Approximating MAX-BISECTION on Regular Graphs. Electronic Colloquium on Computational Complexity (ECCC) 7(43) (2000) |
| i29 | | Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas: Approximation Algorithms for MAX-BISECTION on Low Degree Reg ular Graphs and Planar Graphs. Electronic Colloquium on Computational Complexity (ECCC) 7(51) (2000) |
| i28 | | Klaus Jansen, Marek Karpinski, Andrzej Lingas: A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs. Electronic Colloquium on Computational Complexity (ECCC) 7(64) (2000) |
| i27 | | Lars Engebretsen, Marek Karpinski: Approximation Hardness of TSP with Bounded Metrics. Electronic Colloquium on Computational Complexity (ECCC) 7(89) (2000) |
| i26 | | Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski: Approximability of Dense Instances of NEAREST CODEWORD Problem. Electronic Colloquium on Computational Complexity (ECCC) 7(91) (2000) |
| 1999 | ||
| j47 | | Sergei Evdokimov, Marek Karpinski, Ilia N. Ponomarenko: Compact cellular algebras and permutation groups. Discrete Mathematics 197-198: 247-267 (1999) |
| j46 | | Wenceslas Fernandez de la Vega, Marek Karpinski: On the Approximation Hardness of Dense TSP and Other Path Problems. Inf. Process. Lett. 70(2): 53-55 (1999) |
| j45 | | Sanjeev Arora, David R. Karger, Marek Karpinski: Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. J. Comput. Syst. Sci. 58(1): 193-210 (1999) |
| c60 | | Marek Karpinski, Igor Shparlinski: On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials. AAECC 1999: 492-497 |
| c59 | | |
| c58 | | Piotr Berman, Marek Karpinski: On Some Tighter Inapproximability Results (Extended Abstract). ICALP 1999: 200-209 |
| c57 | | Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski: Quantum Finite Multitape Automata. SOFSEM 1999: 340-348 |
| i25 | | Marek Karpinski, Rustam Mubarakzjanov: A Note on Las Vegas OBDDs. Electronic Colloquium on Computational Complexity (ECCC) 6(9) (1999) |
| i24 | | Marek Karpinski: Randomized Complexity of Linear Arrangements and Polyhedra. Electronic Colloquium on Computational Complexity (ECCC) 6(20) (1999) |
| i23 | | Marek Karpinski, Igor Shparlinski: On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials. Electronic Colloquium on Computational Complexity (ECCC) 6(27) (1999) |
| 1998 | ||
| j44 | | Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao: An exponential lower bound on the size of algebraic decision trees for Max. Computational Complexity 7(3): 193-203 (1998) |
| j43 | | Elias Dahlhaus, Marek Karpinski: Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs. Discrete Applied Mathematics 84(1-3): 79-91 (1998) |
| j42 | | Marek Karpinski, Wojciech Rytter: On a Sublinear Time Parallel Construction of Optimal Binary Search Trees. Parallel Processing Letters 8(3): 387-397 (1998) |
| j41 | | Mikael Goldmann, Marek Karpinski: Simulating Threshold Circuits by Majority Circuits. SIAM J. Comput. 27(1): 230-246 (1998) |
| j40 | | Dima Grigoriev, Marek Karpinski: Computing the Additive Complexity of Algebraic Circuits with Root Extracting. SIAM J. Comput. 27(3): 694-701 (1998) |
| j39 | | Marek Karpinski, Wojciech Rytter: Alphabet-Independent Optimal Parallel Search for Three-Dimensional Patterns. Theor. Comput. Sci. 205(1-2): 243-260 (1998) |
| c56 | | Dima Grigoriev, Marek Karpinski: An Exponential Lower Bound for Depth 3 Arithmetic Circuits. STOC 1998: 577-582 |
| i22 | | Farid M. Ablayev, Marek Karpinski: On the Power of Randomized Ordered Branching Programs. Electronic Colloquium on Computational Complexity (ECCC) 5(4) (1998) |
| i21 | | Farid M. Ablayev, Marek Karpinski: A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs . Electronic Colloquium on Computational Complexity (ECCC) 5(11) (1998) |
| i20 | | Gunter Blache, Marek Karpinski, Juergen Wirtgen: On Approximation Intractability of the Bandwidth Problem. Electronic Colloquium on Computational Complexity (ECCC) 5(14) (1998) |
| i19 | | Wenceslas Fernandez de la Vega, Marek Karpinski: On Approximation Hardness of Dense TSP and other Path Problems. Electronic Colloquium on Computational Complexity (ECCC) 5(24) (1998) |
| i18 | | Piotr Berman, Marek Karpinski: On Some Tighter Inapproximability Results. Electronic Colloquium on Computational Complexity (ECCC) 5(29) (1998) |
| i17 | | Marek Karpinski: On the Computational Power of Randomized Branching Programs. Electronic Colloquium on Computational Complexity (ECCC) 5(38) (1998) |
| i16 | | Wenceslas Fernandez de la Vega, Marek Karpinski: Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT. Electronic Colloquium on Computational Complexity (ECCC) 5(64) (1998) |
| i15 | | Piotr Berman, Marek Karpinski: On Some Tighter Inapproximability Results, Further Improvements. Electronic Colloquium on Computational Complexity (ECCC) 5(65) (1998) |
| 1997 | ||
| j38 | | Joachim von zur Gathen, Marek Karpinski, Igor Shparlinski: Counting Curves and Their Projections. Computational Complexity 6(1): 64-99 (1997) |
| j37 | | Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees. Computational Complexity 6(4): 357-375 (1997) |
| j36 | | Dima Grigoriev, Marek Karpinski, Roman Smolensky: Randomization and the Computational Power of Analytic and Algebraic Decision Trees. Computational Complexity 6(4): 376-388 (1997) |
| j35 | | Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov: Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees. Discrete & Computational Geometry 17(2): 191-215 (1997) |
| j34 | | Marek Karpinski, Alexander Zelikovsky: New Approximation Algorithms for the Steiner Tree Problems. J. Comb. Optim. 1(1): 47-65 (1997) |
| j33 | | Marek Karpinski, Angus Macintyre: Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks. J. Comput. Syst. Sci. 54(1): 169-176 (1997) |
| j32 | | Marek Karpinski, Wojciech Rytter, Ayumi Shinohara: An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions. Nord. J. Comput. 4(2): 172-186 (1997) |
| j31 | | Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter: Correctness of Constructing Optimal Alphabetic Trees Revisited. Theor. Comput. Sci. 180(1-2): 309-324 (1997) |
| c55 | | Andris Ambainis, Kalvis Apsitis, Cristian Calude, Rusins Freivalds, Marek Karpinski, Tomas Larfeldt, Iveta Sala, Juris Smotrovs: Effects of Kolmogorov Complexity Present in Inductive Inference as Well. ALT 1997: 244-259 |
| c54 | | Marek Karpinski, Angus Macintyre: Approximating the Volume of General Pfaffian Bodies. Structures in Logic and Computer Science 1997: 162-173 |
| c53 | | Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter: On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. CPM 1997: 40-51 |
| c52 | | Alexander L. Chistov, Gábor Ivanyos, Marek Karpinski: Polynomial Time Algorithms for Modules over Finite Dimensional Algebras. ISSAC 1997: 68-74 |
| c51 | | Marek Karpinski: Polynominal Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems. RANDOM 1997: 1-14 |
| c50 | | Andris Ambainis, Rusins Freivalds, Marek Karpinski: Weak and Strong Recognition by 2-way Randomized Automata. RANDOM 1997: 175-185 |
| c49 | | |
| c48 | | Piotr Berman, Moses Charikar, Marek Karpinski: On-line Load Balancing for Related Machines. WADS 1997: 116-125 |
| i14 | | Marek Karpinski, Alexander Zelikovsky: Approximating Dense Cases of Covering Problems. Electronic Colloquium on Computational Complexity (ECCC) 4(4) (1997) |
| i13 | | Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky: An Approximation Algorithm for the Bandwidth Problem on Dense Graphs. Electronic Colloquium on Computational Complexity (ECCC) 4(17) (1997) |
| i12 | | Marek Karpinski: Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems. Electronic Colloquium on Computational Complexity (ECCC) 4(24) (1997) |
| i11 | | Marek Karpinski, Juergen Wirtgen: On Approximation Hardness of the Bandwidth Problem. Electronic Colloquium on Computational Complexity (ECCC) 4(41) (1997) |
| 1996 | ||
| j30 | | Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko: Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann. Fundam. Inform. 28(3-4): 297-301 (1996) |
| j29 | | Marek Karpinski, Rutger Verbeek: On Randomized versus Deterministic Computation. Theor. Comput. Sci. 154(1): 23-39 (1996) |
| j28 | | Dima Grigoriev, Marek Karpinski: Computability of the Additive Complexity of Algebraic Circuits with Root Extracting. Theor. Comput. Sci. 157(1): 91-99 (1996) |
| j27 | | Marek Karpinski, Igor Shparlinski: On Some Approximation Problems Concerning Sparse Polynomials over Finite Fields. Theor. Comput. Sci. 157(2): 259-266 (1996) |
| c47 | | Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter: Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract). CPM 1996: 39-49 |
| c46 | | Farid M. Ablayev, Marek Karpinski: On the Power of Randomized Branching Programs. ICALP 1996: 348-356 |
| c45 | | Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter: Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees. SODA 1996: 36-41 |
| c44 | | Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees. STOC 1996: 612-619 |
| c43 | | Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter: Efficient Algorithms for Lempel-Zip Encoding (Extended Abstract). SWAT 1996: 392-403 |
| i10 | | Dima Grigoriev, Marek Karpinski: Randomized Omega(n2) Lower Bound for Knapsack. Electronic Colloquium on Computational Complexity (ECCC) 3(58) (1996) |
| 1995 | ||
| j26 | | Hans Kleine Büning, Marek Karpinski, Andreas Flögel: Resolution for Quantified Boolean Formulas. Inf. Comput. 117(1): 12-18 (1995) |
| c42 | | Marek Karpinski, Wojciech Rytter, Ayumi Shinohara: Pattern-Matching for Strings with Short Descriptions. CPM 1995: 205-214 |
| c41 | | Marek Karpinski, Angus Macintyre: Bounding VC-dimension of neural networks: Progress and prospects. EuroCOLT 1995: 337-341 |
| c40 | | Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov: Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. FOCS 1995: 258-265 |
| c39 | | Rusins Freivalds, Marek Karpinski: Lower Time Bounds for Randomized Computation. ICALP 1995: 183-195 |
| c38 | | Marek Karpinski, Angus Macintyre: Polynomial bounds for VC dimension of sigmoidal neural networks. STOC 1995: 200-208 |
| c37 | | Sanjeev Arora, David R. Karger, Marek Karpinski: Polynomial time approximation schemes for dense instances of NP-hard problems. STOC 1995: 284-293 |
| c36 | | Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, Kai Werther: On real Turing machines that toss coins. STOC 1995: 335-342 |
| i9 | | Marek Karpinski, Alexander Zelikovsky: 1.757 and 1.267 - Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems. Electronic Colloquium on Computational Complexity (ECCC) 2(3) (1995) |
| i8 | | Marek Karpinski, Rutger Verbeek: On Randomized Versus Deterministic Computation. Electronic Colloquium on Computational Complexity (ECCC) 2(21) (1995) |
| i7 | | Marek Karpinski, Wojciech Rytter, Ayumi Shinohara: Pattern-Matching for Strings with Short Descriptions. Electronic Colloquium on Computational Complexity (ECCC) 2(22) (1995) |
| i6 | | Marek Karpinski, Alexander Zelikovsky: New Approximation Algorithms for the Steiner Tree Problems. Electronic Colloquium on Computational Complexity (ECCC) 2(30) (1995) |
| i5 | | Farid M. Ablayev, Marek Karpinski: On the Power of Randomized Branching Programs. Electronic Colloquium on Computational Complexity (ECCC) 2(54) (1995) |
| i4 | | Marek Karpinski, Angus Macintyre: VC Dimension of Sigmoidal and General Pfaffian Networks. Electronic Colloquium on Computational Complexity (ECCC) 2(55) (1995) |
| i3 | | Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao: An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX. Electronic Colloquium on Computational Complexity (ECCC) 2(57) (1995) |
| i2 | | Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees. Electronic Colloquium on Computational Complexity (ECCC) 2(63) (1995) |
| 1994 | ||
| j25 | | Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski: An Algorithm to Learn Read-Once Threshold Formulas, and Transformations Between Learning Models. Computational Complexity 4: 37-61 (1994) |
| j24 | | Dima Grigoriev, Marek Karpinski, Michael F. Singer: Computational Complexity of Sparse Rational Interpolation. SIAM J. Comput. 23(1): 1-11 (1994) |
| j23 | | Elias Dahlhaus, Marek Karpinski: An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph. Theor. Comput. Sci. 134(2): 493-528 (1994) |
| c35 | | Rusins Freivalds, Dace Gobleja, Marek Karpinski, Carl H. Smith: Co-learnability and FIN-identifiability of Enumerable Classes of Total Recursive Functions. AII/ALT 1994: 100-105 |
| c34 | | Rusins Freivalds, Marek Karpinski, Carl H. Smith: Co-Learning of Total Recursive Functions. COLT 1994: 190-197 |
| c33 | | Marek Karpinski, Wojciech Rytter: An Alphabet-Independent Optimal Parallel Search for Three Dimensional Pattern. CPM 1994: 125-135 |
| c32 | | Piotr Berman, Ulrich Fößmeier, Marek Karpinski, Michael Kaufmann, Alexander Zelikovsky: Approaching the 5/4-Approximation for Rectilinear Steiner Trees. ESA 1994: 60-71 |
| c31 | | Rusins Freivalds, Marek Karpinski: Lower Space Bounds for Randomized Computation. ICALP 1994: 580-592 |
| c30 | | Marek Karpinski, Wojciech Rytter: On a Sublinear Time Parallel Construction of Optimal Binary Search Trees. MFCS 1994: 453-461 |
| c29 | | Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov: Lower bounds on testing membership to a polyhedron by algebraic decision trees. STOC 1994: 635-644 |
| i1 | | Marek Karpinski, Angus Macintyre: Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks. Electronic Colloquium on Computational Complexity (ECCC) 1(24) (1994) |
| 1993 | ||
| j22 | | Dana Angluin, Lisa Hellerstein, Marek Karpinski: Learning Read-Once Formulas with Queries. J. ACM 40(1): 185-210 (1993) |
| j21 | | Marek Karpinski, Michael Luby: Approximating the Number of Zeroes of a GF[2] Polynomial. J. Algorithms 14(2): 280-287 (1993) |
| j20 | | Elias Dahlhaus, Péter Hajnal, Marek Karpinski: On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs. J. Algorithms 15(3): 367-384 (1993) |
| j19 | | Peter Bürgisser, Marek Karpinski, Thomas Lickteig: On Randomized Semi-algebraic Test Complexity. J. Complexity 9(2): 231-251 (1993) |
| j18 | | Marek Karpinski, Thorsten Werther: VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions. SIAM J. Comput. 22(6): 1276-1285 (1993) |
| c28 | | Dima Grigoriev, Marek Karpinski: A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals. AAECC 1993: 162-169 |
| c27 | | Marek Karpinski, Rutger Verbeek: On Randomized Versus Deterministic Computation. ICALP 1993: 227-240 |
| c26 | | Mikael Goldmann, Marek Karpinski: Simulating threshold circuits by majority circuits. STOC 1993: 551-560 |
| c25 | | Joachim von zur Gathen, Marek Karpinski, Igor Shparlinski: Counting curves and their projections. STOC 1993: 805-812 |
| 1992 | ||
| j17 | | Elias Dahlhaus, Marek Karpinski, Pierre Kelsen: An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3. Inf. Process. Lett. 42(6): 309-313 (1992) |
| j16 | | Elias Dahlhaus, Marek Karpinski: Perfect Matching for Regular Graphs is AC°-Hard for the General Matching Problem. J. Comput. Syst. Sci. 44(1): 94-102 (1992) |
| c24 | | Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko: Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis. ISSAC 1992: 117-122 |
| 1991 | ||
| j15 | | Peter Bürgisser, Marek Karpinski, Thomas Lickteig: Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication. Computational Complexity 1: 131-155 (1991) |
| j14 | | Michael Clausen, Andreas W. M. Dress, Johannes Grabmeier, Marek Karpinski: On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials Over Finite Fields. Theor. Comput. Sci. 84(2): 151-164 (1991) |
| c23 | | |
| c22 | | Dima Grigoriev, Marek Karpinski: An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]. FOCS 1991: 662-669 |
| c21 | | |
| c20 | | Marek Karpinski, Michael Luby: Approximating the Number of Zeroes of a GF[2] Polynomial. SODA 1991: 300-303 |
| 1990 | ||
| j13 | | Dima Grigoriev, Marek Karpinski, Michael F. Singer: Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields. SIAM J. Comput. 19(6): 1059-1063 (1990) |
| c19 | | Andreas Flögel, Marek Karpinski, Hans Kleine Büning: Subclasses of Quantified Boolean Formulas. CSL 1990: 145-155 |
| c18 | | Dima Grigoriev, Marek Karpinski, Michael F. Singer: Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents. FOCS 1990: 840-846 |
| c17 | | Marek Karpinski, Friedhelm Meyer auf der Heide: On the Complexity of Genuinely Polynomial Computation. MFCS 1990: 362-368 |
| c16 | | Elias Dahlhaus, Marek Karpinski, Mark B. Novick: Fast Parallel Algorithms for the Clique Separator Decomposition. SODA 1990: 244-251 |
| 1989 | ||
| j12 | | Andrzej Lingas, Marek Karpinski: Subtree Isomorphism is NC Reducible to Bipartite Perfect Matching. Inf. Process. Lett. 30(1): 27-32 (1989) |
| c15 | | Lisa Hellerstein, Marek Karpinski: Learning Read-Once Formulas Using Membership Queries. COLT 1989: 146-161 |
| c14 | | Elias Dahlhaus, Marek Karpinski: An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract). FOCS 1989: 454-459 |
| 1988 | ||
| j11 | | Elias Dahlhaus, Marek Karpinski: Parallel Construction of Perfect Matchings and Hamiltonian Cycles on Dense Graphs. Theor. Comput. Sci. 61: 121-136 (1988) |
| c13 | | |
| c12 | | Elias Dahlhaus, Péter Hajnal, Marek Karpinski: Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs. FOCS 1988: 186-193 |
| c11 | | Marek Karpinski, Zbigniew W. Ras: Learning Machine for Probabilistically Describable Concepts. ISMIS 1988: 353-362 |
| c10 | | Elias Dahlhaus, Marek Karpinski: A Fast Parallel Algorithm for Computing all Maximal Cliques in a Graph and the Related Problems (Extended Abstract). SWAT 1988: 139-144 |
| 1987 | ||
| j10 | | Marek Karpinski, Rutger Verbeek: On the Monte Carlo Space Constructible Functions and Seperation Results for Probabilistic Complexity Classes. Inf. Comput. 75(2): 178-189 (1987) |
| c9 | | Marek Karpinski, Rutger Verbeek: Randomness, Provability, and the Seperation of Monte Carlo Time and Space. Computation Theory and Logic 1987: 189-207 |
| c8 | | Marek Karpinski, Hans Kleine Büning, Peter H. Schmitt: On the Computational Complexity of Quantified Horn Clauses. CSL 1987: 129-137 |
| c7 | | Dima Grigoriev, Marek Karpinski: The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract). FOCS 1987: 166-172 |
| 1986 | ||
| j9 | | Marek Karpinski, Rutger Verbeek: On the Power of Two-Way Random Generators and the Impossibility of Deterministic Poly-Space Simulation. Information and Control 71(1/2): 131-142 (1986) |
| 1985 | ||
| j8 | | |
| j7 | | Marek Karpinski, Rutger Verbeek: There Is No Polynomial Deterministic Space Simulation of Probabilistic Space with a Two-Way Random-Tape Generator. Information and Control 67(1-3): 158-162 (1985) |
| 1983 | ||
| e2 | | Marek Karpinski (Ed.): Fundamentals of Computation Theory, Proceedings of the 1983 International FCT-Conference, Borgholm, Sweden, August 21-27, 1983. Lecture Notes in Computer Science 158, Springer 1983, isbn 3-540-12689-9 |
| 1982 | ||
| j6 | | Marek Karpinski: Decidability of "Skolem Matrix Emptiness Problem" Entails Constructability of Exact Regular Expression. Theor. Comput. Sci. 17: 99-102 (1982) |
| 1980 | ||
| c6 | | Marek Karpinski: On global word definability and constructively definable sets in Nn. CLAAP 1980: 225-227 |
| 1979 | ||
| c5 | | Ryszard Danecki, Marek Karpinski: Decidability Results on Plane Automata Searching Mazes. FCT 1979: 84-91 |
| 1977 | ||
| c4 | | |
| e1 | | Marek Karpinski (Ed.): Fundamentals of Computation Theory, Proceedings of the 1977 International FCT-Conference, Poznan-Kórnik, Poland, September 19-23, 1977. Lecture Notes in Computer Science 56, Springer 1977, isbn 3-540-08442-8 |
| 1976 | ||
| j5 | | Marek Karpinski: Valued Probabilistic Tree Functions. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 24: 927-930 (1976) |
| c3 | | |
| 1975 | ||
| c2 | | |
| 1974 | ||
| j4 | | Marek Karpinski: Free Structure Tree Automata IV. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 22: 87-91 (1974) |
| j3 | | Marek Karpinski: Probablistic Climbing and Sinking Languages. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 22: 1057-1062 (1974) |
| c1 | | |
| 1973 | ||
| j2 | | Marek Karpinski: Free Structure Tree Automata, II: Nondeterminstic and Deterministic Regularity. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 21(5): 447-450 (1973) |
| j1 | | Marek Karpinski: Free Structure Tree Automata, III: Normalized Climbing Automata. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 21(6): 567-572 (1973) |
Colors in the list of coauthors
Last update Fri May 24 06:55:07 2013 CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page