Free Structure Tree Automata, II: Nondeterminstic and Deterministic Regularity. - Marek Karpinski (Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys., 1973)

Free Structure Tree Automata, III: Normalized Climbing Automata. - Marek Karpinski (Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys., 1973)

Stretching by Probabilistic Tree Automata and Santos Grammars. - Marek Karpinski (MFCS, 1974)

Free Structure Tree Automata IV. - Marek Karpinski (Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys., 1974)

Probablistic Climbing and Sinking Languages. - Marek Karpinski (Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys., 1974)

Decision Algorithms for Havel's Branching Automata. - Marek Karpinski (MFCS, 1975)

Multiplicity Functions on Omega-Automata. - Marek Karpinski (MFCS, 1976)

Valued Probabilistic Tree Functions. - Marek Karpinski (Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys., 1976)

The Equivalences Problems for Binary EOL-Systems are Decidable. - Marek Karpinski (FCT, 1977)

Decidability Results on Plane Automata Searching Mazes. - Ryszard Danecki; Marek Karpinski (FCT, 1979)

On global word definability and constructively definable sets in Nn. - Marek Karpinski (CLAAP, 1980)

Decidability of "Skolem Matrix Emptiness Problem" Entails Constructability of Exact Regular Expression. - Marek Karpinski (Theor. Comput. Sci., 1982)

Preface - Marek Karpinski; Jan van Leeuwen (Inf. Control., 1985)

There Is No Polynomial Deterministic Space Simulation of Probabilistic Space with a Two-Way Random-Tape Generator - Marek Karpinski; Rutger Verbeek (Inf. Control., 1985)

On the Power of Two-Way Random Generators and the Impossibility of Deterministic Poly-Space Simulation - Marek Karpinski; Rutger Verbeek (Inf. Control., 1986)

Randomness, Provability, and the Seperation of Monte Carlo Time and Space. - Marek Karpinski; Rutger Verbeek (Computation Theory and Logic, 1987)

On the Computational Complexity of Quantified Horn Clauses. - Marek Karpinski; Hans Kleine Büning; Peter H. Schmitt (CSL, 1987)

The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract) - Dima Grigoriev; Marek Karpinski (FOCS, 1987)

On the Monte Carlo Space Constructible Functions and Seperation Results for Probabilistic Complexity Classes - Marek Karpinski; Rutger Verbeek (Inf. Comput., 1987)

Boolean Complexity of Algebraic Interpolation Problems. - Marek Karpinski (CSL, 1988)

Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs - Elias Dahlhaus; Péter Hajnal; Marek Karpinski (FOCS, 1988)

Learning Machine for Probabilistically Describable Concepts. - Marek Karpinski; Zbigniew W. Ras (ISMIS, 1988)

A Fast Parallel Algorithm for Computing all Maximal Cliques in a Graph and the Related Problems (Extended Abstract). - Elias Dahlhaus; Marek Karpinski (SWAT, 1988)

The computational complexity of graph problems with succinct multigraph representation. - Marek Karpinski; Klaus W. Wagner (ZOR Methods Model. Oper. Res., 1988)

Parallel Construction of Perfect Matchings and Hamiltonian Cycles on Dense Graphs. - Elias Dahlhaus; Marek Karpinski (Theor. Comput. Sci., 1988)

Learning Read-Once Formulas Using Membership Queries. - Lisa Hellerstein; Marek Karpinski (COLT, 1989)

An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract) - Elias Dahlhaus; Marek Karpinski (FOCS, 1989)

Subtree Isomorphism is NC Reducible to Bipartite Perfect Matching. - Andrzej Lingas; Marek Karpinski (Inf. Process. Lett., 1989)

Subclasses of Quantified Boolean Formulas. - Andreas Flögel; Marek Karpinski; Hans Kleine Büning (CSL, 1990)

Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents - Dima Grigoriev; Marek Karpinski; Michael F. Singer (FOCS, 1990)

On the Complexity of Genuinely Polynomial Computation. - Marek Karpinski; Friedhelm Meyer auf der Heide (MFCS, 1990)

Fast Parallel Algorithms for the Clique Separator Decomposition. - Elias Dahlhaus; Marek Karpinski; Mark B. Novick (SODA, 1990)

Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields. - Dima Grigoriev; Marek Karpinski; Michael F. Singer (SIAM J. Comput., 1990)

Approximation Algorithms for Counting Problems in Finite Fields. - Marek Karpinski (FCT, 1991)

An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] - Dima Grigoriev; Marek Karpinski (FOCS, 1991)

Algorithms for Sparse Rational Interpolation. - Dima Grigoriev; Marek Karpinski (ISSAC, 1991)

Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication. - Peter Bürgisser; Marek Karpinski; Thomas Lickteig (Comput. Complex., 1991)

