Arrow Research search

Author name cluster

Marek Karpinski

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

54 papers
2 author rows

Possible papers

54

TCS Journal 2018 Journal Article

A QPTAS for the base of the number of crossing-free structures on a planar point set

  • Marek Karpinski
  • Andrzej Lingas
  • Dzmitry Sledneu

The number of triangulations of a planar n point set S is known to be c n, where the base c lies between 2. 43 and 30. Similarly, the number of crossing-free spanning trees on S is known to be d n, where the base d lies between 6. 75 and 141. 07. The fastest known algorithm for counting triangulations of S runs in 2 ( 1 + o ( 1 ) ) n log ⁡ n time while that for counting crossing-free spanning trees runs in O ⁎ ( 7. 125 n ) time. The fastest known, non-trivial approximation algorithms for the number of triangulations of S and the number of crossing-free spanning trees of S, respectively, run in time subexponential in n. We present the first non-trivial approximation algorithms for these numbers running in quasi-polynomial time. They yield the first quasi-polynomial approximation schemes for the base of the number of triangulations of S and the base of the number of crossing-free spanning trees on S, respectively.

Details DOI

TCS Journal 2015 Journal Article

Inapproximability of dominating set on power law graphs

  • Mikael Gast
  • Mathias Hauptmann
  • Marek Karpinski

We prove the first logarithmic lower bounds for the approximability of the Minimum Dominating Set problem for the case of connected ( α, β ) -power law graphs for α being a size parameter and β the power law exponent. We give also a best up to now upper approximation bound for this problem in the case of the parameters β > 2. We develop also a new functional method for proving lower approximation bounds and display a sharp approximation phase transition area between approximability and inapproximability of the underlying problems. Our results depend on a method which could be also of independent interest.

Details DOI

STOC Conference 2009 Conference Paper

Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems

  • Marek Karpinski
  • Warren Schudy

We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood decoding of an error correcting code. As another application of our method we give the first linear time approximation schemes for correlation clustering with a fixed number of clusters and its hierarchical generalization. Our results depend on a new technique for dealing with small objective function values of optimization problems and could be of independent interest.

Details

TCS Journal 2007 Journal Article

Optimal trade-off for Merkle tree traversal

  • Piotr Berman
  • Marek Karpinski
  • Yakov Nekrich

