Marek Karpinski

Approximation of Global MAX-CSP Problems (2008)

W. Fern, Marek Karpinski

We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear...

Federal Republic of Germany AND (2008)

Dima Yu. Grigoriev, Marek Karpinski, Michael F. Singer

In [DG 891, the authors show that many results concerning the problem of efficient interpolation of k-sparse multivariate polynomials can be formulated and proved in the general setting of k-sparse...

TSP with bounded metrics (2008)

Lars Engebretsen, Marek Karpinski, Marek Karpinski

Abstract. The general asymmetric TSP with triangle inequality is known to be ap-proximable only within logarithmic factors. In this paper we study the asymmetric and symmetric TSP problems with...

Stopping Times, Metrics and Approximate Counting (2008)

Magnus Bordewich, Marek Karpinski

Abstract. In this paper we examine the importance of the choice of metric in path coupling, and its relationship to stopping time analysis. We give strong evidence that stopping time analysis is no...

On the Computational Power of Probabilistic and Quantum Branching Programs (Revised Version) (2008)

Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, Christopher Pollett

In this paper we show that one-qubit polynomial time computations are as powerful as NC 1 circuits. More generally, we define syntactic models for quantum and stochastic branching programs of bounded...

Tensor Decomposition and Approximation Schemes for Constraint Satisfaction Problems ∗ (2008)

W. Fern, Marek Karpinski, Santosh Vempala

The only general class of MAX-rCSP problems for which Polynomial Time Approximation Schemes (PTAS) are known are the dense problems. In this paper, we give PTAS’s for a much larger class of...

Tensor Decomposition and Approximation Schemes for Constraint Satisfaction Problems ABSTRACT W. Fernandez de la Vega ∗ (2008)

Marek Karpinski, Ravi Kannan, Santosh Vempala Σ

The only general class of MAX-rCSP problems for which Polynomial Time Approximation Schemes (PTAS) are known are the dense problems. In this paper, we give PTAS’s for a much larger class of...

08201 Abstracts Collection -- Design and Analysis of Randomized and Approximation Algorithms (2008)

Dyer, Martin E., Jerrum, Mark, Karpinski, Marek

From 11.05.08 to 16.05.08, the Dagstuhl Seminar 08201 ``Design and Analysis of Randomized and Approximation Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss...

z (2007)

Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter

We consider the complexity of problems related to 2-dimensional texts (2d-texts) described succinctly. In a succinct description, larger rectangular sub-texts are defined in terms of smaller parts in...

1 (2007)

Weak and Strong Recognition by 2-way Randomized Automata (2007)

We obtain new lower bounds on the number of non zeros of sparse polynomials and give a fully polynomial time (ffl; ffi) approximation algorithm for the number of non-zeros of multivariate sparse...

Andris Ambainis, Rusins Freivalds, Marek Karpinski

. Languages weakly recognized by a Monte Carlo 2-way nite automaton with n states are proved to be strongly recognized by a Monte Carlo 2-way nite automaton with n O(n) states. This improves...

Computability of the Additive Complexity of Algebraic Circuits with Root Extracting (2007)

Quadratic Randomized Lower Bound for the Knapsack Problem (2007)

We design an algorithm for computing the generalized (algebraic circuits with root extracting, cf. [P 81], [J 81], [GSY 93]) additive complexity of any rational function. It is the first...

Dima Grigoriev, Marek Karpinski, Marek Karpinski

We prove \Omega\Gamma n 2 ) complexity lower bound for the general model of randomized computation trees solving the Knapsack Problem, and more generally Restricted Integer Programming. This is also...

Learning by the Process of Elimination (2007)

Rusins Freivalds, Marek Karpinski, Carl H. Smith, Rolf Wiehagen, Sherlock Holmes

The process of elimination is a fundamental component of many learning processes. In order to understand the nature of elimination, herein we study an extreme model of learning from examples where...

Read-Once Threshold Formulas, Justifying Assignments, and Generic Transformations (2007)

Revised Version Nader, Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski

We present a membership query (i.e. interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of boolean threshold functions. Using a generic transformation from...

Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication (2007)

Peter Burgisser, Marek Karpinski, Thomas Lickteig

We define the complexity of a computational problem given by a relation using the model of a computation tree with Ostrowski complexity measure. To a sequence of problems we assign an exponent...

On the Complexity of Genuinely Polynomial Computation (2007)

Randomized Complexity of Linear Arrangements and Polyhedra (2007)

We present separation results on genuinely (or strongly) time bounded sequential, parallel and non-deterministic complexity classes defined by RAMs with fixed set of arithmetic operations. In...

Computing the Additive Complexity of Algebraic Circuits with Root Extracting (2007)

We survey some of the recent results on the complexity of recognizing n--dimensional linear arrangements and convex polyhedra by randomized algebraic decision trees. We give also a number of concrete...

A Generalization of Wilkie's Theorem of the Complement, and an Application to Pfaffian Closure (2007)

We design an algorithm for computing the generalized (algebraic circuits with root extracting, cf. [P 81], [J 81], [GSY 93]) additive complexity of any rational function. It is the first...

Marek Karpinski, Angus Macintyre, Marek Karpinski (bonn, Angus Macintyre (edinburgh

Using a modification of Wilkie's recent proof of o-minimality for Pfaffian functions, we give an invariant characterization of o-minimal expansions of IR. We apply this to construct the Pfaffian...

Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees (2007)

Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter

A sublinear time subquadratic work parallel algorithm for construction of an optimal binary search tree, in a special case of practical interest, namely where the frequencies of items to be stored...

Randomized Ω(n²) Lower Bound for Knapsack (2007)

Parallel Construction of Minimum Redundancy Length-Limited Codes (2007)

We prove \Omega\Gamma n 2 ) complexity lower bound for the general model of randomized computation trees solving the Knapsack Problem, and more generally Restricted Integer Programming. This is the...

Abstract. This paper presents new results on parallel constructions of the length-limited prex-free codes with the minimum redundancy. We describe an algorithm for the construction of length-limited...

x (2007)

Randomized splay trees: theoretical and experimental results (2007)

Let k be a fixed integer. We consider the problem of partitioning an input set of points endowed with a distance function into k clusters. We give polynomial time approximation schemes for the...

Susanne Albers, Marek Karpinski

Splay trees are self-organizing binary search trees that were introduced by Sleator and Tarjan [12]. In this paper we present the first randomized variant of these trees. The new algorithm for...

Approximation Schemes for Metric Minimum Bisection and Partitioning (2007)

We design polynomial time approximation schemes (PTASs) for Metric MINBISECTION, i.e. dividing a given nite metric space into two halves so as to minimize the sum of distances across the cut. The...

y (2007)

Approximating Huffman Codes in Parallel Piotr Berman (2007)

We design a polynomial time approximation scheme (PTAS) for the problem of Metric MIN-BISECTION of dividing a given nite metric space into two halves so as to minimize the sum of distances across...

Improved Approximations for General Minimum Cost Scheduling Piotr Berman (2007)

In this paper we present some new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements...

y Abstract. We give improved trade-off results on approximating general minimum cost scheduling problems.

2 (2007)

Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel

Abstract. The Max-Bisection and Min-Bisection problems are to nd a partition of the vertices of a graph into two equal size subsets that respectively maximizes or minimizes the number of edges with...

y (2007)

z Abstract. We design the rst polynomial time approximation schemes (PTASs) for the problem of Metric MIN-BISECTION of dividing a given nite metric space into two halves so as to minimize the sum of...

z (2007)

Approximating Optimal Binary Trees in Parallel Piotr Berman (2007)

We give polynomial time approximation schemes for the problem of partitioning an input set of n points into a xed number k of clusters so as to minimize the sum over all clusters of the total...

1.0957 - Approximation algorithm for Random MAX-3SAT (2007)

In this paper we present new results on an approximate construction of Huffman trees. Our algorithms match asymptotically the time and work needed by known sorting algorithms. For example, we show...

Karpinski, Marek

International Journal of Computational Geometry & Applications c ○ World Scientific Publishing Company EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION (2006)

Annette Ebbers-baumann, Ansgar Grüne, Rolf Klein, Marek Karpinski, Christian Knauer, A. Ebbers-baumann, ...

Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question...

International Journal of Computational Geometry & Applications c ○ World Scientific Publishing Company EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION (2006)

Annette Ebbers-baumann, Ansgar Grüne, Rolf Klein, Marek Karpinski, Christian Knauer

Communicated by Li Zhang Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on...

8/7-approximation algorithm for (1,2)-TSP (2006)

Metric Construction, Stopping Times and Path Coupling (2005)

We design a polynomial time 8/7-approximation algorithm for the Traveling Salesman Problem in which all distances are either one or two. This improves over the best known approximation factor for...

Bordewich, Magnus, Dyer, Martin, Karpinski, Marek

In this paper we examine the importance of the choice of metric in path coupling, and the relationship of this to \emph{stopping time analysis}. We give strong evidence that stopping time analysis is...

Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs (2005)

Bordewich, Magnus, Dyer, Martin, Karpinski, Marek

We give a new method for analysing the mixing time of a Markov chain using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for...

On the complexity of global constraint satisfaction (2005)

Cristina Bazgan, Marek Karpinski

We study the computational complexity of decision and optimization problems that may be expressed as boolean contraint satisfaction problem with the global cardinality constraints. In this paper we...

Embedding Point Sets into Plane Graphs of Small Dilation (2005)

Annette Ebbers-Baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas

Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S?EvenforasetS as simple as five points evenly placed on the circle, this question seems...

Path coupling using stopping times (2005)

Magnus Bordewich, Marek Karpinski

Abstract. We analyse the mixing time of Markov chains using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent...

Path coupling using stopping times and counting independent sets and colourings in hypergraphs (2005)

Magnus Bordewich, Martin Dyer, Marek Karpinski

Abstract We give a new method for analysing the mixing time of a Markov chain using path couplingwith stopping times. We apply this approach to two hypergraph problems. We show that the Glauber...

Embedding point sets into plane graphs of small dilation (2005)

Annette Ebbers-baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas

Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question...

Path coupling using stopping times and counting independent sets and colourings in hypergraphs (2005)

Magnus Bordewich, Martin Dyer, Marek Karpinski

We give a new method for analysing the mixing time of a Markov chain using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for...

On the complexity of global constraint satisfaction (2005)

Cristina Bazgan, Marek Karpinski

Abstract. We study the computational complexity of decision and optimization problems that may be expressed as boolean contraint satisfaction problem with the global cardinality constraints. In this...

05201 Abstracts Collection -- Design and Analysis of Randomized and Approximation Algorithms (2005)

Dyer, Martin, Jerrum, Mark, Karpinski, Marek

From 15.05.05 to 20.05.05, the Dagstuhl Seminar 05201 ``Design and Analysis of Randomized and Approximation Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss...

On Computational Power of Quantum Branching Programs (2003)

Ablayev, Farid, Gainutdinova, Aida, Karpinski, Marek

In this paper we study a model of a Quantum Branching Program (QBP) and investigate its computational power. We prove a general lower bound on the width of read-once QBPs, which we show to be almost...

A.: Improved approximation algorithms for the quality of service steiner tree problem (2003)

Marek Karpinski, Ion I. M, Er Olshevsky

A.: Improved approximation algorithms for the quality of service steiner tree problem (2003)

Marek Karpinski, Ion I. Măndoiu, Er Olshevsky

Abstract. The Quality of Service Multicast Tree Problem is a generalization of the Steiner tree problem which appears in the context of multimedia multicast and network design. In this...

A.: Improved approximation algorithms for the quality of service steiner tree problem (2003)

Marek Karpinski, Ioni. Măndoiu, Er Olshevsky

Abstract. The Quality of Service Steiner Tree Problem is a generalization of the Steiner problem which appears in the context of multimedia multicast and network design. In this generalization, each...

A.: Improved approximation algorithms for the quality of service steiner tree problem (2003)

Marek Karpinski, Ion I. Măndoiu, Er Olshevsky

Abstract. The Quality of Service Multicast Tree Problem is a generalization of the Steiner tree problem which appears in the context of multimedia multicast and network design. In this...

Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems (2002)

Csaba,Bela, Krysta,Piotr, Karpinski,Marek

Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems (2002)

Csaba, Bela, Krysta, Piotr, Karpinski, Marek

Approximating minimum unsatisfiability of linear equations (2002)

A polynomial time approximation scheme for metric MIN-BISECTION (2002)

We consider the following optimization problem: given a system of m linear equations in n variables over a certain field, a feasible solution is any assignment of values to the variables, and the...

Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems (2002)

We design a polynomial time approximation scheme (PTAS) for the problem of Metric MIN-BISECTION of dividing a given finite metric space into two halves so as to minimize the sum of distances across...

Marek Karpinski, Piotr Krysta

We study the approximability of dense and sparse instances of the following problems: the minimum 2-edge-connected (2-EC) and 2-vertex-connected (2-VC) spanning subgraph, metric TSP with distances 1...

A polynomial time approximation scheme for subdense MAX-CUT (2002)

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION, ECCC (2002)

We prove that the subdense instances of MAX-CUT of average degree n=logn) posses a polynomial time approximation scheme (PTAS). We extend this result also to show that the instances of general 2-ary...

On Approximability of Minimum Bisection Problem (2002)

We consider bounded occurrence (degree) instances of a minimum constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for graphs. MIN-LIN2 is an optimization problem for a given system...

Approximating Huffman Codes in Parallel (2002)

We survey some recent results on the complexity of computing approximate solutions for instances of the Minimum Bisection problem and formulate some intriguing and still open questions about the...

Piotr Berman, Marek Karpinski, Yakov Nekrich

In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is...

Parallel Construction of the Minimum Redundancy Length-Limited Codes (2002)

Approximation Schemes for Clustering Problems in Finite Metrics and High Dimensional Spaces (2002)

This paper presents new results on the construction of the lengthlimited prefix-free codes with the minimum redundancy. We describe an algorithm for the construction of length-limited codes that...

A Polynomial Time Approximation Scheme for Subdense MAX-CUT (2002)

We give polynomial time approximation schemes (PTASs) for the problem of partitioning an input set of n points into a fixed number k of clusters so as to minimize the sum over all clusters of the sum...

9/8-Approximation Algorithm for Random MAX-3SAT (2002)

We prove that the subdense instances of MAX-CUT of average degree Omega(n/log n) posses a polynomial time approximation scheme (PTAS). We extend this result also to show that the instances of general...

Approximability of the Minimum Bisection Problem: An Algorithmic Challenge (2002)

We prove that MAX-3SAT can be approximated in polynomial time within a factor 9/8 on random instances.

Polynomial Time Approximation Schemes for Metric Min-Sum Clustering (2002)

We survey some recent results on the complexity of computing approximate solutions for instances of the Minimum Bisection problem and formulate some very intriguing and still open questions about the...

Approximating bounded degree instances of NP-hard problems (2001)

We give polynomial time approximation schemes for the problem of partitioning an input set of n points into a fixed number k of clusters so as to minimize the sum over all clusters of the total...

Approximation hardness of TSP with bounded metrics (2001)

We present some of the recent results on computational complexity of approximating bounded degree combinatorial optimization problems. In particular, we present the best up to now known explicit...

Lars Engebretsen, Marek Karpinski

Abstract. The general asymmetric TSP with triangle inequality is known to be approximable only within an O(log n) factor, and is also known to be approximable within a constant factor as soon as the...

Random Sampling and Approximation of MAX-CSP Problems (2001)

Noga Alon, Ravi Kannan, Marek Karpinski

We present a new efficient sampling method for approximating r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on n variables up to an additive error . We prove a new general paradigm...

Random Sampling and Approximation of MAX-CSP Problems (2001)

Noga Alon, Ravi Kannan, Marek Karpinski

We present a new efficient sampling method for approximating r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on n variables up to an additive error . We prove a new general paradigm...

Improved Approximations for General Minimum Cost Scheduling (2001)

Approximating Minimum (2001)

We give improved trade-off results on approximating general minimum cost scheduling problems.

Unsatisfiability Of Linear, Marek Karpinski

We consider the following optimization problem: given a system of m linear equations in n variables over a certain field, a feasible solution is any assignment of values to the variables, and the...

Approximation hardness of TSP with bounded metrics (2001)

Lars Engebretsen, Marek Karpinski

Abstract. The general asymmetric (and metric) TSP is known to be approximable only to within an O(log n) factor, and is also known to be approximable within a constant factoras soon as the metric is...

Improved approximation of Max-Cut on graphs of bounded degree (2001)

Approximating Bounded Degree Instances of NP-Hard Problems (2001)

Let ff ' 0:87856 denote the best approximation ratio currently known for the Max Cut problem on general graphs [GW95]. We consider a semidefinite relaxation of the Max Cut problem, round it...

1.375-Approximation Algorithm for Sorting by Reversals (2001)

We present some of the recent results on computational complexity of approximating bounded degree combinatorial optimization problems. In particular, we present the best up to now known explicit...

Piotr Berman, Sridhar Hannenhalli, Marek Karpinski

Analysis of genomes evolving by inversions leads to a general combinatorial problem of Sorting by Reversals, MIN-SBR, the problem of sorting a permutation by a minimum number of reversals. This...

Improved approximation of Max-Cut on graphs of bounded degree (2000)

A Note on Approximating MAX-BISECTION on Regular Graphs (2000)

We analyze the addition of a simple local improvement step to various known randomized approximation algorithms. Let ff ' 0:87856 denote the best approximation ratio currently known for the Max...

A Note on Approximating MAX-BISECTION on Regular Graphs (2000)

We design a 0:795 approximation algorithm for the Max-Bisection problem restricted to regular graphs. In the case of three regular graphs our results imply an approximation ratio of 0:834. 1

Quantum finite multitape automata (1999)

We design a 0:795 approximation algorithm for the Max-Bisection problem restricted to regular graphs. In the case of three regular graphs our results imply an approximation ratio of 0:834.

Ambainis, Andris, Bonner, Richard, Freivalds, Rusins, Golovkins, Marats, Karpinski, Marek

Quantum finite automata were introduced by C.Moore, J.P. Crutchfield, and by A.Kondacs and J.Watrous. This notion is not a generalization of the deterministic finite automata. Moreover, it was proved...

A lower bound for integer multiplication on randomized ordered read-once branching programs (1999)

Quantum Finite Multitape Automata (1999)

We prove an exponential lower bound (2

Andris Ambainis, Richard Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski, Andris Ambainis (berkeley, ...

Quantum finite automata were introduced by C. Moore, J. P. Crutchfield [MC 97], and by A. Kondacs and J. Watrous [KW 97]. This notion is not a generalization of the deterministic finite automata....

Randomized Complexity of Linear Arrangements and Polyhedra (1999)

By Marek Karpinski, Marek Karpinski

We survey some of the recent results on the complexity of recognizing n--dimensional linear arrangements and convex polyhedra by randomized algebraic decision trees. We give also a number of concrete...

On Some Tighter Inapproximability Results (1999)

On The Computational Hardness Of Testing Square-Freeness Of Sparse Polynomials (1999)

We give a number of improved inapproximability results, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems like MAX2SAT and E2-LIN-2, and...

Marek Karpinski And, Marek Karpinski, Igor Shparlinski

. We show that deciding square-freeness of a sparse univariate polynomial over ZZ and over the algebraic closure of a finite field IFq of p elements is NP-hard. We also discuss some related open...

On The Computational Hardness Of Testing Square-Freeness Of Sparse Polynomials (1999)

R.Mubarakzjanov, Some separation problems on randomized OBDDs (1998)

. We show that deciding square-freeness of a sparse univariate polynomial over ZZ and over the algebraic closure of a finite field IFq of p elements is NP-hard. We also discuss some related open...

Marek Karpinski, Rustam Mubarakzjanov

We investigate the relationships between complexity classes of Boolean functions that are computable by polynomial size branching programs. In the first part of this paper, we consider different...

An Exponential Lower Bound for Depth 3 Arithmetic Circuits (1998)

Dima Grigoriev Marek, Marek Karpinski

We prove the first exponential lower bound on the size of any depth 3 arithmetic circuit with unbounded fanin computing an explicit function (the determinant) over an arbitrary finite field. This...

A Note on Las Vegas OBDDs (1998)

Marek Karpinski Rustam, Marek Karpinski, Rustam Mubarakzjanov

We prove that the error-free (Las Vegas) randomized OBDDs are computationally equivalent to the deterministic OBDDs. In contrast, it is known the same is not true for the Las Vegas read-once...

On Some Tighter Inapproximability Results (1998)

Piotr Berman Marek, Marek Karpinski

We prove a number of improved inaproximability results, including the best up to date explicit approximation thresholds for MIS problem of bounded degree, bounded occurrences MAX-2SAT, and bounded...

A Note on Las Vegas OBDDs (1998)

Marek Karpinski Rustam, Marek Karpinski, Rustam Mubarakzjanov

We prove that the error-free (Las Vegas) randomized OBDDs are computationally equivalent to the deterministic OBDDs. In contrast, it is known the same is not true for Las Vegas read-once branching...

An Exponential Lower Bound for Depth 3 Arithmetic Circuits (1998)

On BPP versus NP[coNP for Ordered Read-Once Branching Programs (1998)

We prove the first exponential lower bound on the size of any depth 3 arithmetic circuit with unbounded fanin computing an explicit function (the determinant) over an arbitrary finite field. This...

Farid Ablayev, Marek Karpinski, Rustam Mubarakzjanov

We investigate the relationship between probabilistic and nondeterministic complexity classes PP , BPP , NP and coNP for the ordered read-once branching programs (OBDDs) . We exhibit two explicit...

A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs (1998)

Farid Ablayev Marek, Marek Karpinski

We prove an exponential lower bound (2\Omega\Gamma n= log n) ) on the size of any randomized ordered read-once branching program computing integer multiplication. Our proof depends on proving a new...

On Some Tighter Inapproximability Results, Further Improvements (1998)

NP-Hardness of the Bandwidth Problem on Dense Graphs (1998)

Improved inaproximability results are given, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems, like MAX-2SAT and E2-LIN-2, and problems in...

Marek Karpinski, Jürgen Wirtgen

The bandwidth problem is the problem of numbering the vertices of a given graph G such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long and...

Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems (1998)

A Note on Las Vegas OBDDs (1998)

We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many NP-hard optimization problems, including maximum cut, graph...

Marek Karpinski, Rustam Mubarakzjanov

We prove that the error-free (Las Vegas) randomized OBDDs are computationally equivalent to the deterministic OBDDs. In contrast, it is known the same is not true for the Las Vegas read-once...

On the Computation Power of Randomized Branching Programs (1998)

Randomized OBDDs and Model Checking (1998)

We survey some upper and lower bounds established recently on the sizes of randomized branching programs computing explicit boolean functions. In particular, we display boolean functions on which...

A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs, ECCC TR98011 (1998)

: We present some recent results on the computational power and the basic manipulation properties of the randomized OBDDs (or equivalently, randomized read-once ordered branching programs). We...

On the complexity of pattern matching for highly compressed texts (1997)

Abstract We prove an exponential lower bound 2\Omega (n = log n) on the size of any randomized ordered read-once branching program computing integer multiplication. Our proof depends on proving a new...

Berman, Piotr, Karpinski, Marek, Larmore, Lawrence L., Plandowski, Wojciech, Rytter, Wojciech

Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems (1997)

Polynomial bounds for VC dimension of sigmoidal and general pfaffian neural networks (1997)

We survey recent results on the existence of polynomial time approximation schemes for some dense instances of NP-hard combinatorial optimization problems. We indicate further some inherent limits...

Approximating Dense Cases of Covering Problems (1997)

Abstract. We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, that the VC Dimension...

Randomization and the Computational Power of Analytic and Algebraic Decision Trees (1997)

We study dense cases of several covering problems. An instance of the set cover problem with m sets is dense if there is ffl ? 0 such that any element belongs to at least fflm sets. We show that the...

Dima Grigoriev Marek, Marek Karpinski, Roman Smolensky

We introduce a new powerful method for proving lower bounds on randomized and deterministic analytic decision trees, and give direct applications of our results towards some concrete geometric...

On-line Load Balancing for Related Machines (1997)

Piotr Berman, Moses Charikar, Marek Karpinski

this paper appeared in Proceedings of WADS 97, LNCS 1272, SpringerVerlag, 1997, 116-125.

An Approximation Algorithm for the Bandwidth Problem on Dense Graphs (1997)

Marek Karpinski, Jürgen Wirtgen, Alex Zelikovsky

The bandwidth problem is the problem of numbering the vertices of a given graph G such that the maximum difference between two numbers of adjacent vertices is minimal. The problem is known to be...

On Approximation Intractability of the Bandwidth Problem (1997)

Gunter Blache, Marek Karpinski, Jürgen Wirtgen

The bandwidth problem is the problem of enumerating the vertices of a given graph G such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long...

On Approximation Hardness of the Bandwidth Problem (1997)

Marek Karpinski, Jurgen Wirtgen

The bandwidth problem is the problem of enumerating the vertices of a given graph G such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long...

On-line Load Balancing for Related Machines (1997)

Piotr Berman Moses, Moses Charikar, Marek Karpinski

We consider the problem of scheduling permanent jobs on related machines in an on-line fashion. We design a new algorithm that achieves the competitive ratio of 3+ p 8 5:828 for the deterministic...

An Efficient Pattern-Matching Algorithm For Strings With Short Descriptions (1997)

Marek Karpinski, Wojciech Rytter

. We investigate the time complexity of the pattern matching problem for strings which are succinctly described in terms of straight-line programs, in which the constants are symbols and the only...

NP-Hardness of the Bandwidth Problem on Dense Graphs (1997)

Marek Karpinski, Jürgen Wirtgen

The bandwidth problem is the problem of numbering the vertices of a given graph G such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long and...

Zero Testing of p-adic and Modular Polynomials (1997)

Complexity of Deciding Solvability of Polynomial Equations over p-adic Integers (1997)

We obtain new algorithms to test if a given multivariate polynomial over p-adic fields is identical to zero. We also consider zero testing of polynomials in residue rings. The results complement a...

Alexander Chistov Marek, Marek Karpinski

Consider a system of polynomial equations in n variables of degrees less than d with integer coefficients with the lengths less than M . We show using the construction close to smooth stratification...

Polynomial Time Algorithms for Modules Over Finite Dimensional Algebras (1997)

Alexander Chistov, Gábor Ivanyos, Marek Karpinski

We present polynomial time algorithms for some fundamental tasks from representation theory of finite dimensional algebras. These involve testing (and constructing) isomorphisms of modules as well as...

An Approximation Algorithm for the Bandwidth Problem on Dense Graphs (1997)

Marek Karpinski, Jürgen Wirtgen, A. Zelikovsky

The bandwidth problem is the problem of numbering the vertices of a given graph G such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history...

o-Minimal Expansions of the Real Field: A Characterization, and an Application to Pfaffian Closure (1997)

Marek Karpinski, Angus Macintyre, Marek Karpinski (bonn, Angus Macintyre (oxford

Using a modification of Wilkie's recent proof of o-minimality for Pfaffian functions, we gave an invariant characterization of o-minimal expansions of IR. We apply this to construct the Pfaffian...

Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems (1997)

Approximating Dense Cases of Covering Problems (1997)

We survey recent results on the existence of polynomial time approximation schemes for some dense instances of NP-hard optimization problems. We indicate further some inherent limits for existence of...

Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems (1997)

We study dense cases of several covering problems. An instance of the set cover problem with m sets is dense if there is ffl ? 0 such that any element belongs to at least fflm sets. We show that the...

An Approximation Algorithm for the Bandwidth Problem on Dense Graphs (1997)

We overview recent results on the existence of polynomial time approximation schemes for some dense instances of NP-hard optimization problems. We indicate further some inherent limits for existence...

Marek Karpinski, Jurgen Wirtgen, Alex Zelikovsky

The bandwidth problem is the problem of numbering the vertices of a given graph G such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history...

Randomization and the Computational Power of Analytic and Algebraic Decision Trees (1997)

Approximating Dense Cases of Covering Problems (1997)

We introduce a new powerful method for proving lower bounds on randomized and deterministic analytic decision trees, and give direct applications of our results towards some concrete geometric...

Marek Karpinski, Alexander Zelikovsky, Er Zelikovsky

. We study dense instances of several covering problems. An instance of the set cover problem with m sets is dense if there is ffl ? 0 such that any element of the ground set X belongs to at least...

A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs (1997)

On the Power of Randomized Ordered Branching Programs (1997)

We prove an exponential lower bound 2\Omega\Gamma n= log n) on the size of any randomized ordered read-once branching program computing integer multiplication. Our proof depends on proving a new...

On Approximation Hardness of the Bandwidth Problem (1997)

We define the notion of a randomized branching program in the natural way similar to the definition of a randomized circuit. We exhibit an explicit boolean function fn : f0; 1g n ! f0; 1g for which...

Marek Karpinski, Jürgen Wirtgen

The bandwidth problem is the problem of enumerating the vertices of a given graph G such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long...

On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts (1997)

Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter

this paper to lack polynomial time algorithms

An Approximation Algorithm for the Bandwidth Problem on Dense Graphs (1997)

Marek Karpinski, Jurgen Wirtgen, Alex Zelikovsky

The bandwidth problem is the problem of numbering the vertices of a given graph G such that the maximum di erence between two numbers of adjacent vertices is minimal. The problem is known to be...

On the power of randomized branching programs (1996)

A lower bound for randomized algebraic decision trees (1996)

We define the notion of a randomized branching program in the natural way similar to the definition of a randomized circuit. We exhibit an explicit function fn for which we prove that: 1) f n can be...

On the Power of Randomized Branching Programs (1996)

We prove the first nontrivial (and superlinear) lower bounds on the depth of randomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and...

Correctness of Constructing Optimal Alphabetic Trees Revisited (1996)

We define the notion of a randomized branching program in the natural way similar to the definition of a randomized circuit. We exhibit an explicit function fn for which we prove that: 1) f n can be...

Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter

Several new observations which lead to new correctness proofs of two known algorithms (HuTucker and Garsia-Wachs) for construction of optimal alphabetic trees are presented. A generalized version of...

Lower Bound, Dima Grigoriev, Marek Karpinski

We prove \Omega\Gamma n 2 ) complexity lower bound for the general model of randomized computation trees solving the Knapsack Problem, and more generally Restricted Integer Programming. This is the...

A Lower Bound for Randomized Algebraic Decision Trees (1996)

Dima Grigoriev Marek, Marek Karpinski, Roman Smolensky

We prove the first nontrivial (and superlinear) lower bounds on the depth of randomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and...

A Lower Bound for Randomized Algebraic Decision Trees (1996)

Dima Grigoriev Marek, Marek Karpinski, Roman Smolensky

We extend the lower bounds on the depth of algebraic decision trees to the case of randomized algebraic decision trees (with two-sided error) for languages being finite unions of hyperplanes and the...

Lower Bound For, Dima Grigoriev, Marek Karpinski

We prove \Omega\Gamma n 2 ) complexity lower bound for the general model of randomized computation trees solving the Knapsack Problem, and more generally Restricted Integer Programming. This is the...

Randomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach (Extended Abstract) (1996)

Extended Abstract, Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter

) Leszek Gasieniec Marek Karpinski y Wojciech Plandowski z Wojciech Rytter x TR-96-021 June 1996 Abstract Denote by LZ(w) the coded form of a string w produced by Lempel-Ziv encoding algorithm. We...

The Complexity of Two-Dimensional Compressed Pattern Matching (1996)

Piotr Berman Marek, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter

We study computational complexity of two-dimensional compressed pattern matching problems. Among other things, we design an efficient randomized algorithm for the equality problem of two compressed...

A Lower Bound for Randomized Algebraic Decision Trees (1996)

Efficient Algorithms for Lempel-Ziv Encoding (1996)

We extend the lower bounds on the depth of algebraic decision trees to the case of randomized algebraic decision trees (with two-sided error) for languages being finite unions of hyperplanes and the...

Exte Nd Ed, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter

) Leszek G¸asieniec 1 ? Marek Karpinski 2 ?? Wojciech Plandowski 3 ??? Wojciech Rytter 3 y 1 Max-Planck Institut fur Informatik, Im Stadtwald, Saarbrucken D-66123, Germany. 2 Dept. of Computer...

The Complexity of Two-Dimensional Compressed Pattern-Matching (1996)

Piotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter

We consider the complexity of problems for highly compressed 2-dimensional texts: compressed pattern-matching (when the pattern is not compressed and the text is compressed) and fully compressed...

A Lower Bound for Randomized Algebraic Decision Trees (1996)

A Lower Bound for Randomized Algebraic Decision Trees (1996)

We extend the lower bounds on the depth of algebraic decision trees to the case of randomized algebraic decision trees (with twosided error) for languages being finite unions of hyperplanes and the...

Dima Grigoriev Marek, Marek Karpinski, Roman Smolensky

We extend the lower bounds on the depth of algebraic decision trees to the case of randomized algebraic decision trees (with two-sided error) for languages being finite unions of hyperplanes and the...

Lower Bound For, Dima Grigoriev, Marek Karpinski

We prove \Omega\Gamma n 2 ) complexity lower bound for the general model of randomized computation trees solving the Knapsack Problem, and more generally Restricted Integer Programming. This is the...

Lower Bound For, Dima Grigoriev, Marek Karpinski

We prove \Omega\Gamma n 2 ) complexity lower bound for the general model of randomized computation trees solving the Knapsack Problem, and more generally Restricted Integer Programming. This is the...

A Lower Bound for Randomized Algebraic Decision Trees (1996)

On real Turing machines that toss coins (1996)