On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials Over Finite Fields. - Michael Clausen; Andreas W. M. Dress; Johannes Grabmeier; Marek Karpinski (Theor. Comput. Sci., 1991)

Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis. - Dima Grigoriev; Marek Karpinski; Andrew M. Odlyzko (ISSAC, 1992)

An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3. - Elias Dahlhaus; Marek Karpinski; Pierre Kelsen (Inf. Process. Lett., 1992)

Perfect Matching for Regular Graphs is AC°-Hard for the General Matching Problem. - Elias Dahlhaus; Marek Karpinski (J. Comput. Syst. Sci., 1992)

A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals. - Dima Grigoriev; Marek Karpinski (AAECC, 1993)

Learning Read-Once Formulas with Queries. - Dana Angluin; Lisa Hellerstein; Marek Karpinski (J. ACM, 1993)

On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs. - Elias Dahlhaus; Péter Hajnal; Marek Karpinski (J. Algorithms, 1993)

Approximating the Number of Zeroes of a GF[2] Polynomial. - Marek Karpinski; Michael Luby (J. Algorithms, 1993)

On Randomized Semi-algebraic Test Complexity. - Peter Bürgisser; Marek Karpinski; Thomas Lickteig (J. Complex., 1993)

VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions. - Marek Karpinski; Thorsten Werther (SIAM J. Comput., 1993)

Co-learnability and FIN-identifiability of Enumerable Classes of Total Recursive Functions. - Rusins Freivalds; Dace Gobleja; Marek Karpinski; Carl H. Smith (AII/ALT, 1994)

Co-Learning of Total Recursive Functions. - Rusins Freivalds; Marek Karpinski; Carl H. Smith (COLT, 1994)

An Alphabet-Independent Optimal Parallel Search for Three Dimensional Pattern. - Marek Karpinski; Wojciech Rytter (CPM, 1994)

Approaching the 5/4-Approximation for Rectilinear Steiner Trees. - Piotr Berman; Ulrich Fößmeier; Marek Karpinski; Michael Kaufmann 001; Alexander Zelikovsky (ESA, 1994)

Lower Space Bounds for Randomized Computation. - Rusins Freivalds; Marek Karpinski (ICALP, 1994)

Lower bounds on testing membership to a polyhedron by algebraic decision trees. - Dima Grigoriev; Marek Karpinski; Nicolai N. Vorobjov Jr. (STOC, 1994)

An Algorithm to Learn Read-Once Threshold Formulas, and Transformations Between Learning Models. - Nader H. Bshouty; Thomas R. Hancock; Lisa Hellerstein; Marek Karpinski (Comput. Complex., 1994)

Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks - Marek Karpinski; Angus Macintyre (Electron. Colloquium Comput. Complex., 1994)

Computational Complexity of Sparse Rational Interpolation. - Dima Grigoriev; Marek Karpinski; Michael F. Singer (SIAM J. Comput., 1994)

An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph. - Elias Dahlhaus; Marek Karpinski (Theor. Comput. Sci., 1994)

Bounding VC-dimension of neural networks: Progress and prospects. - Marek Karpinski; Angus Macintyre (EuroCOLT, 1995)

Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. - Dima Grigoriev; Marek Karpinski; Nicolai N. Vorobjov Jr. (FOCS, 1995)

Lower Time Bounds for Randomized Computation. - Rusins Freivalds; Marek Karpinski (ICALP, 1995)

Polynomial time approximation schemes for dense instances of NP-hard problems. - Sanjeev Arora; David R. Karger; Marek Karpinski (STOC, 1995)

On real Turing machines that toss coins. - Felipe Cucker; Marek Karpinski; Pascal Koiran; Thomas Lickteig; Kai Werther (STOC, 1995)

1.757 and 1.267 - Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems - Marek Karpinski; Alexander Zelikovsky (Electron. Colloquium Comput. Complex., 1995)

Pattern-Matching for Strings with Short Descriptions - Marek Karpinski; Wojciech Rytter; Ayumi Shinohara (Electron. Colloquium Comput. Complex., 1995)

New Approximation Algorithms for the Steiner Tree Problems - Marek Karpinski; Alexander Zelikovsky (Electron. Colloquium Comput. Complex., 1995)

On the Power of Randomized Branching Programs - Farid M. Ablayev; Marek Karpinski (Electron. Colloquium Comput. Complex., 1995)

VC Dimension of Sigmoidal and General Pfaffian Networks - Marek Karpinski; Angus Macintyre (Electron. Colloquium Comput. Complex., 1995)

Resolution for Quantified Boolean Formulas - Hans Kleine Büning; Marek Karpinski; Andreas Flögel (Inf. Comput., 1995)

Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract). - Leszek Gasieniec; Marek Karpinski; Wojciech Plandowski; Wojciech Rytter (CPM, 1996)

Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees. - Marek Karpinski; Lawrence L. Larmore; Wojciech Rytter (SODA, 1996)