In this paper we describe optimal trade-offs between time and space complexity of Merkle tree traversals with their associated authentication paths, improving on the previous results of M. Jakobsson, T. Leighton, S. Micali, and M. Szydlo [Fractal Merkle tree representation and traversal, in: RSA Cryptographers Track, RSA Security Conference, 2003] and M. Szydlo [Merkle tree traversal in log space and time, in: Proc. Eurocrypt, in: LNCS, vol. 3027, 2004, pp. 541–554; Merkle tree traversal in log space and time, Preprint version 2003, available at http: //www. szydlo. com]. In particular, we show that our algorithm requires 2 log n / log ( 3 ) n hash function computations and storage for less than ( log n / log ( 3 ) n + 1 ) log log n + 2 log n hash values, where n is the number of leaves in the Merkle tree. We also prove that these trade-offs are optimal, i. e. there is no algorithm that requires less than O ( log n / log t ) time and less than O ( t log n / log t ) space for any choice of parameter t ≥ 2. Our algorithm could be of special interest in the case when both time and space are limited.

Details DOI

I&C Journal 2005 Journal Article

On the computational power of probabilistic and quantum branching program

  • 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 NC1 circuits. More generally, we define syntactic models for quantum and stochastic branching programs of bounded width and prove upper and lower bounds on their power. We show that any NC1 language can be accepted exactly by a width-2 quantum branching program of polynomial length, in contrast to the classical case where width 5 is necessary unless NC1 =ACC. This separates width-2 quantum programs from width-2 doubly stochastic programs as we show the latter cannot compute the middle bit of multiplication. Finally, we show that bounded-width quantum and stochastic programs can be simulated by classical programs of larger but bounded width, and thus are in NC1. For read-once quantum branching programs (QBPs), we give a symmetric Boolean function which is computable by a read-once QBP with O (log n) width, but not by a deterministic read-once BP with o (n) width, or by a classical randomized read-once BP with o (n) width which is “stable” in the sense that its transitions depend on the value of the queried variable but do not vary from step to step. Finally, we present a general lower bound on the width of read-once QBPs, showing that our O (log n) upper bound for this symmetric function is almost tight.

Details DOI

STOC Conference 2005 Conference Paper

Tensor decomposition and approximation schemes for constraint satisfaction problems

  • Wenceslas Fernandez de la Vega
  • Marek Karpinski
  • Ravindran Kannan
  • Santosh S. 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 weighted MAX-rCSP problems which includes as special cases the dense problems and, for r = 2, all metric instances (where the weights satisfy the triangle inequality) and quasimetric instances; for r > 2, our class includes a generalization of metrics. Our algorithms are based on low-rank approximations with two novel features: (1) a method of approximating a tensor by the sum of a small number of "rank-1" tensors, akin to the traditional Singular Value Decomposition (this might be of independent interest) and (2) a simple way of scaling the weights. Besides MAX-rCSP problems, we also give PTAS's for problems with a constant number of global constraints such as maximum weighted graph bisection and some generalizations.

Details

I&C Journal 2003 Journal Article

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

  • Farid Ablayev
  • Marek Karpinski

We prove an exponential lower bound 2Ω(n/logn) on the size of any randomized ordered read-once branching program computing integer multiplication. Our proof depends on proving a new lower bound on Yao’s randomized one-way communication complexity of certain Boolean functions. It generalizes to some other models of randomized branching programs. In contrast, we prove that testing integer multiplication, contrary even to a nondeterministic situation, can be computed by randomized ordered read-once branching program in polynomial size. It is also known that computing the latter problem with deterministic read-once branching programs is as hard as factoring integers.

Details DOI

STOC Conference 2003 Conference Paper

Approximation schemes for clustering problems

  • Wenceslas Fernandez de la Vega
  • Marek Karpinski
  • Claire Mathieu
  • Yuval Rabani

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 following three clustering problems: Metric k -Clustering, l 2 2 k -Clustering, and l 2 2 k -Median. In the k -Clustering problem, the objective is to minimize the sum of all intra-cluster distances. In the k -Median problem, the goal is to minimize the sum of distances from points in a cluster to the (best choice of) cluster center. In metric instances, the input distance function is a metric. In l 2 2 instances, the points are in R d and the distance between two points x,y is measured by x−y 2 2 (notice that (R d , ⋅ 2 2 is not a metric space). For the first two problems, our results are the first polynomial time approximation schemes. For the third problem, the running time of our algorithms is a vast improvement over previous work.

Details

I&C Journal 2002 Journal Article

Learning by the Process of Elimination

  • Rūsiņš Freivalds
  • Marek Karpinski
  • Carl H. Smith
  • Rolf Wiehagen

Elimination of potential hypotheses is a fundamental component of many learning processes. In order to understand the nature of elimination, herein we study the following model of learning recursive functions from examples. On any target function, the learning machine has to eliminate all, save one, possible hypotheses such that the missing one correctly describes the target function. It turns out that this type of learning by the process of elimination (elm-learning, for short) can be stronger, weaker or of the same power as usual Gold style learning. While for usual learning any r. e. class of recursive functions can be learned in all of its numberings, this is no longer true for elm-learning. For elm-learnability of an r. e. class in a given of its numberings, we derive sufficient conditions of this numbering (decidability of index equivalence and paddability) as well as a condition being both necessary and sufficient. Then we deal with the problem of which r. e. classes are elm-learnable in all of their numberings and which are not. Elm-learning of arbitrary classes of recursive function is shown to be of the same power as usual learning. For elm-learnability of an arbitrary class in an arbitrary numbering, paddability of this numbering remains to be useful, whereas decidability of index equivalence can be “maximally weak” or “extremely useful”. We also give a characterization for elm-learnability of an arbitrary class of recursive functions. Finally, we consider some generalizations of elm-learning. One of them is of the same power as usual learning by teams. A further generalization even allows to learn the class of all recursive functions.

Details DOI

STOC Conference 2002 Conference Paper

Random sampling and approximation of MAX-CSP problems

  • Noga Alon
  • Wenceslas Fernandez de la Vega
  • Ravindran 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 εn r . We prove a newgeneral paradigm in that it suffices, for a given set of constraints, to pick a small uniformly random subset of its variables, and the optimum value of the subsystem induced on these variables gives (after a direct normalization and with high probability) an approximation to the optimum of the whole system up to an additive error of εn r . Our method gives for the first time a polynomial in ε —1 bound on the sample size necessary to carry out the above approximation. Moreover, this bound is independent in the exponent on the dimension r . The above method gives a completely uniform sampling technique for all the MAX-rCSP problems, and improves the best known sample bounds for the low dimensional problems, like MAX-CUT. The method of solution depends on a new result on t he cut norm of random subarrays, and a new sampling technique for high dimensional linear programs. This method could be also of independent interest.

Details

TCS Journal 2001 Journal Article

On BPP versus NP∪coNP for ordered read-once branching programs

  • Farid Ablayev
  • Marek Karpinski
  • Rustam Mubarakzjanov

We investigate the relationship between probabilistic and nondeterministic complexity classes PP, BPP, NP and coNP with respect to ordered read-once branching programs (OBDDs). We exhibit two explicit Boolean functions qn, Rn such that: (1) qn: {0, 1}n→{0, 1} belongs to BPP⧹(NP∪coNP) in the context of OBDDs; (2) Rn: {0, 1}n→{0, 1} belongs to PP⧹(BPP∪NP∪coNP) in the context of OBDDs. Both of these functions are not in AC 0.

Details DOI

TCS Journal 2000 Journal Article

Zero testing of p-adic and modular polynomials

  • Marek Karpinski
  • Alf van der Poorten
  • Igor Shparlinski

We obtain new algorithms for testing whether a given by a black box multivariate polynomial over p-adic fields given by a black box is identical to zero. We also remark on the zero testing of polynomials in residue rings. Our results complement a known results on the zero testing of polynomials over the integers, the rationals, and over finite fields.

Details DOI

TCS Journal 1998 Journal Article

Alphabet-independent optimal parallel search for three-dimensional patterns

  • 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 × m × m in a text T of shape n × n × n are to be found. Our algorithm works in log m time with O(N/ log(m)) processors on a CREW PRAM, where N = n 3. Some ideas from [3] are used. We explore classification of two-dimensional periodicities of faces of the cubic pattern. Some projection techniques are developed to deal with three dimensions. The nonperiodicity implies some sparseness properties, while periodicity implies other special useful properties (i. e. , monotonicity) of the set of occurrences. Both types of properties are used in deriving our algorithm. The advantage of our approach is that it is essentially two-dimensional, no special properties related to three dimensions and no new complicated data structures are considered, the resulting algorithm is rather simple. The search phase is preceded by the preprocessing phase (computation of the witness table). Our main results concern the searching phase, however, we present shortly a new approach to the second phase also. Usefulness of the dictionaries of basic factors (DBFs, see [9]), in the computation of the three-dimensional witness table is presented. Our algorithms can be easily adjusted to the case of unequally sided patterns.

Details DOI

TCS Journal 1997 Journal Article

Correctness of constructing optimal alphabetic trees revisited

  • 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 the Garsia-Wachs algorithm is given. Proof of this generalized version works in a structured and illustrative way and clarifies the usually poorly understood behavior of both the Hu-Tucker and Garsia-Wachs algorithms. The generalized version permits any nonnegative weights, as opposed to strictly positive weights required in the original Garsia-Wachs algorithm. New local structural properties of optimal alphabetic trees are given. The concept of well-shaped segment (a part of an optimal tree) is introduced. It is shown that some parts of the optimal tree are known in advance to be well-shaped, and this implies correctness of the algorithms rather easily. The crucial part of the correctness proof of the Garsia-Wachs algorithm, namely the structural theorem, is identified. The correctness proof of the Hu-Tucker algorithm consists of showing a very simple mutual simulation between this algorithm and the Garsia-Wachs algorithm. For this proof, it is essential to use the generalized version of Garsia-Wachs algorithm, in which an arbitrary locally minimal pair is processed, not necessarily the rightmost minimal pair. Such a generalized version is also needed for parallel implementations. Another result presented in this paper is the clarification of the problem of resolving ties (equalities between weights of items) in the Hu-Tucker algorithm. This is related to the proof, by simulation, of correctness of the Hu-Tucker algorithm. It is shown that the condition that there are no ties may generally be assumed without harm and that, essentially, the Hu-Tucker algorithm avoids ties automatically.

Details DOI

TCS Journal 1996 Journal Article

On randomized versus deterministic computation

  • 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 even know how to separate linear randomized time from O(nlog n randomized time) or how to compare them relative to corresponding deterministic time classes. In other words, we are far from understanding the power of random coin tosses in the computation, and the possible ways of simulating them deterministically. In this paper we study the relative power of linear and polynomial randomized time compared with exponential deterministic time. Surprisingly, we are able to construct an oracle A such that exponential time (with or without the oracle A) is simulated by linear time Las Vegas algorithms using the oracle A. For Las Vegas polynomial time (ZPP) this will mean the following equalities of the time classes: ZPP A = EXPTIME A = EXPTIME (= DTIME(2 poly )). Furthermore, for all the sets M ⊆ ∑∗, M ⩽ UR A ̄ a ́ t M ϵ EXPTIME (⩽ UR being unfaithful polynomial random reduction, cf. [10]). Thus A ̄ is ⩽ UR complete for EXPTIME, but interestingly not NP-hard under (deterministic) polynomial reduction unless EXPTIME = NEXPTIME. We also prove, for the first time, that randomized reductions are exponentially more powerful than deterministic or nondeterministic ones (cf. [2]). Moreover, a set B is constructed such that Monte Carlo polynomial time (BPP) under the oracle B is exponentially more powerful than deterministic time with nondeterministic oracles, more precisely, BPP B = Δ 2 EXPTIME B = Δ 2 EXPTIME (= DTIME(2 poly ) NTIME(n)). This strengthens considerably a result of Stockmeyer [17] about the polynomial time hierarchy that for some decidable oracle B, BPPB n ́ Δ2PB. Under our oracle BPP B is exponentially more powerful than Δ 2 P B, and B does not add any power to Δ 2 EXPTIME. One of the consequences of this result is that under oracle B, Δ 2 EXPTIME has polynomial size circuits.

Details DOI

TCS Journal 1996 Journal Article

On some approximation problems concerning sparse polynomials over finite fields

  • Marek Karpinski
  • Igor Shparlinski

We obtain new lower bounds on the number of non-zeros of sparse polynomials and give a fully polynomial time (ε, δ) approximation algorithm for the number of non-zeros of multivariate sparse polynomials over a finite field of q elements and degree less than q − 1. This partially answers an open problem of D. Grigoriev and M. Karpinski. Also, probabilistic and deterministic algorithms for testing identity to zero of a sparse polynomial given by a “black-box” are given. Finally, we propose an algorithm to estimate the size of the image of a univariate sparse polynomial.

Details DOI

FOCS Conference 1995 Conference Paper

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

  • Dima Grigoriev
  • Marek Karpinski
  • Nicolai N. Vorobjov Jr.

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 /spl Omega/(log N) for testing membership to an n-dimensional convex polyhedron having N faces of all dimensions, provided that N>(nd)/sup /spl Omega//(n). This weakens considerably the restriction on N previously imposed by the authors and opens a possibility to apply the bound to some naturally appearing polyhedra.

Details

TCS Journal 1994 Journal Article

An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph

  • 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(log3 n) parallel time and O(nm) processors on CREW PRAM, for an n-vertex, m-edge graph, and is optimal up to a polylogarithmic factor with respect to the best sequential algorithm of Rose, et al. (1976). The MEO problem for arbitrary graphs arises in a number of combinatorial optimization problems, as well as in database applications, scheduling problems, and the sparse Gaussian elimination on symmetric matrices. It was believed before to be inherently sequential, and strongly resisting sublinear parallel time (sublinear sequential storage) algorithms. As an application, this paper gives the first efficient parallel solutions to the problem of minimal fill-in for arbitrary graphs and connected combinatorial optimization problems (see e. g. Rose et al. , 1976; Tarjan, 1985), and to the problem of the Gaussian elimination of sparse symmetric matrices (Rose, 1970; 1973) (The problem of computing a minimum fill-in is known to be NP-complete (Yannakakis, 1981). The method of solution involves a development of new techniques for solving connected minimal set system problem, and combining it with some new divide-and-conquer methods.

Details DOI

MFCS Conference 1994 Conference Paper

On a Sublinear Time Parallel Construction of Optimal Binary Search Trees

  • Marek Karpinski
  • Wojciech Rytter

Abstract 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 × processors ). Our algorithm works in O (n 1−ɛ log n ) time with the total work O (n 2−2ɛ ), for an arbitrarily small constant 0 < ε ≤ 1/2. This is optimal within a factor n 2ɛ with respect to the best known sequential algorithm given by Knuth, which needs only O (n 2 ) time due to a monotonicity property of optimal binary search trees, see [6]). It is unknown how to explore this property in an efficient NC construction of binary search trees. Here we show that it can be effectively used in sublinear time parallel computation. Our improvement also relies on the use (in independently processed small subcomputations) of the parallelism present in Knuth's algorithm. The best known sublinear time algorithms for the construction of binary search trees (as an instance of a more general problem) have O (n 3 ) work for time larger than n 3/4, see [3] and [7]. For time √n these algorithms need n 4 work, while our algorithm needs for this time only n 3 work, thus improving the known algorithms by a linear factor. Also if time is O (n 1−ɛ ) and ε is very small our improvement is close to O( n ). Such improvement is similar to the one implied by the monotonicity property in sequential computations (from n 3 sequential time for a more general dynamic programming problem to n 2 time for the special case of optimal binary search trees).

Details

FOCS Conference 1991 Conference Paper

An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]

  • Dima Grigoriev
  • Marek Karpinski