We prove the first nontrivial (and superlinear) lower bounds on the depth of randomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and...

Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig

In this paper we consider real counterparts of classical probabilistic complexity classes in the framework of real Turing machines as introduced by Blum, Shub, and Smale [2]. We give an extension of...

Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks (1996)

By Marek, Marek Karpinski, Angus Macintyre

We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, that the VC Dimension of analog...

Approximating Dense Cases of Covering Problems (1996)

Randomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach (1996)

We study dense cases of several covering problems. An instance of the set cover problem with m sets is dense if there is ffl ? 0 such that any element belongs to at least fflm sets. We show that the...

Extend Ed, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter, Instytut Informatyki, Uniwersytet Warszawski

) Leszek G¸asieniec 1 ? Marek Karpinski 2 ?? Wojciech Plandowski 3 ??? Wojciech Rytter 3 y 1 Max-Planck Institut fur Informatik, Im Stadtwald, Saarbrucken D-66123, Germany. 2 Dept. of Computer...

On the Power of Randomized Branching Programs (1996)

By Farid, Farid Ablayev, Marek Karpinski

We define the notion of a randomized branching program in the natural way similar to the definition of a randomized circuit. We exhibit an explicit function f n for which we prove that: 1) f n can be...

On the Power of Randomized Branching Programs (1996)