Efficient Algorithms for Lempel-Zip Encoding (Extended Abstract). - Leszek Gasieniec; Marek Karpinski; Wojciech Plandowski; Wojciech Rytter (SWAT, 1996)

Randomized Omega(n2) Lower Bound for Knapsack - Dima Grigoriev; Marek Karpinski (Electron. Colloquium Comput. Complex., 1996)

Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann. - Dima Grigoriev; Marek Karpinski; Andrew M. Odlyzko (Fundam. Informaticae, 1996)

Computability of the Additive Complexity of Algebraic Circuits with Root Extracting. - Dima Grigoriev; Marek Karpinski (Theor. Comput. Sci., 1996)

On Some Approximation Problems Concerning Sparse Polynomials over Finite Fields. - Marek Karpinski; Igor E. Shparlinski (Theor. Comput. Sci., 1996)

On Randomized versus Deterministic Computation. - Marek Karpinski; Rutger Verbeek (Theor. Comput. Sci., 1996)

Effects of Kolmogorov Complexity Present in Inductive Inference as Well. - Andris Ambainis; Kalvis Apsitis; Cristian Calude; Rusins Freivalds; Marek Karpinski; Tomas Larfeldt; Iveta Sala; Juris Smotrovs (ALT, 1997)

Approximating the Volume of General Pfaffian Bodies. - Marek Karpinski; Angus Macintyre (Structures in Logic and Computer Science, 1997)

Polynomial Time Algorithms for Modules over Finite Dimensional Algebras. - Alexander L. Chistov; Gábor Ivanyos; Marek Karpinski (ISSAC, 1997)

Weak and Strong Recognition by 2-way Randomized Automata. - Andris Ambainis; Rusins Freivalds; Marek Karpinski (RANDOM, 1997)

Polynominal Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems. - Marek Karpinski (RANDOM, 1997)

Counting Curves and Their Projections. - Joachim von zur Gathen; Marek Karpinski; Igor E. Shparlinski (Comput. Complex., 1997)

A Lower Bound for Randomized Algebraic Decision Trees. - Dima Grigoriev; Marek Karpinski; Friedhelm Meyer auf der Heide; Roman Smolensky (Comput. Complex., 1997)

Randomization and the Computational Power of Analytic and Algebraic Decision Trees. - Dima Grigoriev; Marek Karpinski; Roman Smolensky (Comput. Complex., 1997)

Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees. - Dima Grigoriev; Marek Karpinski; Nicolai N. Vorobjov Jr. (Discret. Comput. Geom., 1997)

Approximating Dense Cases of Covering Problems - Marek Karpinski; Alexander Zelikovsky (Electron. Colloquium Comput. Complex., 1997)

An Approximation Algorithm for the Bandwidth Problem on Dense Graphs - Marek Karpinski; Juergen Wirtgen; Alexander Zelikovsky (Electron. Colloquium Comput. Complex., 1997)

Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems - Marek Karpinski (Electron. Colloquium Comput. Complex., 1997)

On Approximation Hardness of the Bandwidth Problem - Marek Karpinski; Juergen Wirtgen (Electron. Colloquium Comput. Complex., 1997)

Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks. - Marek Karpinski; Angus Macintyre (J. Comput. Syst. Sci., 1997)

An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions. - Marek Karpinski; Wojciech Rytter; Ayumi Shinohara (Nord. J. Comput., 1997)

Correctness of Constructing Optimal Alphabetic Trees Revisited. - Marek Karpinski; Lawrence L. Larmore; Wojciech Rytter (Theor. Comput. Sci., 1997)

An Exponential Lower Bound for Depth 3 Arithmetic Circuits. - Dima Grigoriev; Marek Karpinski (STOC, 1998)

An exponential lower bound on the size of algebraic decision trees for Max. - Dima Grigoriev; Marek Karpinski; Andrew Chi-Chih Yao (Comput. Complex., 1998)

Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs. - Elias Dahlhaus; Marek Karpinski (Discret. Appl. Math., 1998)

On the Power of Randomized Ordered Branching Programs - Farid M. Ablayev; Marek Karpinski (Electron. Colloquium Comput. Complex., 1998)

A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs - Farid M. Ablayev; Marek Karpinski (Electron. Colloquium Comput. Complex., 1998)

On Approximation Intractability of the Bandwidth Problem - Gunter Blache; Marek Karpinski; Juergen Wirtgen (Electron. Colloquium Comput. Complex., 1998)

On Some Tighter Inapproximability Results - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 1998)

On the Computational Power of Randomized Branching Programs - Marek Karpinski (Electron. Colloquium Comput. Complex., 1998)

Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT - Wenceslas Fernandez de la Vega; Marek Karpinski (Electron. Colloquium Comput. Complex., 1998)