The authors design the first polynomial time (for an arbitrary and fixed field GF(q)) ( in, delta )-approximation algorithm for the number of zeros of arbitrary polynomial f(x/sub 1/. .. x/sub n/) over GF(q). It gives the first efficient method for estimating the number of zeros and nonzeros of multivariate polynomials over small finite fields other than GF(2) (like GF(3)), the case important for various circuit approximation techniques. The algorithm is based on the estimation of the number of zeros of an arbitrary polynomial f(x/sub 1/. .. ,x/sub n/) over GF(q) in the function of the number m of its terms. The bounding ratio is proved to be m/sup (q-1)/log/sup q/. >

Details

TCS Journal 1991 Journal Article

On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields

  • Michael Clausen
  • Andreas Dress
  • Johannes Grabmeier
  • Marek Karpinski

Given a black box which will produce the value of a k-sparse multivariate polynomial for any given specific argument, one may ask for optimal strategies (1) to distinguish such a polynomial from the zero-polynomial, (2) to distinguish any two such polynomials from one other and (3) to (uniformly) reconstruct the polynomial from such an information source. While such strategies are known already for polynomials over fields of characteristic zero, the equally important, but considerably more complicated case of a finite field K of small characteristic is studied in the present paper. The result is that the time complexity of such strategies depends critically on the degree m of the extension field of K from which the arguments are to be chosen; e. g. if m equals the number n of variables, then (1) can be solved by k+1 and (2) as well as (3) by 2k+1 queries, while in case m = 1 essentially 2log n·log k queries are needed.