On the Power of Randomized Branching Programs (1996)

. We define the notion of a randomized branching program in the natural way similar to the definition of a randomized circuit. We exhibit an explicit function fn for which we prove that: 1) fn can be...

Correctness of Constructing Optimal Alphabetic Trees Revisited (1996)

We define the notion of a randomized branching program in the natural way similar to the definition of a randomized circuit. We exhibit an explicit function f n for which we prove that: 1) f n can be...

Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter

Several new observations which lead to new correctness proofs of two known algorithms (Hu-Tucker and Garsia-Wachs) for construction of optimal alphabetic trees are presented. A generalized version of...

A Lower Bound for Randomized Algebraic Decision Trees (1996)

By Dima, Dima Grigoriev, Marek Karpinski, Roman Smolensky

We extend the lower bounds on the depth of algebraic decision trees to the case of randomized algebraic decision trees (with two-sided error) for languages being finite unions of hyperplanes and the...

Randomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach (Extended Abstract) (1996)

Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter, Instytut Informatyki, Uniwersytet Warszawski

Denote by LZ(w) the coded form of a string w produced by Lempel-Ziv encoding algorithm. We consider several classical algorithmic problems for texts in the compressed setting. The first of them is...

A Lower Bound for Randomized Algebraic Decision Trees (1996)

Approximating Dense Cases of Covering Problems (1996)

We extend the lower bounds on the depth of algebraic decision trees to the case of randomized algebraic decision trees (with two-sided error) for languages being finite unions of hyperplanes and the...

Randomized Ω(n²) Lower Bound for Knapsack (1996)

We study dense cases of several covering problems. An instance of the set cover problem with m sets is dense if there is ffl ? 0 such that any element belongs to at least fflm sets. We show that the...

Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis (1996)

We prove \Omega\Gamma n 2 ) complexity lower bound for the general model of randomized computation trees solving the Knapsack Problem, and more generally Restricted Integer Programming. This is the...

Dima Yu. Grigoriev, Marek Karpinski, Andrew M. Odlyzko

Symbolic manipulation of sparse polynomials, given as lists of exponents and nonzero coefficients, appears to be much more complicated than dealing with polynomials in dense encoding (see e.g. [GKS...

Efficient Algorithms for Lempel-Ziv Encoding (Extended Abstract) (1996)

Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter

) Leszek G¸asieniec 1 ? Marek Karpinski 2 ?? Wojciech Plandowski 3 ??? Wojciech Rytter 3 y 1 Max-Planck Institut fur Informatik, Im Stadtwald, Saarbrucken D-66123, Germany. 2 Dept. of Computer...

Polynomial time approximation schemes for dense instances of NP-hard problems (1995)

Polynomial time approximation schemes for dense instances of NP-hard problems (1995)

We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense " instances of many NP-hard optimization problems, including maximum cut, graph...

Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks (1995)

We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many NP-hard optimization problems, including maximum cut, graph...

An XOR-Based Erasure-Resilient Coding Scheme (1995)

. We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, that the VC Dimension of...

Johannes Blömer, Malik Kalfane, Richard Karp, Marek Karpinski, Michael Luby, David Zuckerman

An (m; n; b; r)-erasure-resilient coding scheme consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of n packets each...

Approaching the 5/4-Approximation for Rectilinear Steiner Trees (1995)

Piotr Berman, Ulrich Fößmeier, Marek Karpinski, Michael Kaufmann, Alexander Zelikovsky

The rectilinear Steiner tree problem requires a shortest tree spanning a given vertex subset in the plane with rectilinear distance. It was proved that the output length of Zelikovsky's [25] and...

Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems (1995)

New Approximation Algorithms for the Steiner Tree Problems (1995)

We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many NP-hard optimization problems, including maximum cut, graph...

Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks (1995)

The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using a novel...

Marek Karpinski Dept, Marek Karpinski, Angus Macintyre

. We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, the VC Dimension of analog...

A Lower Bound on the Size of Algebraic Decision Trees for the MAX Problem (1995)

Dima Grigoriev Marek, Marek Karpinski, Andrew Yao

We prove an exponential lower bound on the size of (ternary) algebraic decision trees for the MAX Problem of finding maximum of n real numbers. This complements n \Gamma 1 lower bound (cf. M. O....

On real Turing machines that toss coins (1995)

Felipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, Kai Werther

In this paper we consider real counterparts of classical probabilistic complexity classes in the framework of real Turing machines as introduced by Blum, Shub, and Smale [2]. We give an extension of...

1.757 and 1.267-Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems (1995)

Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems (1995)

The Steiner tree problem requires to find a shortest tree connecting a given set of terminal points in a metric space. We suggest a better and fast heuristic for the Steiner problem in graphs and in...

, Malik Kalfane (1995)

Johannes Blomer, Malik Kalfane, Richard Karp, Marek Karpinski, Michael Luby, David Zuckerman

An (m; n; b; r)-erasure-resilient coding scheme consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of n packets each...

VC Dimension of Sigmoidal and General Pfaffian Neural Networks (1995)

We present a unified framework for designing polynomial time approximation schemes (PTASs) for "dense" instances of many NP-hard optimization problems, including maximum cut, graph...

Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks (1995)

We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, that the VC Dimension of analog...

Bounding VC-Dimension for Neural Networks: Progress and Prospects (1995)

. We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, the VC Dimension of analog...

Lower Time Bounds for Randomized Computation (1995)

. Techniques from differential topology are used to give polynomial bounds for the VC-dimension of sigmoidal neural networks. The bounds are quadratic in w, the dimension of the space of weights....

Usi Ns, Marek Karpinski

It is a fundamental problem in the randomized computation how to separate different randomized time or randomized space classes (c.f., e.g., [KV87, KV88]). We have separated randomized space classes...

Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees (1995)

Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov

We introduce a new method of proving lower bounds on the depth of algebraic decision trees of degree d and apply it to prove a lower bound \Omega\Gammand/ N ) for testing membership to an...

An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX (1995)

Dima Grigoriev, Marek Karpinski, Andrew C. Yao

We prove an exponential lower bound on the size of any fixed-degree algebraic decision tree for solving MAX, the problem of finding the maximum of n real numbers. This complements the n \Gamma 1...

New Approximation Algorithms for the Steiner Tree Problems (1995)

Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks (1995)

The Steiner tree problem asks for the shortest tree connecting a given set of terminal points in a metric space. We design new approximation algorithms for the Steiner tree problems using a novel...

A Lower Bound for Randomized Algebraic Decision Trees (1995)

We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, the VC Dimension of analog...

Pattern-Matching for Strings with Short Descriptions (1995)

We extend the lower bounds on the depth of algebraic decision trees to the case of randomized algebraic decision trees (with two-sided error) for languages being finite unions of hyperplanes and the...

Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

. We consider strings which are succinctly described. The description is in terms of straight-line programs in which the constants are symbols and the only operation is the concatenation. Such...

VC Dimension of Sigmoidal and General Pfaffian Networks (1995)

Polynomial time approximation schemes for dense instances of NP-hard problems (1995)

We introduce a new method for proving explicit upper bounds on the VC Dimension of general functional basis networks, and prove as an application, for the first time, that the VC Dimension of analog...

Lower Space Bounds for Randomized Computation (1994)

We present a unified framework for designing polynomial time approximation schemes (PTASs) for “dense ” instances of many NP-hard optimization problems, including maximum cut, graph bisection,...

Rusins Freivalds, Marek Karpinski

It is a fundamental open problem in the randomized computation how to separate different randomized time or randomized small space classes (cf., e.g., [KV 87], [KV 88]). In this paper we study lower...

Lower Bounds on Testing Membership to a Polyhedron by Algebraic Decision Trees (1994)

Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov

We describe a new method of proving lower bounds on the depth of algebraic decision trees and apply it to prove a lower bound \Omega\Gammand/ N) for testing membership to a convex polyhedron having N...

Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees (1994)

Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov, A. Bjorner, L. Lovasz, A. Yao [b

We introduce a new method of proving lower bounds on the depth of algebraic d-degree decision (resp. computation) trees and apply it to prove a lower bound \Omega\Gammand/ N) (resp.\Omega\Gammaesp N=...

Simulating Threshold Circuits by Majority Circuits (1994)

Mikael Goldmann, Marek Karpinski

We prove that a single threshold gate with arbitrary weights can be simulated by an explicit polynomial-size depth 2 majority circuit. In general we show that a depth d threshold circuit can be...

Lower Bounds on Testing Membership to a Polyhedron by Algebraic Decision Trees (1994)

Dima Grigoriev Marek, Marek Karpinski, Nicolai Vorobjov

We describe a new method of proving lower bounds on the depth of algebraic decision trees and apply it to prove a lower bound \Omega\Gammand/ N) for testing membership to a convex polyhedron having N...