On Some Tighter Inapproximability Results, Further Improvements - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 1998)

On a Sublinear Time Parallel Construction of Optimal Binary Search Trees. - Marek Karpinski; Wojciech Rytter (Parallel Process. Lett., 1998)

Simulating Threshold Circuits by Majority Circuits. - Mikael Goldmann; Marek Karpinski (SIAM J. Comput., 1998)

Computing the Additive Complexity of Algebraic Circuits with Root Extracting. - Dima Grigoriev; Marek Karpinski (SIAM J. Comput., 1998)

Alphabet-Independent Optimal Parallel Search for Three-Dimensional Patterns. - Marek Karpinski; Wojciech Rytter (Theor. Comput. Sci., 1998)

On Some Tighter Inapproximability Results (Extended Abstract). - Piotr Berman; Marek Karpinski (ICALP, 1999)

Quantum Finite Multitape Automata. - Andris Ambainis; Richard F. Bonner; Rusins Freivalds; Marats Golovkins; Marek Karpinski (SOFSEM, 1999)

Compact cellular algebras and permutation groups. - Sergei Evdokimov 001; Marek Karpinski; Ilia N. Ponomarenko (Discret. Math., 1999)

A Note on Las Vegas OBDDs - Marek Karpinski; Rustam Mubarakzjanov (Electron. Colloquium Comput. Complex., 1999)

Randomized Complexity of Linear Arrangements and Polyhedra - Marek Karpinski (Electron. Colloquium Comput. Complex., 1999)

On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials - Marek Karpinski; Igor E. Shparlinski (Electron. Colloquium Comput. Complex., 1999)

On the Approximation Hardness of Dense TSP and Other Path Problems. - Wenceslas Fernandez de la Vega; Marek Karpinski (Inf. Process. Lett., 1999)

Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. - Sanjeev Arora; David R. Karger; Marek Karpinski (J. Comput. Syst. Sci., 1999)

On-Line Load Balancing for Related Machines - Piotr Berman; Moses Charikar; Marek Karpinski (Electron. Colloquium Comput. Complex., 2000)

Improved Approximation of MAX-CUT on Graphs of Bounded Degree - Uriel Feige; Marek Karpinski; Michael Langberg (Electron. Colloquium Comput. Complex., 2000)

Approximation Algorithms for MAX-BISECTION on Low Degree Reg ular Graphs and Planar Graphs - Marek Karpinski; Miroslaw Kowaluk; Andrzej Lingas (Electron. Colloquium Comput. Complex., 2000)

A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs - Klaus Jansen; Marek Karpinski; Andrzej Lingas (Electron. Colloquium Comput. Complex., 2000)

Approximation Hardness of TSP with Bounded Metrics - Lars Engebretsen; Marek Karpinski (Electron. Colloquium Comput. Complex., 2000)

Approximability of Dense Instances of NEAREST CODEWORD Problem - Cristina Bazgan; Wenceslas Fernandez de la Vega; Marek Karpinski (Electron. Colloquium Comput. Complex., 2000)

Zero testing of p-adic and modular polynomials. - Marek Karpinski; Alfred J. van der Poorten; Igor E. Shparlinski (Theor. Comput. Sci., 2000)

On Computational Power of Quantum Branching Programs. - Farid M. Ablayev; Aida Gainutdinova; Marek Karpinski (FCT, 2001)

Approximating Minimum Unsatisfiability of Linear Equations - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction - Cristina Bazgan; Wenceslas Fernandez de la Vega; Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

Approximating Bounded Degree Instances of NP-Hard Problems - Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

1.375-Approximation Algorithm for Sorting by Reversals - Piotr Berman; Sridhar Hannenhalli; Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

Efficient Amplifiers and Bounded Degree Optimization. - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

Improved Approximations for General Minimum Cost Scheduling - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

Random Sampling and Approximation of MAX-CSP Problems - Noga Alon; Wenceslas Fernandez de la Vega; Ravi Kannan; Marek Karpinski (Electron. Colloquium Comput. Complex., 2001)

A note on approximating Max-Bisection on regular graphs. - Uriel Feige; Marek Karpinski; Michael Langberg (Inf. Process. Lett., 2001)

On BPP versus NPcoNP for ordered read-once branching programs. - Farid M. Ablayev; Marek Karpinski; Rustam Mubarakzjanov (Theor. Comput. Sci., 2001)

Approximability of the Minimum Bisection Problem: An Algorithmic Challenge. - Marek Karpinski (MFCS, 2002)

Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. - Béla Csaba; Marek Karpinski; Piotr Krysta (SODA, 2002)

Approximating Huffman Codes in Parallel - Piotr Berman; Marek Karpinski; Yakov Nekrich (Electron. Colloquium Comput. Complex., 2002)