Details DOI

CSL Conference 1991 Conference Paper

Subclasses of Quantified Boolean Formulas

  • Andreas Flögel
  • Marek Karpinski
  • Hans Kleine Büning

Abstract Using the results of a former paper of two of the authors [KaKB 90], for certain subclasses of quantified Boolean formulas it is shown, that the evaluation problems for these classes are coNP-complete. These subclasses can be seen as extensions of Horn and 2-CNF formulas. Further it is shown that the evaluation problem for quantified CNF formulas remains PSPACE-complete, even if at most one universal variable is allowed in each clause.

Details

FOCS Conference 1990 Conference Paper

Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents

  • Dima Grigoriev
  • Marek Karpinski
  • Michael F. Singer

The authors present the first algorithm for the (black box) interpolation of t-sparse, n-variate, rational functions without knowing bounds on exponents of their sparse representation, with the number of queries independent of exponents. In fact, the algorithm uses O(nt/sup t/) queries to the black box, and it can be implemented for a fixed t in a polynomially bounded storage (or polynomial parallel time). >

Details

MFCS Conference 1990 Conference Paper

On the Complexity of Genuinely Polynomial Computation

  • Marek Karpinski
  • Friedhelm Meyer auf der Heide

Abstract We present separation results on genuinely (or strongly) time bounded sequential, parallel and nondeterministic complexity classes defined by RAMs with fixed set of arithmetic operations. In particular, we separate non-uniform polynomial time from non-uniform parallel polynomial time for the set of operations {+, −, *} (answering a question of [M 88]), and uniform deterministic polynomial time from uniform nondeterministic polynomial time for the set of operations {t+, −, DIV c }, where DIV c denotes a restricted integer division operation.