On a Sublinear Time Parallel Construction of Optimal Binary Search Trees (Note) (1994)

Marek Karpinski Dept, Marek Karpinski, Wojciech Rytter

We design an efficient sublinear time parallel construction of optimal binary search trees. The efficiency of the parallel algorithm corresponds to its total work (the product time \Theta...

Randomized Navigation to a Wall through Convex Obstacles (1994)

Lower Bounds on Testing Membership to a Polyhedron by Algebraic Decision Trees (1994)

We consider the problem of navigating through an unknown enviroment in which the obstacles are convex, and each contains a circle of diameter 1. The task is to reach a given straight line, in the...

Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov

We describe a new method of proving lower bounds on the depth of algebraic decision trees and apply it to prove a lower bound \Omega\Gammand/ N) for testing membership to a convex polyhedron having N...

Fast Interpolation Algorithms for Sparse Polynomials with Respect to the Size of Coefficients (1994)

Alexander L. Chistov, Marek Karpinski

In this paper we consider the interpolation of sparse polynomials in two different oracle models taking into account the size of coefficients only. St. Petersburg Institute for Informatics and...

Approaching the 5/4-Approximation for Rectilinear Steiner Trees (1994)

Piotr Berman, Ulrich Fößmeier, Rectilinear Steiner Trees, Marek Karpinski, Michael Kaufmann, Alexander Zelikovsky

The rectilinear Steiner tree problem requires to find a shortest tree connecting a given set of terminal points in the plane with rectilinear distance. We show that the performance ratios of...

Lower Bound for Randomized Linear Decision Tree Recognizing a Union of Hyperplanes in a Generic Position (1994)

Dima Grigoriev, Marek Karpinski, If Q

Let L be a union of hyperplanes with s vertices. We prove that the runtime of a probabilistic linear search tree recognizing membership to L is at least\Omega (log s), provided that L satisfies a...

Efficient Approximation Algorithms for Sparse Polynomials over Finite Fields (1994)

On a Sublinear Time Parallel Construction of Optimal Binary Search Trees (1994)

We obtain new lower bounds on the number of non zeros of sparse polynomials and give a fully polynomial time (ffl; ffi ) approximation algorithm for the number of non-zeros of multivariate sparse...

Marek Karpinski, Wojciech Rytter