Polynomial Time Approximation Schemes for Metric Min-Sum Clustering - Wenceslas Fernandez de la Vega; Marek Karpinski; Claire Kenyon; Yuval Rabani (Electron. Colloquium Comput. Complex., 2002)

Parallel Construction of Minimum Redundancy Length-Limited Codes - Marek Karpinski; Yakov Nekrich (Electron. Colloquium Comput. Complex., 2002)

A Polynomial Time Approximation Scheme for Metric MIN-BISECTION - Wenceslas Fernandez de la Vega; Marek Karpinski; Claire Kenyon (Electron. Colloquium Comput. Complex., 2002)

A Polynomial Time Approximation Scheme for Subdense MAX-CUT - Wenceslas Fernandez de la Vega; Marek Karpinski (Electron. Colloquium Comput. Complex., 2002)

On Approximability of Minimum Bisection Problem - Marek Karpinski (Electron. Colloquium Comput. Complex., 2002)

9/8-Approximation Algorithm for Random MAX-3SAT - Wenceslas Fernandez de la Vega; Marek Karpinski (Electron. Colloquium Comput. Complex., 2002)

Learning by the Process of Elimination. - Rusins Freivalds; Marek Karpinski; Carl H. Smith; Rolf Wiehagen (Inf. Comput., 2002)

Randomized splay trees: Theoretical and experimental results. - Susanne Albers; Marek Karpinski (Inf. Process. Lett., 2002)

On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. - Piotr Berman; Marek Karpinski; Lawrence L. Larmore; Wojciech Plandowski; Wojciech Rytter (J. Comput. Syst. Sci., 2002)

Approximation schemes for clustering problems. - Wenceslas Fernandez de la Vega; Marek Karpinski; Claire Kenyon; Yuval Rabani (STOC, 2003)

Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem. - Marek Karpinski; Ion I. Mandoiu; Alexander Olshevsky; Alexander Zelikovsky (WADS, 2003)

Improved Approximation Lower Bounds on Small Occurrence Optimization - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2003)

Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT - Piotr Berman; Marek Karpinski; Alex D. Scott (Electron. Colloquium Comput. Complex., 2003)

Approximation Hardness of Short Symmetric Instances of MAX-3SAT. - Piotr Berman; Marek Karpinski; Alex D. Scott (Electron. Colloquium Comput. Complex., 2003)

Approximability of Hypergraph Minimum Bisection. - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2003)

A lower bound for integer multiplication on randomized ordered read-once branching programs. - Farid M. Ablayev; Marek Karpinski (Inf. Comput., 2003)

Random sampling and approximation of MAX-CSPs. - Noga Alon; Wenceslas Fernandez de la Vega; Ravi Kannan; Marek Karpinski (J. Comput. Syst. Sci., 2003)

Approximation schemes for Metric Bisection and partitioning. - Wenceslas Fernandez de la Vega; Marek Karpinski; Claire Kenyon (SODA, 2004)

Computational Complexity of Some Restricted Instances of 3SAT - Piotr Berman; Marek Karpinski; Alexander D. Scott (Electron. Colloquium Comput. Complex., 2004)

A Note on Traversing Skew Merkle Trees - Marek Karpinski; Yakov Nekrich (Electron. Colloquium Comput. Complex., 2004)

Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs. - Marek Karpinski; Miroslaw Kowaluk; Andrzej Lingas (Fundam. Informaticae, 2004)

Work-Efficient Algorithms For The Construction Of Length-Limited Huffman Codes. - Marek Karpinski; Lawrence L. Larmore; Yakov Nekrich (Parallel Process. Lett., 2004)

05201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms. - Martin E. Dyer; Mark Jerrum; Marek Karpinski (Design and Analysis of Randomized and Approximation Algorithms, 2005)

Predecessor Queries in Constant Time?. - Marek Karpinski; Yakov Nekrich (ESA, 2005)

Path Coupling Using Stopping Times. - Magnus Bordewich; Martin E. Dyer; Marek Karpinski (FCT, 2005)

Optimal trade-off for merkle tree traversal. - Marek Karpinski; Yakov Nekrich (ICETE, 2005)

On the Complexity of Global Constraint Satisfaction. - Cristina Bazgan; Marek Karpinski (ISAAC, 2005)

Tensor decomposition and approximation schemes for constraint satisfaction problems. - Wenceslas Fernandez de la Vega; Marek Karpinski; Ravi Kannan; Santosh S. Vempala (STOC, 2005)

Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem. - Marek Karpinski; Ion I. Mandoiu; Alexander Olshevsky; Alexander Zelikovsky (Algorithmica, 2005)

Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs - Magnus Bordewich; Martin E. Dyer; Marek Karpinski (Electron. Colloquium Comput. Complex., 2005)