Details

FOCS Conference 1989 Conference Paper

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

  • Elias Dahlhaus
  • Marek Karpinski

The first efficient parallel algorithm for computing minimal elimination ordering (MEO) of an arbitrary graph is designed. The algorithm works in O(log/sup 3/n) parallel time and O(nm) processors on a concurrent-read-concurrent-write parallel random-access machine (CRCW PRAM) for an n-vertex, m-edge graph and is optimal up to polylogarithmic factor with respect to the best sequential algorithm of D. Rose et. al. (SIAM J. Comput. , vol. 5, p. 266-83, 1976). As an application, the first efficient parallel solution to the problem of minimal fill-in for arbitrary graphs is given. The method of solution involves the development of new techniques for solving the connected minimal set system problem and combining them with some new divide-and-conquer methods. >

Details

CSL Conference 1989 Conference Paper

Boolean Complexity of Algebraic Interpolation Problems

  • Marek Karpinski

Abstract We present here some recent results on fast parallel interpolation of multivariate polynomials over finite fields. Some applications towards the general conversion algorithms for boolean functions are also formulated.

Details

CSL Conference 1988 Conference Paper

On the Computational Complexity of Quantified Horn Clauses

  • Marek Karpinski
  • Hans Kleine Büning
  • Peter H. Schmitt