. We design an efficient sublinear time parallel construction of optimal binary search trees. The efficiency of the parallel algorithm corresponds to its total work (the product time \Theta...

On the Computational Complexity of Matching on Chordal and Strongly Chordal Graphs (1994)

Elias Dahlhaus, Marek Karpinski

In this paper we study the computational complexity (both sequential and parallel) of the maximum matching problem for chordal and strongly chordal graphs. We show that there is a linear time greedy...

Counting Curves and Their Projections (1994)

An Algorithm To Learn Read-Once Threshold Formulas, And Transformations Between Learning Models (1994)

Some deterministic and probabilistic methods are presented for counting and estimating the number of points on curves over finite fields, and on their projections. The classical question of...

Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski

We present a membership query (i.e. black box interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of Boolean threshold functions. We also present a...

Counting curves and their projections (1993)

Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Decision Trees (1993)

Abstract. Some deterministic and probabilistic methods are presented for counting and estimating the number of points on curves over finite fields, and on their projections. The classical question of...

Dima Grigoriev Marek, Marek Karpinski, Log M

We describe a new method for proving lower bounds for algebraic decision trees. We prove, for the first time, that the minimum depth for arbitrary decision trees for the problem of testing the...

An Algorithm to Learn ReadOnce Threshold Formulas, and some Generic Transformations between Learning Models (1993)

Revised Version Nader, Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski

We present a membership query (i.e. black box interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of boolean threshold functions. We also present a...

On the parallel complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs (1993)

Elias Dahlhaus, Péter Hajnal, Marek Karpinski

Dirac's classical theorem asserts that, if every vertex of a graph G on n vertices has degree at least n 2 then G has a Hamiltonian cycle. We give a fast parallel algorithm on a CREW \Gamma PRAM...

An Algorithm to Learn Read-Once Threshold Formulas, and some Generic Transformations between Learning Models (1993)

Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski

We present a membership query (i.e. black box interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of boolean threshold functions. We also present a...

Alphabet-Independent Optimal Parallel Search for Three Dimensional Patterns (1993)

Marek Karpinski, Wojciech Rytter

We give an alphabet-independent optimal parallel algorithm for the searching phase of three-dimensional pattern-matching. All occurrences of a three dimensional pattern P of shape m \Theta m \Theta m...

Approximating the Number of Solutions of a GF(2) Polynomial (1993)

Marek Karpinski, Michael Luby

We develop a polynomial time Monte-Carlo algorithm for estimating the number of solutions to a multivariate polynomial over GF (2). This gives the first efficient method for estimating the number of...

Counting Curves and Their Projections (1993)

Approximating the Number of Zeroes of a GF[2] Polynomial (1993)

. Some deterministic and probabilistic methods are presented for counting and estimating the number of points on curves over finite fields, and on their projections. The classical question of...

Marek Karpinski, Michael Luby

We develop a probabilistic polynomial time algorithm which on input a polynomial g(x 1 ; : : : ; xn ) over GF[2], ffl and ffi , outputs an approximation to the number of zeroes of g with relative...

Simulating Threshold Circuits by Majority Circuits (1993)

Mikael Goldmann, Marek Karpinski

We prove that a single threshold gate with arbitrary weights can be simulated by an explicit polynomial-size depth 2 majority circuit. In general we show that a polynomial-size, depth- d threshold...

Simulating Threshold Circuits by Majority Circuits (1993)

Mikael Goldmann, Marek Karpinski

We prove that a single threshold gate can be simulated by an explicit polynomial size depth 2 majority circuit. In general we show that a depth d threshold circuit can be simulated uniformly by a...

Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Computation Trees (1993)

Lower Space Bounds for Randomized Computation (1993)

We describe a new method for proving lower bounds for algebraic computation trees. We prove, for the first time, that the minimum depth for arbitrary computation trees for the problem of testing the...

Usi Ns, Marek Karpinski

It is a fundamental open problem in the randomized computation how to separate different randomized time or randomized small space classes (cf., e.g., [KV 87], [KV 88]). In this paper we study lower...

On Randomized Versus Deterministic Computation (1993)

Marek Karpinski, Rutger Verbeek

. In contrast to deterministic or nondeterministic computation, it is a fundamental open problem in randomized computation how to separate different randomized time classes (at this point we do not...

Polynomial time approximation schemes for dense instances of minimum constraint satisfaction (1993)

Cristina Bazgan, Marek Karpinski

It is known that large fragments of the class of dense Minimum Constraint Satisfaction (MIN-CSP) problems do not have polynomial time approximation schemes (PTASs) contrary to their Maximum...

An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3 (1992)

Elias Dahlhaus Dept, Elias Dahlhaus, Marek Karpinski, Pierre Kelsen

The paper considers the problem of computing a maximal independent set in a hypergraph (see [3] and [7]). We present an efficient deterministic NC algorithm for finding a maximal independent set in a...

An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3 (1992)

Elias Dahlhaus, Marek Karpinski, Peter Kelsen

The paper considers the problem of computing a maximal independent set in a hypergraph (see [3] and [7]). We present an efficient deterministic NC algorithm for finding a maximal independent set in a...

Probabilistic Recurrence Relations for Parallel Divide-and-Conquer Algorithms (1992)

Marek Karpinski, Wolf Zimmermann

We study two probabilistic recurrence relations that arise frequently in the analysis of parallel and sequential divide-and-conquer algorithms (cf. [Ka 91]). Suppose a problem of size x has to be...

Read-Once Threshold Formulas, Justifying Assignments, and Generic Tranformations (1992)

Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski

We present a membership query (i.e. interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of boolean threshold functions. Using a generic transformation from...

On Randomized Algebraic Test Complexity (1992)

Peter Burgisser, Marek Karpinski, Thomas Lickteig

We investigate the impact of randomization on the complexity of deciding membership in a (semi-)algebraic subset X ae R m . Examples are exhibited where allowing for a certain error probability ffl...

Computational Complexity of Learning Read-Once Formulas over Different Bases (1991)

Lisa Hellerstein, Marek Karpinski

We study computational complexity of learning read-once formulas over different boolean bases. In particular we design a polynomial time algorithm for learning read-once formulas over a threshold...

Probabilistic Recurrence Relations for Parallel Divide-and-Conquer Algorithms (1991)

Marek Karpinski, Wolf Zimmermann

We study two probabilistic recurrence relations that arise frequently in the analysis of parallel and sequential divide-and-conquer algorithms (cf. [Karp 91]). Suppose a problem of size x has to be...

Computational Complexity of Sparse Rational Interpolation (1991)

Dima Grigoriev, Marek Karpinski, Michael F. Singer

We analyze the computational complexity of sparse rational interpolation, and give the first genuine time (arithmetic complexity does not depend on the size of the coefficients) algorithm for this...

Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis (1991)

Dima Grigoriev, Marek Karpinski, Andrew M. Odlyzko

Symbolic manipulation of sparse polynomials, given as lists of exponents and nonzero coefficients, appears to be much more complicated than dealing with polynomials in dense encoding (see e.g. [GKS...

An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over (1991)

Gf Dima Grigoriev, Dima Grigoriev, Marek Karpinski

We design the first polynomial time (for an arbitrary and fixed field GF [q]) (ffl; ffi )-approximation algorithm for the number of zeros of arbitrary polynomial f(x 1 ; : : : ; x n ) over GF [q]. It...

Algorithms for Sparse Rational Interpolation (1991)

Dima Grigoriev Marek, Marek Karpinski

We present two algorithms on sparse rational interpolation. The first is the interpolation algorithm in a sense of the sparse partial fraction representation of rational functions. The second is the...

An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over (1991)

Algorithms for Sparse Rational Interpolation (1991)

We design the first polynomial time (for an arbitrary and fixed field GF [q]) (ffl; ffi )-approximation algorithm for the number of zeros of arbitrary polynomial f(x 1 ; : : : ; x n ) over GF [q]. It...

Dima Yu. Grigoriev, Marek Karpinski

We present two algorithms on sparse rational interpolation. The first is the interpolation algorithm in a sense of sparse partial fraction representation of rational functions. The second is the...

The Computational Complexity of (XOR, AND)-Counting Problems (1990)

Andrzej Ehrenfeucht, Marek Karpinski

We characterize the computational complexity of counting the exact number of satisfying assignments in (XOR; AND)-formulas in their RSE-representation (i.e., equivalently, polynomials in GF [2][x 1 ;...

Fast Parallel Algorithms for the Clique Separator Decomposition (1990)

Elias Dahlhaus, Marek Karpinski, Mark B. Novick

We give an efficient NC algorithm for finding a clique separator decomposition of an arbitrary graph, that is, a series of cliques whose removal disconnects the graph. This algorithm allows one to...

An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (1989)

Elias Dahlhaus, Marek Karpinski

. We design the first efficient parallel algorithm for computing the minimal elimination ordering (MEO) of an arbitrary graph. The algorithm works in O(log 3 n) parallel time and O(nm) processors on...

There Is No Polynomial Deterministic Space Simulation of Probabilistic Space with a Two-Way Random-Tape Generator (1989)

Marek Karpinski, Rutger Verbeek

We prove there is no polynomial deterministic space simulation for two-way random-tape probabilistic space (Pr 2 SPACE) (as defined in [BCP 83]) for all functions f : IN ! IN and all ff 2 IN ; Pr 2...

VC Dimension and Learnability of Sparse Polynomials and Rational Functions (1989)

Marek Karpinski, Thorsten Werther

We prove upper and lower bounds on the VC dimension of sparse univariate polynomials over reals, and apply these results to prove uniform learnability of sparse polynomials and rational functions. As...

Boolean Circuit Complexity of Algebraic Interpolation Problems (1989)