8/7-Approximation Algorithm for (1,2)-TSP - Piotr Berman; Marek Karpinski (Electron. Colloquium Comput. Complex., 2005)

Metric Construction, Stopping Times and Path Coupling. - Magnus Bordewich; Martin E. Dyer; Marek Karpinski (Electron. Colloquium Comput. Complex., 2005)

On the computational power of probabilistic and quantum branching program. - Farid M. Ablayev; Aida Gainutdinova; Marek Karpinski; Cristopher Moore; Chris Pollett (Inf. Comput., 2005)

Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. - Klaus Jansen; Marek Karpinski; Andrzej Lingas; Eike Seidel (SIAM J. Comput., 2005)

Stopping Times, Metrics and Approximate Counting. - Magnus Bordewich; Martin E. Dyer; Marek Karpinski (ICALP (1), 2006)

8/7-approximation algorithm for (1, 2)-TSP. - Piotr Berman; Marek Karpinski (SODA, 2006)

Approximation Complexity of Nondense Instances of MAX-CUT. - Wenceslas Fernandez de la Vega; Marek Karpinski (Electron. Colloquium Comput. Complex., 2006)

On the Sample Complexity of MAX-CUT. - Wenceslas Fernandez de la Vega; Marek Karpinski (Electron. Colloquium Comput. Complex., 2006)

Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP. - Wenceslas Fernandez de la Vega; Marek Karpinski (Electron. Colloquium Comput. Complex., 2006)

Approximation of Global MAX-CSP Problems. - Wenceslas Fernandez de la Vega; Ravi Kannan; Marek Karpinski (Electron. Colloquium Comput. Complex., 2006)

TSP with bounded metrics. - Lars Engebretsen; Marek Karpinski (J. Comput. Syst. Sci., 2006)

Algorithms for Construction of Optimal and Almost-optimal Length-restricted Codes. - Marek Karpinski; Yakov Nekrich (Parallel Process. Lett., 2006)

Computational complexity of some restricted instances of 3-SAT. - Piotr Berman; Marek Karpinski; Alexander D. Scott (Discret. Appl. Math., 2007)

Approximating Transitive Reductions for Directed Networks. - Piotr Berman; Bhaskar DasGupta; Marek Karpinski (Electron. Colloquium Comput. Complex., 2007)

Embedding Point Sets into Plane Graphs of Small Dilation. - Annette Ebbers-Baumann; Ansgar Grüne; Rolf Klein; Marek Karpinski; Christian Knauer; Andrzej Lingas (Int. J. Comput. Geom. Appl., 2007)

1.0957-Approximation Algorithm for Random MAX-3SAT. - Wenceslas Fernandez de la Vega; Marek Karpinski (RAIRO Oper. Res., 2007)

Optimal trade-off for Merkle tree traversal. - Piotr Berman; Marek Karpinski; Yakov Nekrich (Theor. Comput. Sci., 2007)

Searching for Frequent Colors in Rectangles. - Marek Karpinski; Yakov Nekrich (CCCG, 2008)

08201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms. - Martin E. Dyer; Mark Jerrum; Marek Karpinski (Design and Analysis of Randomized and Approximation Algorithms, 2008)

The Mixing Time of Glauber Dynamics for Colouring Regular Trees - Leslie Ann Goldberg; Mark Jerrum; Marek Karpinski (CoRR, 2008)

Approximating Transitivity in Directed Networks - Piotr Berman; Bhaskar DasGupta; Marek Karpinski (CoRR, 2008)

A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two - Piotr Berman; Marek Karpinski; Alexander Zelikovsky (CoRR, 2008)

1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two. - Piotr Berman; Marek Karpinski; Alexander Zelikovsky (Electron. Colloquium Comput. Complex., 2008)

Schemes for Deterministic Polynomial Factoring. - Gábor Ivanyos; Marek Karpinski; Nitin Saxena 001 (Electron. Colloquium Comput. Complex., 2008)

Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems. - Marek Karpinski; Warren Schudy (Electron. Colloquium Comput. Complex., 2008)

Path coupling using stopping times and counting independent sets and colorings in hypergraphs. - Magnus Bordewich; Martin E. Dyer; Marek Karpinski (Random Struct. Algorithms, 2008)

Space Efficient Multi-dimensional Range Reporting. - Marek Karpinski; Yakov Nekrich (COCOON, 2009)

Low-Memory Adaptive Prefix Coding. - Travis Gagie; Marek Karpinski; Yakov Nekrich (DCC, 2009)

The Complexity of Perfect Matching Problems on Dense Hypergraphs. - Marek Karpinski; Andrzej Rucinski 001; Edyta Szymanska (ISAAC, 2009)

1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2. - Piotr Berman; Marek Karpinski; Alexander Zelikovsky (WADS, 2009)

