Marek Karpinski

339 papers A* 37A 5B 42C 1Misc 2Journal 224Unranked 26

Year	Rank	Type	Title / Venue / Authors
2021	J	`jnl`	Noisy polynomial interpolation modulo prime powers. J. Complex. Marek Karpinski, Igor E. Shparlinski
2020	J	`jnl`	Dense Steiner problems: Approximation algorithms and inapproximability. CoRR Marek Karpinski, Mateusz Lewandowski, Syed Mohammad Meesum, Matthias Mnich
2020	J	`jnl`	Noisy polynomial interpolation modulo prime powers. CoRR Marek Karpinski, Igor E. Shparlinski
2018	J	`jnl`	A QPTAS for the base of the number of crossing-free structures on a planar point set. Theor. Comput. Sci. Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
2018	J	`jnl`	Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications. Algorithmica Bhaskar DasGupta, Marek Karpinski, Nasim Mobasheri, Farzane Yahyanejad
2018	J	`jnl`	Identity testing and interpolation from high powers of polynomials of large degree over finite fields. J. Complex. Marek Karpinski, László Mérai, Igor E. Shparlinski
2018	J	`jnl`	Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields. Algorithmica Gábor Ivanyos, Marek Karpinski, Miklos Santha, Nitin Saxena, Igor E. Shparlinski
2018	J	`jnl`	Tropical dominating sets in vertex-coloured graphs. J. Discrete Algorithms Jean-Alexandre Anglès d'Auriac, Csilla Bujtás, Abdelhakim El Maftouhi, Marek Karpinski, Yannis Manoussakis, Leandro Montero, N. Narayanan, Laurent Rosaz, Johan Thapper, Zsolt Tuza
2017	J	`jnl`	Identity Testing from High Powers of Polynomials of Large Degree over Finite Fields. CoRR Marek Karpinski, Igor E. Shparlinski
2016	J	`jnl`	Approximation Complexity of Max-Cut on Power Law Graphs. CoRR Mikael Gast, Mathias Hauptmann, Marek Karpinski
2016	B	`conf`	Tropical Dominating Sets in Vertex-Coloured Graphs. WALCOM Jean-Alexandre Anglès d'Auriac, Csilla Bujtás, Hakim El Maftouhi, Marek Karpinski, Yannis Manoussakis, Leandro Montero, Narayanan Narayanan, Laurent Rosaz, Johan Thapper, Zsolt Tuza
2015	—	`conf`	A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set. ICALP (1) Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
2015	J	`jnl`	Approximability of TSP on Power Law Graphs. CoRR Mikael Gast, Mathias Hauptmann, Marek Karpinski
2015	J	`jnl`	Approximation hardness of graphic TSP on cubic graphs. RAIRO Oper. Res. Marek Karpinski, Richard Schmied
2015	J	`jnl`	Complexity of Symbolic and Numerical Problems (Dagstuhl Seminar 15242). Dagstuhl Reports Peter Bürgisser, Felipe Cucker, Marek Karpinski, Nicolai N. Vorobjov Jr.
2015	J	`jnl`	Explicit Bounds for Nondeterministically Testable Hypergraph Parameters. CoRR Marek Karpinski, Roland Markó
2015	J	`jnl`	Generalized Wong sequences and their applications to Edmonds' problems. J. Comput. Syst. Sci. Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
2015	J	`jnl`	Inapproximability of dominating set on power law graphs. Theor. Comput. Sci. Mikael Gast, Mathias Hauptmann, Marek Karpinski
2015	J	`jnl`	Nearly tight approximation bounds for vertex cover on dense k-uniform k-partite hypergraphs. J. Discrete Algorithms Marek Karpinski, Richard Schmied, Claus Viehmann
2015	J	`jnl`	New inapproximability bounds for TSP. J. Comput. Syst. Sci. Marek Karpinski, Michael Lampis, Richard Schmied
2015	J	`jnl`	Node Expansions and Cuts in Gromov-hyperbolic Graphs. CoRR Bhaskar DasGupta, Marek Karpinski, Nasim Mobasheri, Farzane Yahyanejad
2015	J	`jnl`	On the Approximability of Independent Set Problem on Power Law Graphs. CoRR Mathias Hauptmann, Marek Karpinski
2015	J	`jnl`	On the Complexity of Nondeterministically Testable Hypergraph Parameters. CoRR Marek Karpinski, Roland Markó
2015	J	`jnl`	Polynomial Interpolation and Identity Testing from High Powers over Finite Fields. CoRR Gábor Ivanyos, Marek Karpinski, Miklos Santha, Nitin Saxena, Igor E. Shparlinski
2015	B	`conf`	Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies. FCT Marek Karpinski
2015	J	`jnl`	Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies. Electron. Colloquium Comput. Complex. Marek Karpinski
2015	J	`jnl`	Tropical Dominating Sets in Vertex-Coloured Graphs. CoRR Jean-Alexandre Anglès d'Auriac, Csilla Bujtás, Hakim El Maftouhi, Marek Karpinski, Yannis Manoussakis, Leandro Montero, N. Narayanan, Laurent Rosaz, Johan Thapper, Zsolt Tuza
2014	J	`jnl`	A QPTAS for the Base of the Number of Triangulations of a Planar Point Set. CoRR Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
2014	—	`conf`	Approximate Counting of Matchings in (3, 3)-Hypergraphs. SWAT Andrzej Dudek, Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
2014	J	`jnl`	Approximate Counting of Matchings in (3, 3)-Hypergraphs. CoRR Andrzej Dudek, Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
2014	J	`jnl`	Approximate Counting of Matchings in (3,3)-Hypergraphs. Electron. Colloquium Comput. Complex. Andrzej Dudek, Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
2014	J	`jnl`	Complexity of Nondeterministic Graph Parameter Testing. CoRR Marek Karpinski, Roland Markó
2014	J	`jnl`	Deterministic polynomial factoring and association schemes. LMS J. Comput. Math. Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena
2014	A	`conf`	Generalized Wong sequences and their applications to Edmonds' problems. STACS Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
2014	J	`jnl`	Limits of CSP Problems and Efficient Parameter Testing. CoRR Marek Karpinski, Roland Markó
2014	J	`jnl`	On the Computational Complexity of Measuring Global Stability of Banking Networks. Algorithmica Piotr Berman, Bhaskar DasGupta, Lakshmi Kaligounder, Marek Karpinski
2013	J	`jnl`	Algorithmic Perspectives of Network Transitive Reduction Problems and their Applications to Synthesis and Analysis of Biological Networks. CoRR Satabdi Aditya, Bhaskar DasGupta, Marek Karpinski
2013	—	`conf`	Approximate Counting of Matchings in Sparse Uniform Hypergraphs. ANALCO Edyta Szymanska, Marek Karpinski, Andrzej Rucinski
2013	J	`jnl`	Approximation Hardness of Graphic TSP on Cubic Graphs CoRR Marek Karpinski, Richard Schmied
2013	J	`jnl`	Approximation Hardness of Graphic TSP on Cubic Graphs. Electron. Colloquium Comput. Complex. Marek Karpinski, Richard Schmied
2013	J	`jnl`	Generalized Wong sequences and their applications to Edmonds' problems. CoRR Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
2013	J	`jnl`	Generalized Wong sequences and their applications to Edmonds' problems. Electron. Colloquium Comput. Complex. Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha
2013	—	`conf`	Improved Inapproximability Results for the Shortest Superstring and Related Problems. CATS Marek Karpinski, Richard Schmied
2013	J	`jnl`	New Inapproximability Bounds for TSP CoRR Marek Karpinski, Michael Lampis, Richard Schmied
2013	B	`conf`	New Inapproximability Bounds for TSP. ISAAC Marek Karpinski, Michael Lampis, Richard Schmied
2013	J	`jnl`	New Inapproximability Bounds for TSP. Electron. Colloquium Comput. Complex. Marek Karpinski, Michael Lampis, Richard Schmied
2013	J	`jnl`	Optimal cuts and partitions in tree metrics in polynomial time. Inf. Process. Lett. Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
2012	J	`jnl`	Approximate Counting of Matchings in Sparse Hypergraphs CoRR Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
2012	J	`jnl`	Approximate Counting of Matchings in Sparse Uniform Hypergraphs CoRR Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
2012	J	`jnl`	Approximating vertex cover in dense hypergraphs. J. Discrete Algorithms Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann
2012	J	`jnl`	Deterministic Polynomial Factoring and Association Schemes CoRR Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena
2012	J	`jnl`	Deterministic Polynomial Factoring and Association Schemes. Electron. Colloquium Comput. Complex. Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena
2012	J	`jnl`	Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. Algorithmica Piotr Berman, Marek Karpinski, Andrzej Lingas
2012	J	`jnl`	Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations CoRR Mikael Gast, Mathias Hauptmann, Marek Karpinski
2012	J	`jnl`	Inapproximability of Dominating Set in Power Law Graphs CoRR Mikael Gast, Mathias Hauptmann, Marek Karpinski
2012	J	`jnl`	On Approximation Lower Bounds for TSP with Bounded Metrics CoRR Marek Karpinski, Richard Schmied
2012	J	`jnl`	On Approximation Lower Bounds for TSP with Bounded Metrics. Electron. Colloquium Comput. Complex. Marek Karpinski, Richard Schmied
2012	J	`jnl`	Optimal Cuts and Bisections on the Real Line in Polynomial Time CoRR Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
2012	J	`jnl`	Optimal Cuts and Partitions in Tree Metrics in Polynomial Time CoRR Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
2012	J	`jnl`	Optimal Cuts and Partitions in Tree Metrics in Polynomial Time. Electron. Colloquium Comput. Complex. Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu
2012	J	`jnl`	Trading GRH for algebra: Algorithms for factoring polynomials and related structures. Math. Comput. Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena
2011	J	`jnl`	Approximating Subdense Instances of Covering Problems. Electron. Notes Discret. Math. Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann
2011	—	`conf`	Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems. APPROX-RANDOM Marek Karpinski, Warren Schudy
2011	J	`jnl`	Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). Dagstuhl Reports Martin E. Dyer, Uriel Feige, Alan M. Frieze, Marek Karpinski
2011	J	`jnl`	Improved Lower Bounds for the Shortest Superstring and Related Problems CoRR Marek Karpinski, Richard Schmied
2011	J	`jnl`	Improved Lower Bounds for the Shortest Superstring and Related Problems. Electron. Colloquium Comput. Complex. Marek Karpinski, Richard Schmied
2011	J	`jnl`	On Systemic Stability of Banking Networks CoRR Piotr Berman, Bhaskar DasGupta, Lakshmi Kaligounder, Marek Karpinski
2011	J	`jnl`	Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs CoRR Marek Karpinski, Richard Schmied, Claus Viehmann
2011	J	`jnl`	Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs. Electron. Colloquium Comput. Complex. Marek Karpinski, Richard Schmied, Claus Viehmann
2011	A*	`conf`	Top-K Color Queries for Document Retrieval. SODA Marek Karpinski, Yakov Nekrich
2010	—	`conf`	A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2. ISAAC (1) Piotr Berman, Marek Karpinski, Alexander Zelikovsky
2010	J	`jnl`	Approximating Subdense Instances of Covering Problems CoRR Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann
2010	J	`jnl`	Approximating Vertex Cover in Dense Hypergraphs CoRR Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann
2010	B	`conf`	Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs. LATIN Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
2010	J	`jnl`	Computational Complexity of the Perfect Matching Problem in Hypergraphs with Subcritical Density. Int. J. Found. Comput. Sci. Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
2010	J	`jnl`	Cycles and paths in edge-colored graphs with given degrees. J. Graph Theory Abdelfattah Abouelaoualim, Kinkar Chandra Das, Wenceslas Fernandez de la Vega, Marek Karpinski, Yannis Manoussakis, Carlos A. J. Martinhon, Rachid Saad
2010	J	`jnl`	Deterministic Polynomial Time Algorithms for Matrix Completion Problems. SIAM J. Comput. Gábor Ivanyos, Marek Karpinski, Nitin Saxena
2010	Misc	`conf`	Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. COCOON Piotr Berman, Marek Karpinski, Andrzej Lingas
2010	J	`jnl`	Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament CoRR Marek Karpinski, Warren Schudy
2010	—	`conf`	Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. ISAAC (1) Marek Karpinski, Warren Schudy
2010	J	`jnl`	Range Reporting for Moving Points on a Grid CoRR Marek Karpinski, J. Ian Munro, Yakov Nekrich
2010	J	`jnl`	The mixing time of Glauber dynamics for coloring regular trees. Random Struct. Algorithms Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski
2010	J	`jnl`	Top-K Color Queries for Document Retrieval CoRR Marek Karpinski, Yakov Nekrich
2009	B	`conf`	1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2. WADS Piotr Berman, Marek Karpinski, Alexander Zelikovsky
2009	J	`jnl`	A Fast Algorithm for Adaptive Prefix Coding. Algorithmica Marek Karpinski, Yakov Nekrich
2009	B	`conf`	Approximating Transitive Reductions for Directed Networks. WADS Piotr Berman, Bhaskar DasGupta, Marek Karpinski
2009	J	`jnl`	Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems CoRR Marek Karpinski, Warren Schudy
2009	J	`jnl`	Deterministic Polynomial Time Algorithms for Matrix Completion Problems CoRR Gábor Ivanyos, Marek Karpinski, Nitin Saxena
2009	J	`jnl`	Deterministic Polynomial Time Algorithms for Matrix Completion Problems. Electron. Colloquium Comput. Complex. Gábor Ivanyos, Marek Karpinski, Nitin Saxena
2009	J	`jnl`	Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications CoRR Piotr Berman, Marek Karpinski, Andrzej Lingas
2009	A*	`conf`	Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. STOC Marek Karpinski, Warren Schudy
2009	B	`conf`	Low-Memory Adaptive Prefix Coding. DCC Travis Gagie, Marek Karpinski, Yakov Nekrich
2009	B	`conf`	Schemes for deterministic polynomial factoring. ISSAC Gábor Ivanyos, Marek Karpinski, Nitin Saxena
2009	Misc	`conf`	Space Efficient Multi-dimensional Range Reporting. COCOON Marek Karpinski, Yakov Nekrich
2009	B	`conf`	The Complexity of Perfect Matching Problems on Dense Hypergraphs. ISAAC Marek Karpinski, Andrzej Rucinski, Edyta Szymanska
2008	—	`conf`	08201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms. Design and Analysis of Randomized and Approximation Algorithms Martin E. Dyer, Mark Jerrum, Marek Karpinski
2008	J	`jnl`	1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two CoRR Piotr Berman, Marek Karpinski, Alexander Zelikovsky
2008	J	`jnl`	1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two. Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski, Alexander Zelikovsky
2008	J	`jnl`	A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two CoRR Piotr Berman, Marek Karpinski, Alexander Zelikovsky
2008	J	`jnl`	Approximating Transitivity in Directed Networks CoRR Piotr Berman, Bhaskar DasGupta, Marek Karpinski
2008	—	`ed.`	Design and Analysis of Randomized and Approximation Algorithms, 11.05. - 16.05.2008 Design and Analysis of Randomized and Approximation Algorithms Martin E. Dyer, Mark Jerrum, Marek Karpinski
2008	J	`jnl`	Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems CoRR Marek Karpinski, Warren Schudy
2008	J	`jnl`	Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems. Electron. Colloquium Comput. Complex. Marek Karpinski, Warren Schudy
2008	J	`jnl`	Low-Memory Adaptive Prefix Coding CoRR Travis Gagie, Marek Karpinski, Yakov Nekrich
2008	J	`jnl`	Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Random Struct. Algorithms Magnus Bordewich, Martin E. Dyer, Marek Karpinski
2008	J	`jnl`	Schemes for Deterministic Polynomial Factoring CoRR Gábor Ivanyos, Marek Karpinski, Nitin Saxena
2008	J	`jnl`	Schemes for Deterministic Polynomial Factoring. Electron. Colloquium Comput. Complex. Gábor Ivanyos, Marek Karpinski, Nitin Saxena
2008	J	`jnl`	Searching for Frequent Colors in Rectangles CoRR Marek Karpinski, Yakov Nekrich
2008	—	`conf`	Searching for Frequent Colors in Rectangles. CCCG Marek Karpinski, Yakov Nekrich
2008	J	`jnl`	Space-Efficient Multi-Dimensional Range Reporting CoRR Marek Karpinski, Yakov Nekrich
2008	J	`jnl`	The Mixing Time of Glauber Dynamics for Colouring Regular Trees CoRR Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski
2008	J	`jnl`	Trading GRH for algebra: algorithms for factoring polynomials and related structures CoRR Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena
2008	J	`jnl`	Trading GRH for algebra: algorithms for factoring polynomials and related structures. Electron. Colloquium Comput. Complex. Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena
2007	J	`jnl`	1.0957-Approximation Algorithm for Random MAX-3SAT. RAIRO Oper. Res. Wenceslas Fernandez de la Vega, Marek Karpinski
2007	J	`jnl`	Approximating Huffman codes in parallel. J. Discrete Algorithms Piotr Berman, Marek Karpinski, Yakov Nekrich
2007	J	`jnl`	Approximating Transitive Reductions for Directed Networks. Electron. Colloquium Comput. Complex. Piotr Berman, Bhaskar DasGupta, Marek Karpinski
2007	J	`jnl`	Computational complexity of some restricted instances of 3-SAT. Discret. Appl. Math. Piotr Berman, Marek Karpinski, Alexander D. Scott
2007	J	`jnl`	Embedding Point Sets into Plane Graphs of Small Dilation. Int. J. Comput. Geom. Appl. Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, Marek Karpinski, Christian Knauer, Andrzej Lingas
2007	J	`jnl`	Optimal trade-off for Merkle tree traversal. Theor. Comput. Sci. Piotr Berman, Marek Karpinski, Yakov Nekrich
2006	A*	`conf`	8/7-approximation algorithm for (1, 2)-TSP. SODA Piotr Berman, Marek Karpinski
2006	B	`conf`	A Fast Algorithm for Adaptive Prefix Coding. ISIT Marek Karpinski, Yakov Nekrich
2006	J	`jnl`	Algorithms for Construction of Optimal and Almost-optimal Length-restricted Codes. Parallel Process. Lett. Marek Karpinski, Yakov Nekrich
2006	J	`jnl`	Approximation Complexity of Nondense Instances of MAX-CUT. Electron. Colloquium Comput. Complex. Wenceslas Fernandez de la Vega, Marek Karpinski
2006	J	`jnl`	Approximation of Global MAX-CSP Problems. Electron. Colloquium Comput. Complex. Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
2006	J	`jnl`	On the Sample Complexity of MAX-CUT. Electron. Colloquium Comput. Complex. Wenceslas Fernandez de la Vega, Marek Karpinski
2006	—	`conf`	Stopping Times, Metrics and Approximate Counting. ICALP (1) Magnus Bordewich, Martin E. Dyer, Marek Karpinski
2006	J	`jnl`	TSP with bounded metrics. J. Comput. Syst. Sci. Lars Engebretsen, Marek Karpinski
2006	J	`jnl`	Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP. Electron. Colloquium Comput. Complex. Wenceslas Fernandez de la Vega, Marek Karpinski
2005	—	`conf`	05201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms. Design and Analysis of Randomized and Approximation Algorithms Martin E. Dyer, Mark Jerrum, Marek Karpinski
2005	J	`jnl`	8/7-Approximation Algorithm for (1,2)-TSP Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski
2005	B	`conf`	Algorithms for Construction of Optimal and Almost-Optimal Length-Restricted Codes. DCC Marek Karpinski, Yakov Nekrich
2005	—	`ed.`	Design and Analysis of Randomized and Approximation Algorithms, 15.05. - 20.05.2005 Design and Analysis of Randomized and Approximation Algorithms Martin E. Dyer, Mark Jerrum, Marek Karpinski
2005	B	`conf`	Embedding Point Sets into Plane Graphs of Small Dilation. ISAAC Annette Ebbers-Baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas
2005	J	`jnl`	Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem. Algorithmica Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky
2005	J	`jnl`	Metric Construction, Stopping Times and Path Coupling. Electron. Colloquium Comput. Complex. Magnus Bordewich, Martin E. Dyer, Marek Karpinski
2005	B	`conf`	On the Complexity of Global Constraint Satisfaction. ISAAC Cristina Bazgan, Marek Karpinski
2005	J	`jnl`	On the computational power of probabilistic and quantum branching program. Inf. Comput. Farid M. Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, Chris Pollett
2005	—	`conf`	Optimal Trade-Off for Merkle Tree Traversal. ICETE (Selected Papers) Piotr Berman, Marek Karpinski, Yakov Nekrich
2005	—	`conf`	Optimal trade-off for merkle tree traversal. ICETE Marek Karpinski, Yakov Nekrich
2005	J	`jnl`	Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs Electron. Colloquium Comput. Complex. Magnus Bordewich, Martin E. Dyer, Marek Karpinski
2005	B	`conf`	Path Coupling Using Stopping Times. FCT Magnus Bordewich, Martin E. Dyer, Marek Karpinski
2005	J	`jnl`	Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. SIAM J. Comput. Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel
2005	A	`conf`	Predecessor Queries in Constant Time?. ESA Marek Karpinski, Yakov Nekrich
2005	A*	`conf`	Tensor decomposition and approximation schemes for constraint satisfaction problems. STOC Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh S. Vempala
2004	J	`jnl`	A Note on Traversing Skew Merkle Trees Electron. Colloquium Comput. Complex. Marek Karpinski, Yakov Nekrich
2004	J	`jnl`	Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs. Fundam. Informaticae Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas
2004	A*	`conf`	Approximation schemes for Metric Bisection and partitioning. SODA Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon
2004	J	`jnl`	Computational Complexity of Some Restricted Instances of 3SAT Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski, Alexander D. Scott
2004	J	`jnl`	Optimal Trade-Off for Merkle Tree Traversal Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski, Yakov Nekrich
2004	J	`jnl`	Work-Efficient Algorithms For The Construction Of Length-Limited Huffman Codes. Parallel Process. Lett. Marek Karpinski, Lawrence L. Larmore, Yakov Nekrich
2003	J	`jnl`	A lower bound for integer multiplication on randomized ordered read-once branching programs. Inf. Comput. Farid M. Ablayev, Marek Karpinski
2003	J	`jnl`	Approximability of Hypergraph Minimum Bisection. Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski
2003	J	`jnl`	Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski, Alex D. Scott
2003	J	`jnl`	Approximation Hardness of Short Symmetric Instances of MAX-3SAT. Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski, Alex D. Scott
2003	A*	`conf`	Approximation schemes for clustering problems. STOC Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani
2003	B	`conf`	Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem. WADS Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky
2003	J	`jnl`	Improved Approximation Lower Bounds on Small Occurrence Optimization Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski
2003	J	`jnl`	Polynomial time approximation schemes for dense instances of minimum constraint satisfaction. Random Struct. Algorithms Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
2003	J	`jnl`	Random sampling and approximation of MAX-CSPs. J. Comput. Syst. Sci. Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
2002	A	`conf`	1.375-Approximation Algorithm for Sorting by Reversals. ESA Piotr Berman, Sridhar Hannenhalli, Marek Karpinski
2002	J	`jnl`	9/8-Approximation Algorithm for Random MAX-3SAT Electron. Colloquium Comput. Complex. Wenceslas Fernandez de la Vega, Marek Karpinski
2002	J	`jnl`	A Polynomial Time Approximation Scheme for Metric MIN-BISECTION Electron. Colloquium Comput. Complex. Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon
2002	J	`jnl`	A Polynomial Time Approximation Scheme for Subdense MAX-CUT Electron. Colloquium Comput. Complex. Wenceslas Fernandez de la Vega, Marek Karpinski
2002	—	`conf`	Approximability of Dense Instances of NEAREST CODEWORD Problem. SWAT Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
2002	A*	`conf`	Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. SODA Béla Csaba, Marek Karpinski, Piotr Krysta
2002	B	`conf`	Approximability of the Minimum Bisection Problem: An Algorithmic Challenge. MFCS Marek Karpinski
2002	J	`jnl`	Approximating Huffman Codes in Parallel Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski, Yakov Nekrich
2002	A*	`conf`	Approximating Huffman Codes in Parallel. ICALP Piotr Berman, Marek Karpinski, Yakov Nekrich
2002	A*	`conf`	Approximating minimum unsatisfiability of linear equations. SODA Piotr Berman, Marek Karpinski
2002	A*	`conf`	Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION. ICALP Piotr Berman, Marek Karpinski
2002	J	`jnl`	Improved approximation of Max-Cut on graphs of bounded degree. J. Algorithms Uriel Feige, Marek Karpinski, Michael Langberg
2002	J	`jnl`	Learning by the Process of Elimination. Inf. Comput. Rusins Freivalds, Marek Karpinski, Carl H. Smith, Rolf Wiehagen
2002	J	`jnl`	On Approximability of Minimum Bisection Problem Electron. Colloquium Comput. Complex. Marek Karpinski
2002	J	`jnl`	On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. J. Comput. Syst. Sci. Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter
2002	J	`jnl`	Parallel Construction of Minimum Redundancy Length-Limited Codes Electron. Colloquium Comput. Complex. Marek Karpinski, Yakov Nekrich
2002	J	`jnl`	Polynomial Time Approximation Schemes for Metric Min-Sum Clustering Electron. Colloquium Comput. Complex. Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani
2002	A*	`conf`	Random sampling and approximation of MAX-CSP problems. STOC Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
2002	J	`jnl`	Randomized splay trees: Theoretical and experimental results. Inf. Process. Lett. Susanne Albers, Marek Karpinski
2001	J	`jnl`	1.375-Approximation Algorithm for Sorting by Reversals Electron. Colloquium Comput. Complex. Piotr Berman, Sridhar Hannenhalli, Marek Karpinski
2001	J	`jnl`	A note on approximating Max-Bisection on regular graphs. Inf. Process. Lett. Uriel Feige, Marek Karpinski, Michael Langberg
2001	J	`jnl`	Approximating Bounded Degree Instances of NP-Hard Problems Electron. Colloquium Comput. Complex. Marek Karpinski
2001	B	`conf`	Approximating Bounded Degree Instances of NP-Hard Problems. FCT Marek Karpinski
2001	J	`jnl`	Approximating Minimum Unsatisfiability of Linear Equations Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski
2001	J	`jnl`	Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski
2001	A*	`conf`	Approximation Hardness of TSP with Bounded Metrics. ICALP Lars Engebretsen, Marek Karpinski
2001	J	`jnl`	Efficient Amplifiers and Bounded Degree Optimization. Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski
2001	J	`jnl`	Improved Approximations for General Minimum Cost Scheduling Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski
2001	J	`jnl`	On BPP versus NPcoNP for ordered read-once branching programs. Theor. Comput. Sci. Farid M. Ablayev, Marek Karpinski, Rustam Mubarakzjanov
2001	B	`conf`	On Computational Power of Quantum Branching Programs. FCT Farid M. Ablayev, Aida Gainutdinova, Marek Karpinski
2001	J	`jnl`	Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction Electron. Colloquium Comput. Complex. Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
2001	A	`conf`	Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. STACS Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel
2001	J	`jnl`	Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems. Algorithmica Marek Karpinski
2001	J	`jnl`	Random Sampling and Approximation of MAX-CSP Problems Electron. Colloquium Comput. Complex. Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski
2000	J	`jnl`	A Note on Approximating MAX-BISECTION on Regular Graphs Electron. Colloquium Comput. Complex. Uriel Feige, Marek Karpinski, Michael Langberg
2000	J	`jnl`	A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs Electron. Colloquium Comput. Complex. Klaus Jansen, Marek Karpinski, Andrzej Lingas
2000	J	`jnl`	Approximability of Dense Instances of NEAREST CODEWORD Problem Electron. Colloquium Comput. Complex. Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski
2000	J	`jnl`	Approximation Algorithms for MAX-BISECTION on Low Degree Reg ular Graphs and Planar Graphs Electron. Colloquium Comput. Complex. Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas
2000	J	`jnl`	Approximation Hardness of TSP with Bounded Metrics Electron. Colloquium Comput. Complex. Lars Engebretsen, Marek Karpinski
2000	J	`jnl`	Improved Approximation of MAX-CUT on Graphs of Bounded Degree Electron. Colloquium Comput. Complex. Uriel Feige, Marek Karpinski, Michael Langberg
2000	J	`jnl`	On-Line Load Balancing for Related Machines Electron. Colloquium Comput. Complex. Piotr Berman, Moses Charikar, Marek Karpinski
2000	J	`jnl`	On-Line Load Balancing for Related Machines. J. Algorithms Piotr Berman, Moses Charikar, Marek Karpinski
2000	J	`jnl`	Polynomial time approximation of dense weighted instances of MAX-CUT. Random Struct. Algorithms Wenceslas Fernandez de la Vega, Marek Karpinski
2000	J	`jnl`	Zero testing of p-adic and modular polynomials. Theor. Comput. Sci. Marek Karpinski, Alfred J. van der Poorten, Igor E. Shparlinski
1999	J	`jnl`	A Note on Las Vegas OBDDs Electron. Colloquium Comput. Complex. Marek Karpinski, Rustam Mubarakzjanov
1999	J	`jnl`	Compact cellular algebras and permutation groups. Discret. Math. Sergei Evdokimov, Marek Karpinski, Ilia N. Ponomarenko
1999	A*	`conf`	On Some Tighter Inapproximability Results (Extended Abstract). ICALP Piotr Berman, Marek Karpinski
1999	J	`jnl`	On the Approximation Hardness of Dense TSP and Other Path Problems. Inf. Process. Lett. Wenceslas Fernandez de la Vega, Marek Karpinski
1999	J	`jnl`	On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials Electron. Colloquium Comput. Complex. Marek Karpinski, Igor E. Shparlinski
1999	—	`conf`	On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials. AAECC Marek Karpinski, Igor E. Shparlinski
1999	J	`jnl`	Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. J. Comput. Syst. Sci. Sanjeev Arora, David R. Karger, Marek Karpinski
1999	B	`conf`	Quantum Finite Multitape Automata. SOFSEM Andris Ambainis, Richard F. Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski
1999	J	`jnl`	Randomized Complexity of Linear Arrangements and Polyhedra Electron. Colloquium Comput. Complex. Marek Karpinski
1999	B	`conf`	Randomized Complexity of Linear Arrangements and Polyhedra. FCT Marek Karpinski
1998	J	`jnl`	A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs Electron. Colloquium Comput. Complex. Farid M. Ablayev, Marek Karpinski
1998	J	`jnl`	Alphabet-Independent Optimal Parallel Search for Three-Dimensional Patterns. Theor. Comput. Sci. Marek Karpinski, Wojciech Rytter
1998	A*	`conf`	An Exponential Lower Bound for Depth 3 Arithmetic Circuits. STOC Dima Grigoriev, Marek Karpinski
1998	J	`jnl`	An exponential lower bound on the size of algebraic decision trees for Max. Comput. Complex. Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao
1998	J	`jnl`	Computing the Additive Complexity of Algebraic Circuits with Root Extracting. SIAM J. Comput. Dima Grigoriev, Marek Karpinski
1998	J	`jnl`	Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs. Discret. Appl. Math. Elias Dahlhaus, Marek Karpinski
1998	J	`jnl`	On Approximation Hardness of Dense TSP and other Path Problems Electron. Colloquium Comput. Complex. Wenceslas Fernandez de la Vega, Marek Karpinski
1998	J	`jnl`	On Approximation Intractability of the Bandwidth Problem Electron. Colloquium Comput. Complex. Gunter Blache, Marek Karpinski, Juergen Wirtgen
1998	J	`jnl`	On Some Tighter Inapproximability Results Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski
1998	J	`jnl`	On Some Tighter Inapproximability Results, Further Improvements Electron. Colloquium Comput. Complex. Piotr Berman, Marek Karpinski
1998	J	`jnl`	On a Sublinear Time Parallel Construction of Optimal Binary Search Trees. Parallel Process. Lett. Marek Karpinski, Wojciech Rytter
1998	J	`jnl`	On the Computational Power of Randomized Branching Programs Electron. Colloquium Comput. Complex. Marek Karpinski
1998	J	`jnl`	On the Power of Randomized Ordered Branching Programs Electron. Colloquium Comput. Complex. Farid M. Ablayev, Marek Karpinski
1998	J	`jnl`	Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT Electron. Colloquium Comput. Complex. Wenceslas Fernandez de la Vega, Marek Karpinski
1998	J	`jnl`	Simulating Threshold Circuits by Majority Circuits. SIAM J. Comput. Mikael Goldmann, Marek Karpinski
1997	J	`jnl`	A Lower Bound for Randomized Algebraic Decision Trees. Comput. Complex. Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
1997	J	`jnl`	An Approximation Algorithm for the Bandwidth Problem on Dense Graphs Electron. Colloquium Comput. Complex. Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky
1997	J	`jnl`	An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions. Nord. J. Comput. Marek Karpinski, Wojciech Rytter, Ayumi Shinohara
1997	J	`jnl`	Approximating Dense Cases of Covering Problems Electron. Colloquium Comput. Complex. Marek Karpinski, Alexander Zelikovsky
1997	—	`conf`	Approximating dense cases of covering problems. Network Design: Connectivity and Facilities Location Marek Karpinski, Alexander Zelikovsky
1997	—	`conf`	Approximating the Volume of General Pfaffian Bodies. Structures in Logic and Computer Science Marek Karpinski, Angus Macintyre
1997	J	`jnl`	Correctness of Constructing Optimal Alphabetic Trees Revisited. Theor. Comput. Sci. Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter
1997	J	`jnl`	Counting Curves and Their Projections. Comput. Complex. Joachim von zur Gathen, Marek Karpinski, Igor E. Shparlinski
1997	B	`conf`	Effects of Kolmogorov Complexity Present in Inductive Inference as Well. ALT Andris Ambainis, Kalvis Apsitis, Cristian Calude, Rusins Freivalds, Marek Karpinski, Tomas Larfeldt, Iveta Sala, Juris Smotrovs
1997	J	`jnl`	Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees. Discret. Comput. Geom. Dima Grigoriev, Marek Karpinski, Nicolai N. Vorobjov Jr.
1997	J	`jnl`	New Approximation Algorithms for the Steiner Tree Problems. J. Comb. Optim. Marek Karpinski, Alexander Zelikovsky
1997	J	`jnl`	On Approximation Hardness of the Bandwidth Problem Electron. Colloquium Comput. Complex. Marek Karpinski, Juergen Wirtgen
1997	B	`conf`	On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. CPM Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter
1997	B	`conf`	On-line Load Balancing for Related Machines. WADS Piotr Berman, Moses Charikar, Marek Karpinski
1997	J	`jnl`	Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks. J. Comput. Syst. Sci. Marek Karpinski, Angus Macintyre
1997	B	`conf`	Polynomial Time Algorithms for Modules over Finite Dimensional Algebras. ISSAC Alexander L. Chistov, Gábor Ivanyos, Marek Karpinski
1997	J	`jnl`	Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems Electron. Colloquium Comput. Complex. Marek Karpinski
1997	—	`conf`	Polynominal Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems. RANDOM Marek Karpinski
1997	J	`jnl`	Randomization and the Computational Power of Analytic and Algebraic Decision Trees. Comput. Complex. Dima Grigoriev, Marek Karpinski, Roman Smolensky
1997	A*	`conf`	Randomized Omega(n STOC Dima Grigoriev, Marek Karpinski
1997	—	`conf`	Weak and Strong Recognition by 2-way Randomized Automata. RANDOM Andris Ambainis, Rusins Freivalds, Marek Karpinski
1996	A*	`conf`	A Lower Bound for Randomized Algebraic Decision Trees. STOC Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
1996	J	`jnl`	Computability of the Additive Complexity of Algebraic Circuits with Root Extracting. Theor. Comput. Sci. Dima Grigoriev, Marek Karpinski
1996	—	`conf`	Efficient Algorithms for Lempel-Zip Encoding (Extended Abstract). SWAT Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter
1996	J	`jnl`	On Randomized versus Deterministic Computation. Theor. Comput. Sci. Marek Karpinski, Rutger Verbeek
1996	J	`jnl`	On Some Approximation Problems Concerning Sparse Polynomials over Finite Fields. Theor. Comput. Sci. Marek Karpinski, Igor E. Shparlinski
1996	A*	`conf`	On the Power of Randomized Branching Programs. ICALP Farid M. Ablayev, Marek Karpinski
1996	B	`conf`	Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract). CPM Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter
1996	J	`jnl`	Randomized Omega(n Electron. Colloquium Comput. Complex. Dima Grigoriev, Marek Karpinski
1996	A*	`conf`	Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees. SODA Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter
1996	J	`jnl`	Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann. Fundam. Informaticae Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko
1995	J	`jnl`	1.757 and 1.267 - Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems Electron. Colloquium Comput. Complex. Marek Karpinski, Alexander Zelikovsky
1995	J	`jnl`	A Lower Bound for Randomized Algebraic Decision Trees Electron. Colloquium Comput. Complex. Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
1995	J	`jnl`	An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX Electron. Colloquium Comput. Complex. Dima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao
1995	—	`conf`	Bounding VC-dimension of neural networks: Progress and prospects. EuroCOLT Marek Karpinski, Angus Macintyre
1995	A*	`conf`	Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. FOCS Dima Grigoriev, Marek Karpinski, Nicolai N. Vorobjov Jr.
1995	A*	`conf`	Lower Time Bounds for Randomized Computation. ICALP Rusins Freivalds, Marek Karpinski
1995	J	`jnl`	New Approximation Algorithms for the Steiner Tree Problems Electron. Colloquium Comput. Complex. Marek Karpinski, Alexander Zelikovsky
1995	J	`jnl`	On Randomized Versus Deterministic Computation Electron. Colloquium Comput. Complex. Marek Karpinski, Rutger Verbeek
1995	A*	`conf`	On real Turing machines that toss coins. STOC Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, Kai Werther
1995	J	`jnl`	On the Power of Randomized Branching Programs Electron. Colloquium Comput. Complex. Farid M. Ablayev, Marek Karpinski
1995	J	`jnl`	Pattern-Matching for Strings with Short Descriptions Electron. Colloquium Comput. Complex. Marek Karpinski, Wojciech Rytter, Ayumi Shinohara
1995	B	`conf`	Pattern-Matching for Strings with Short Descriptions. CPM Marek Karpinski, Wojciech Rytter, Ayumi Shinohara
1995	A*	`conf`	Polynomial bounds for VC dimension of sigmoidal neural networks. STOC Marek Karpinski, Angus Macintyre
1995	A*	`conf`	Polynomial time approximation schemes for dense instances of STOC Sanjeev Arora, David R. Karger, Marek Karpinski
1995	J	`jnl`	Resolution for Quantified Boolean Formulas Inf. Comput. Hans Kleine Büning, Marek Karpinski, Andreas Flögel
1995	J	`jnl`	VC Dimension of Sigmoidal and General Pfaffian Networks Electron. Colloquium Comput. Complex. Marek Karpinski, Angus Macintyre
1994	J	`jnl`	An Algorithm to Learn Read-Once Threshold Formulas, and Transformations Between Learning Models. Comput. Complex. Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski
1994	B	`conf`	An Alphabet-Independent Optimal Parallel Search for Three Dimensional Pattern. CPM Marek Karpinski, Wojciech Rytter
1994	J	`jnl`	An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph. Theor. Comput. Sci. Elias Dahlhaus, Marek Karpinski
1994	A	`conf`	Approaching the 5/4-Approximation for Rectilinear Steiner Trees. ESA Piotr Berman, Ulrich Fößmeier, Marek Karpinski, Michael Kaufmann, Alexander Zelikovsky
1994	A*	`conf`	Co-Learning of Total Recursive Functions. COLT Rusins Freivalds, Marek Karpinski, Carl H. Smith
1994	—	`conf`	Co-learnability and FIN-identifiability of Enumerable Classes of Total Recursive Functions. AII/ALT Rusins Freivalds, Dace Gobleja, Marek Karpinski, Carl H. Smith
1994	J	`jnl`	Computational Complexity of Sparse Rational Interpolation. SIAM J. Comput. Dima Grigoriev, Marek Karpinski, Michael F. Singer
1994	A*	`conf`	Lower Space Bounds for Randomized Computation. ICALP Rusins Freivalds, Marek Karpinski
1994	A*	`conf`	Lower bounds on testing membership to a polyhedron by algebraic decision trees. STOC Dima Grigoriev, Marek Karpinski, Nicolai N. Vorobjov Jr.
1994	B	`conf`	On a Sublinear Time Parallel Construction of Optimal Binary Search Trees. MFCS Marek Karpinski, Wojciech Rytter
1994	J	`jnl`	Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks Electron. Colloquium Comput. Complex. Marek Karpinski, Angus Macintyre
1993	—	`conf`	A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals. AAECC Dima Grigoriev, Marek Karpinski
1993	J	`jnl`	Approximating the Number of Zeroes of a GF[2] Polynomial. J. Algorithms Marek Karpinski, Michael Luby
1993	A*	`conf`	Counting curves and their projections. STOC Joachim von zur Gathen, Marek Karpinski, Igor E. Shparlinski
1993	J	`jnl`	Learning Read-Once Formulas with Queries. J. ACM Dana Angluin, Lisa Hellerstein, Marek Karpinski
1993	J	`jnl`	On Randomized Semi-algebraic Test Complexity. J. Complex. Peter Bürgisser, Marek Karpinski, Thomas Lickteig
1993	A*	`conf`	On Randomized Versus Deterministic Computation. ICALP Marek Karpinski, Rutger Verbeek
1993	J	`jnl`	On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs. J. Algorithms Elias Dahlhaus, Péter Hajnal, Marek Karpinski
1993	A*	`conf`	Simulating threshold circuits by majority circuits. STOC Mikael Goldmann, Marek Karpinski
1993	J	`jnl`	VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions. SIAM J. Comput. Marek Karpinski, Thorsten Werther
1992	J	`jnl`	An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3. Inf. Process. Lett. Elias Dahlhaus, Marek Karpinski, Pierre Kelsen
1992	B	`conf`	Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis. ISSAC Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko
1992	J	`jnl`	Perfect Matching for Regular Graphs is AC°-Hard for the General Matching Problem. J. Comput. Syst. Sci. Elias Dahlhaus, Marek Karpinski
1991	B	`conf`	Algorithms for Sparse Rational Interpolation. ISSAC Dima Grigoriev, Marek Karpinski
1991	A*	`conf`	An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] FOCS Dima Grigoriev, Marek Karpinski
1991	A*	`conf`	Approximating the Number of Zeroes of a GF[2] Polynomial. SODA Marek Karpinski, Michael Luby
1991	B	`conf`	Approximation Algorithms for Counting Problems in Finite Fields. FCT Marek Karpinski
1991	J	`jnl`	On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials Over Finite Fields. Theor. Comput. Sci. Michael Clausen, Andreas W. M. Dress, Johannes Grabmeier, Marek Karpinski
1991	J	`jnl`	Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication. Comput. Complex. Peter Bürgisser, Marek Karpinski, Thomas Lickteig
1990	J	`jnl`	Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields. SIAM J. Comput. Dima Grigoriev, Marek Karpinski, Michael F. Singer
1990	A*	`conf`	Fast Parallel Algorithms for the Clique Separator Decomposition. SODA Elias Dahlhaus, Marek Karpinski, Mark B. Novick
1990	A*	`conf`	Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents FOCS Dima Grigoriev, Marek Karpinski, Michael F. Singer
1990	B	`conf`	On the Complexity of Genuinely Polynomial Computation. MFCS Marek Karpinski, Friedhelm Meyer auf der Heide
1990	B	`conf`	Subclasses of Quantified Boolean Formulas. CSL Andreas Flögel, Marek Karpinski, Hans Kleine Büning
1989	A*	`conf`	An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract) FOCS Elias Dahlhaus, Marek Karpinski
1989	A*	`conf`	Learning Read-Once Formulas Using Membership Queries. COLT Lisa Hellerstein, Marek Karpinski
1989	J	`jnl`	Subtree Isomorphism is NC Reducible to Bipartite Perfect Matching. Inf. Process. Lett. Andrzej Lingas, Marek Karpinski
1988	—	`conf`	A Fast Parallel Algorithm for Computing all Maximal Cliques in a Graph and the Related Problems (Extended Abstract). SWAT Elias Dahlhaus, Marek Karpinski
1988	B	`conf`	Boolean Complexity of Algebraic Interpolation Problems. CSL Marek Karpinski
1988	C	`conf`	Learning Machine for Probabilistically Describable Concepts. ISMIS Marek Karpinski, Zbigniew W. Ras
1988	A*	`conf`	Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs FOCS Elias Dahlhaus, Péter Hajnal, Marek Karpinski
1988	J	`jnl`	Parallel Construction of Perfect Matchings and Hamiltonian Cycles on Dense Graphs. Theor. Comput. Sci. Elias Dahlhaus, Marek Karpinski
1988	J	`jnl`	The computational complexity of graph problems with succinct multigraph representation. ZOR Methods Model. Oper. Res. Marek Karpinski, Klaus W. Wagner
1987	B	`conf`	On the Computational Complexity of Quantified Horn Clauses. CSL Marek Karpinski, Hans Kleine Büning, Peter H. Schmitt
1987	J	`jnl`	On the Monte Carlo Space Constructible Functions and Seperation Results for Probabilistic Complexity Classes Inf. Comput. Marek Karpinski, Rutger Verbeek
1987	—	`conf`	Randomness, Provability, and the Seperation of Monte Carlo Time and Space. Computation Theory and Logic Marek Karpinski, Rutger Verbeek
1987	A*	`conf`	The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract) FOCS Dima Grigoriev, Marek Karpinski
1986	J	`jnl`	On the Power of Two-Way Random Generators and the Impossibility of Deterministic Poly-Space Simulation Inf. Control. Marek Karpinski, Rutger Verbeek
1985	J	`jnl`	Preface Inf. Control. Marek Karpinski, Jan van Leeuwen
1985	J	`jnl`	There Is No Polynomial Deterministic Space Simulation of Probabilistic Space with a Two-Way Random-Tape Generator Inf. Control. Marek Karpinski, Rutger Verbeek
1983	B	`ed.`	Fundamentals of Computation Theory, Proceedings of the 1983 International FCT-Conference, Borgholm, Sweden, August 21-27, 1983 FCT Marek Karpinski
1982	J	`jnl`	Decidability of "Skolem Matrix Emptiness Problem" Entails Constructability of Exact Regular Expression. Theor. Comput. Sci. Marek Karpinski
1980	—	`conf`	On global word definability and constructively definable sets in N CLAAP Marek Karpinski
1979	B	`conf`	Decidability Results on Plane Automata Searching Mazes. FCT Ryszard Danecki, Marek Karpinski
1977	B	`ed.`	Fundamentals of Computation Theory, Proceedings of the 1977 International FCT-Conference, Poznan-Kórnik, Poland, September 19-23, 1977 FCT Marek Karpinski
1977	B	`conf`	The Equivalences Problems for Binary EOL-Systems are Decidable. FCT Marek Karpinski
1976	B	`conf`	Multiplicity Functions on Omega-Automata. MFCS Marek Karpinski
1976	J	`jnl`	Valued Probabilistic Tree Functions. Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys. Marek Karpinski
1975	B	`conf`	Decision Algorithms for Havel's Branching Automata. MFCS Marek Karpinski
1974	J	`jnl`	Free Structure Tree Automata IV. Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys. Marek Karpinski
1974	J	`jnl`	Probablistic Climbing and Sinking Languages. Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys. Marek Karpinski
1974	B	`conf`	Stretching by Probabilistic Tree Automata and Santos Grammars. MFCS Marek Karpinski
1973	J	`jnl`	Free Structure Tree Automata, II: Nondeterminstic and Deterministic Regularity. Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys. Marek Karpinski
1973	J	`jnl`	Free Structure Tree Automata, III: Normalized Climbing Automata. Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys. Marek Karpinski