Marek Karpinski
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Marek Karpinski has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
- Andrew M. Odlyzko
AT&T Labs – Research , 180 Park Avenue, Florham Park , NJ , 07932 , United States
1 shared publication - Andris Ambainis
Computer Science Division University of California CA94720 Berkeley USA
1 shared publication - Cristina Bazgan
Université Paris-Dauphine, PSL Research University, CNRS, UMR 7243, LAMSADE
1 shared publication - Dima Grigoriev
Dept. of Computer Science and Mathematics, Penn State University, University Park
1 shared publication - Dima Grigoriev
Departments of Mathematics and Computer Science, The Pensylvania State University, University Park, PA 16802, USA
1 shared publication - Dima Grigoriev
Steklov Mathematical Institute
1 shared publication
Latest Publications
- Open Access
- 18 June 2003
- Published by Wiley in Random Structures & Algorithms
- Vol. 23 (1) , 73-91
Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
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 Constraint Satisfaction analogs. In this paper we prove, somewhat surprisingly, that the minimum satisfaction of dense instances ofkSAT‐formulas, and linear equations mod 2, Ek‐LIN2, do have PTASs for anyk.The MIN‐Ek‐LIN2 problems are equivalent to thek‐ary versions of the Nearest Codeword problem, the problem which is known to be exceedingly hard to approximate on general instances. The method of solution of the above problems depends on the development of a new density sampling technique fork‐uniform hypergraphs which could be of independent interest. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 73–91, 2003
- 18 June 2003
- Published by Wiley in Random Structures & Algorithms
- Vol. 23 (1) , 73-91
Open AccessPolynomial time approximation schemes for dense instances of minimum constraint satisfaction
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 Constraint Satisfaction analogs. In this paper we prove, somewhat surprisingly, that the minimum satisfaction of dense instances ofkSAT‐formulas, and linear equations mod 2, Ek‐LIN2, do have PTASs for anyk.The MIN‐Ek‐LIN2 problems are equivalent to thek‐ary versions of the Nearest Codeword problem, the problem which is known to be exceedingly hard to approximate on general instances. The method of solution of the above problems depends on the development of a new density sampling technique fork‐uniform hypergraphs which could be of independent interest. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 73–91, 2003
- Open Access
Quantum finite multitape automata
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 that not all regular languages can be recognized by quantum finite automata. A.Ambainis and R.Freivalds proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by a deterministic or probabilistic finite automata. This is the first result on a problem which can be solved by a quantum computer but not by a deterministic or probabilistic computer. Additionally we discover unexpected probabilistic automata recognizing complicated languages.
Open AccessQuantum finite multitape automata
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 that not all regular languages can be recognized by quantum finite automata. A.Ambainis and R.Freivalds proved that for some languages quantum finite automata may be exponentially more concise rather than both deterministic and probabilistic finite automata. In this paper we introduce the notion of quantum finite multitape automata and prove that there is a language recognized by a quantum finite automaton but not by a deterministic or probabilistic finite automata. This is the first result on a problem which can be solved by a quantum computer but not by a deterministic or probabilistic computer. Additionally we discover unexpected probabilistic automata recognizing complicated languages.
- 1 March 1997
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 17 (2) , 191-215
Lower bound on testing membership to a polyhedron by algebraic decision and computation trees
- 1 March 1997
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 17 (2) , 191-215
Lower bound on testing membership to a polyhedron by algebraic decision and computation trees
- 1 March 1996
- Published by Springer Nature in computational complexity
- Vol. 6 (1) , 64-99
Counting curves and their projections
- 1 March 1996
- Published by Springer Nature in computational complexity
- Vol. 6 (1) , 64-99
Counting curves and their projections
- 1 January 1996
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 28 (3,4) , 297-301
Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis
We prove for the first time an existence of the short (polynomial size) proofs for nondivisibility of two sparse polynomials (putting thus this problem is the class NP) under the Extended Riemann Hypothesis. The divisibility problem is closely relate
- 1 January 1996
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 28 (3,4) , 297-301
Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis
We prove for the first time an existence of the short (polynomial size) proofs for nondivisibility of two sparse polynomials (putting thus this problem is the class NP) under the Extended Riemann Hypothesis. The divisibility problem is closely relate
- 1 March 1994
- Published by Springer Nature in computational complexity
- Vol. 4 (1) , 37-61
An algorithm to learn read-once threshold formulas, and transformations between learning models
- 1 March 1994
- Published by Springer Nature in computational complexity
- Vol. 4 (1) , 37-61
An algorithm to learn read-once threshold formulas, and transformations between learning models
- 1 January 1993
- Published by Springer Nature
- p. 91-104
Computational Complexity of Sparse Real Algebraic Function Interpolation
- 1 January 1993
- Published by Springer Nature
- p. 91-104
Computational Complexity of Sparse Real Algebraic Function Interpolation
- 1 June 1991
- Published by Springer Nature in computational complexity
- Vol. 1 (2) , 131-155
Some computational problems in linear algebra as hard as matrix multiplication
- 1 June 1991
- Published by Springer Nature in computational complexity
- Vol. 1 (2) , 131-155
Some computational problems in linear algebra as hard as matrix multiplication