A Fast Algorithm for Adaptive Prefix Coding. - Marek Karpinski; Yakov Nekrich (Algorithmica, 2009)

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications - Piotr Berman; Marek Karpinski; Andrzej Lingas (CoRR, 2009)

A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2. - Piotr Berman; Marek Karpinski; Alexander Zelikovsky (ISAAC (1), 2010)

Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. - Marek Karpinski; Warren Schudy (ISAAC (1), 2010)

Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs. - Marek Karpinski; Andrzej Rucinski 001; Edyta Szymanska (LATIN, 2010)

Range Reporting for Moving Points on a Grid - Marek Karpinski; J. Ian Munro; Yakov Nekrich (CoRR, 2010)

Computational Complexity of the Perfect Matching Problem in Hypergraphs with Subcritical Density. - Marek Karpinski; Andrzej Rucinski 001; Edyta Szymanska (Int. J. Found. Comput. Sci., 2010)

Cycles and paths in edge-colored graphs with given degrees. - Abdelfattah Abouelaoualim; Kinkar Chandra Das; Wenceslas Fernandez de la Vega; Marek Karpinski; Yannis Manoussakis; Carlos A. J. Martinhon; Rachid Saad (J. Graph Theory, 2010)

The mixing time of Glauber dynamics for coloring regular trees. - Leslie Ann Goldberg; Mark Jerrum; Marek Karpinski (Random Struct. Algorithms, 2010)

Deterministic Polynomial Time Algorithms for Matrix Completion Problems. - Gábor Ivanyos; Marek Karpinski; Nitin Saxena 001 (SIAM J. Comput., 2010)

Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems. - Marek Karpinski; Warren Schudy (APPROX-RANDOM, 2011)

Top-K Color Queries for Document Retrieval. - Marek Karpinski; Yakov Nekrich (SODA, 2011)

On Systemic Stability of Banking Networks - Piotr Berman; Bhaskar DasGupta; Lakshmi Kaligounder; Marek Karpinski (CoRR, 2011)

Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). - Martin E. Dyer; Uriel Feige; Alan M. Frieze; Marek Karpinski (Dagstuhl Reports, 2011)

Improved Lower Bounds for the Shortest Superstring and Related Problems. - Marek Karpinski; Richard Schmied (Electron. Colloquium Comput. Complex., 2011)

Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs. - Marek Karpinski; Richard Schmied; Claus Viehmann (Electron. Colloquium Comput. Complex., 2011)

Approximating Subdense Instances of Covering Problems. - Jean Cardinal; Marek Karpinski; Richard Schmied; Claus Viehmann (Electron. Notes Discret. Math., 2011)

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. - Piotr Berman; Marek Karpinski; Andrzej Lingas (Algorithmica, 2012)

Approximate Counting of Matchings in Sparse Hypergraphs - Marek Karpinski; Andrzej Rucinski 001; Edyta Szymanska (CoRR, 2012)

Optimal Cuts and Bisections on the Real Line in Polynomial Time - Marek Karpinski; Andrzej Lingas; Dzmitry Sledneu (CoRR, 2012)

Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations - Mikael Gast; Mathias Hauptmann; Marek Karpinski (CoRR, 2012)

On Approximation Lower Bounds for TSP with Bounded Metrics. - Marek Karpinski; Richard Schmied (Electron. Colloquium Comput. Complex., 2012)

Approximating vertex cover in dense hypergraphs. - Jean Cardinal; Marek Karpinski; Richard Schmied; Claus Viehmann (J. Discrete Algorithms, 2012)

Trading GRH for algebra: Algorithms for factoring polynomials and related structures. - Gábor Ivanyos; Marek Karpinski; Lajos Rónyai; Nitin Saxena 001 (Math. Comput., 2012)

Approximate Counting of Matchings in Sparse Uniform Hypergraphs. - Edyta Szymanska; Marek Karpinski; Andrzej Rucinski 001 (ANALCO, 2013)

Improved Inapproximability Results for the Shortest Superstring and Related Problems. - Marek Karpinski; Richard Schmied (CATS, 2013)

Algorithmic Perspectives of Network Transitive Reduction Problems and their Applications to Synthesis and Analysis of Biological Networks. - Satabdi Aditya; Bhaskar DasGupta; Marek Karpinski (CoRR, 2013)

Approximation Hardness of Graphic TSP on Cubic Graphs. - Marek Karpinski; Richard Schmied (Electron. Colloquium Comput. Complex., 2013)

Optimal cuts and partitions in tree metrics in polynomial time. - Marek Karpinski; Andrzej Lingas; Dzmitry Sledneu (Inf. Process. Lett., 2013)

Approximate Counting of Matchings in (3, 3)-Hypergraphs. - Andrzej Dudek; Marek Karpinski; Andrzej Rucinski 001; Edyta Szymanska (SWAT, 2014)