Abstract A polynomial time algorithm is presented for the evaluation problem for quantified propositional Horn clauses. This answers an open problem posed by Itai and Makowski in (IM 87).

Details

FOCS Conference 1988 Conference Paper

Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs

  • Elias Dahlhaus
  • Péter Hajnal
  • Marek Karpinski

G. A. Dirac's classical theorem (1952) asserts that if every vertex of a graph G on n vertices has degree at least n/2, the G has a Hamiltonian cycle. A fast parallel algorithm on a concurrent-read-exclusive-write parallel random-access machine (CREW PRAM) is given to find a Hamiltonian cycle in such graphs. The algorithm uses a linear number of processors and is optimal up to a polylogarithmic factor. It works in O(log/sup 4/n) parallel time and uses linear number of processors on a CREW PRAM. It is also proved that a perfect matching in dense graphs can be found in NC/sup 2/. The cost of improved time is a quadratic number of processors. It is also proved that finding an NC algorithm for perfect matching in slightly less dense graphs is as hard as the same problem for all graphs, and the problem of finding a Hamiltonian cycle becomes NP-complete. >

Details

TCS Journal 1988 Journal Article

Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs

  • Elias Dahlhaus
  • Marek Karpinski

The intensive study of fast parallel and distributed algorithms for various routing (and communications) problems on graphs with good expanding properties [29, 30, 33] has been carried out recently. The parallel solutions for expanders that already exist [30] required an extensive randomization and an application of a randomized subroutine for the Maximum Matching Problem. In this paper we attack the problem of fast parallel algorithms for constructing perfect matchings and Hamiltonian cycles on dense graph-networks (undirected graphs of minimal degree 1 2 ¦V¦). Somewhat surprisingly, we design fast deterministic parallel algorithms for constructing both the perfect matchings and the Hamiltonian cycles on the dense graphs. The algorithm for constructing perfect matchings on dense graphs works in O(log2 n) parallel time and O(n 8) processors, or O(log4 n) parallel time and O(n 4) processors on a CREW-PRAM. The algorithm for constructing Hamiltonian cycles on dense graphs works in O(log5 n) parallel time and O(n 4) processors on a CREW-PRAM. Our method of the parallel solution involves a development of new dense graph combinatorics suitable for fast parallelization.