On the Computational Complexity of Measuring Global Stability of Banking Networks. - Piotr Berman; Bhaskar DasGupta; Lakshmi Kaligounder; Marek Karpinski (Algorithmica, 2014)

A QPTAS for the Base of the Number of Triangulations of a Planar Point Set. - Marek Karpinski; Andrzej Lingas; Dzmitry Sledneu (CoRR, 2014)

Limits of CSP Problems and Efficient Parameter Testing. - Marek Karpinski; Roland Markó (CoRR, 2014)

Complexity of Nondeterministic Graph Parameter Testing. - Marek Karpinski; Roland Markó (CoRR, 2014)

Approximate Counting of Matchings in (3,3)-Hypergraphs. - Andrzej Dudek; Marek Karpinski; Andrzej Rucinski 001; Edyta Szymanska (Electron. Colloquium Comput. Complex., 2014)

Deterministic polynomial factoring and association schemes. - Manuel Arora; Gábor Ivanyos; Marek Karpinski; Nitin Saxena 001 (LMS J. Comput. Math., 2014)

Node Expansions and Cuts in Gromov-hyperbolic Graphs. - Bhaskar DasGupta; Marek Karpinski; Nasim Mobasheri; Farzane Yahyanejad (CoRR, 2015)

Approximability of TSP on Power Law Graphs. - Mikael Gast; Mathias Hauptmann; Marek Karpinski (CoRR, 2015)

On the Approximability of Independent Set Problem on Power Law Graphs. - Mathias Hauptmann; Marek Karpinski (CoRR, 2015)

On the Complexity of Nondeterministically Testable Hypergraph Parameters. - Marek Karpinski; Roland Markó (CoRR, 2015)

Explicit Bounds for Nondeterministically Testable Hypergraph Parameters. - Marek Karpinski; Roland Markó (CoRR, 2015)

Complexity of Symbolic and Numerical Problems (Dagstuhl Seminar 15242). - Peter Bürgisser; Felipe Cucker; Marek Karpinski; Nicolai N. Vorobjov Jr. (Dagstuhl Reports, 2015)

Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies. - Marek Karpinski (Electron. Colloquium Comput. Complex., 2015)

Generalized Wong sequences and their applications to Edmonds' problems. - Gábor Ivanyos; Marek Karpinski; Youming Qiao; Miklos Santha (J. Comput. Syst. Sci., 2015)

New inapproximability bounds for TSP. - Marek Karpinski; Michael Lampis; Richard Schmied (J. Comput. Syst. Sci., 2015)

Nearly tight approximation bounds for vertex cover on dense k-uniform k-partite hypergraphs. - Marek Karpinski; Richard Schmied; Claus Viehmann (J. Discrete Algorithms, 2015)

Inapproximability of dominating set on power law graphs. - Mikael Gast; Mathias Hauptmann; Marek Karpinski (Theor. Comput. Sci., 2015)

Tropical Dominating Sets in Vertex-Coloured Graphs. - 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 (WALCOM, 2016)

Approximation Complexity of Max-Cut on Power Law Graphs. - Mikael Gast; Mathias Hauptmann; Marek Karpinski (CoRR, 2016)

Identity Testing from High Powers of Polynomials of Large Degree over Finite Fields. - Marek Karpinski; Igor E. Shparlinski (CoRR, 2017)

Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications. - Bhaskar DasGupta; Marek Karpinski; Nasim Mobasheri; Farzane Yahyanejad (Algorithmica, 2018)

Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields. - Gábor Ivanyos; Marek Karpinski; Miklos Santha; Nitin Saxena 001; Igor E. Shparlinski (Algorithmica, 2018)

Identity testing and interpolation from high powers of polynomials of large degree over finite fields. - Marek Karpinski; László Mérai; Igor E. Shparlinski (J. Complex., 2018)

Tropical dominating sets in vertex-coloured graphs. - Jean-Alexandre Anglès d'Auriac; Csilla Bujtás; Abdelhakim El Maftouhi; Marek Karpinski; Yannis Manoussakis; Leandro Montero; N. Narayanan 001; Laurent Rosaz; Johan Thapper; Zsolt Tuza (J. Discrete Algorithms, 2018)

A QPTAS for the base of the number of crossing-free structures on a planar point set. - Marek Karpinski; Andrzej Lingas; Dzmitry Sledneu (Theor. Comput. Sci., 2018)

Dense Steiner problems: Approximation algorithms and inapproximability. - Marek Karpinski; Mateusz Lewandowski; Syed Mohammad Meesum; Matthias Mnich (CoRR, 2020)

Noisy polynomial interpolation modulo prime powers. - Marek Karpinski; Igor E. Shparlinski (J. Complex., 2021)