Details DOI

I&C Journal 1987 Journal Article

On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes

  • Marek Karpinski
  • Rutger Verbeek

It is proven that contrary to the deterministic and nondeterministic cases there is no recursive lower bound for Monte Carlo space constructible functions. The existence of small constructible bounds enables the separation of Monte Carlo space f(n) from probabilistic space g(n)(f(n)=o(g(n))) and—together with a new halting lemma for probabilistic machines with small space bounds—a hierarchy of “provable” Monte Carlo space classes with small bounds. We are also able to separate O(log log n) terminating Monte Carlo space in the sense of (Aleliunas et al. , in “Proceedings, 20th IEEE Found. of Comput. Sci. 1979”, pp. 218–223; Welsh, Discrete Appl. Math. 5 (1983), 133–145) from NSPACE(log logn).

Details DOI

FOCS Conference 1987 Conference Paper

The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract)

  • Dima Grigoriev
  • Marek Karpinski

It is shown that the problem of deciding and constructing a perfect matching in bipartite graphs G with the polynomial permanents of their n × n adjacency matrices A (perm(A) = nO(1)) are in the deterministic classes NC2 and NC3, respectively. We further design an NC3 algorithm for the problem of constructing all perfect matchings (enumeration problem) in a graph G with a permanent bounded by O(nk). The basic step was the development of a new symmetric functions method for the decision algorithm and the new parallel technique for the matching enumerator problem. The enumerator algorithm works in O(log3 n) parallel time and O(n3k+5. 5 · log n) processors. In the case of arbitrary bipartite graphs it yields an 'optimal' (up to the log n- factor) parallel time algorithm for enumerating all the perfect matchings in a graph. It entails also among other things an efficient NC3-algorithm for computing small (polynomially bounded) arithmetic permanents, and a sublinear parallel time algorithm for enumerating all the perfect matchings in graphs with permanents up to 2nε.

Details

TCS Journal 1982 Journal Article

Decidability of “Skolem matrix emptiness problem” entails constructability of exact regular expression

  • Marek Karpinski

The famous result of T. Skolem of 1933 assures the regularity of J A -sets of arbitrary integer valued matrices A. It prompts also a problem of deciding the emptiness of J A (Skolem Problem), and a more important problem of describing J A in terms of finite-state machine or Kleene's Regular Expression. We show (by elementary method) that recursiveness of Skolem Problem entails constructability of exact regular expression (machine). Under the same assumption, this provides an algorithm for the full matrix equivalence problem J A = J B. Moreover, we prove the equivalence problem ‘modulo a finite set’ J A = F J B to be recursively solvable.

Details DOI

MFCS Conference 1975 Conference Paper

Decision Algorithms for Havel's Branching Automata

  • Marek Karpinski

Abstract The decision problems on ( nondeterministic ) branching ω-automata (ωBAs) has been proved recursively solvable. These results solve, as a special case, the decision problems on (deterministic) Havel's branching automata (DBAs), and the connected heuristic searching problems ([4]).

Details

MFCS Conference 1975 Conference Paper

Stretching by Probabilistic Tree Automata and Santos Grammars

  • Marek Karpinski

Abstract The characterization theorems on Santos grammars [8] by means of pseudo probabilistic tree languages stretchings have been given. They are all derivable from the Equivalence Theorems on probabilistic tree languages settled in [2].

Details
v2026.09.13