Marek Karpinski

Q: What Schools Are Affiliated With Marek Karpinski

Marek Karpinski is affiliated with the following schools: University of California, Berkeley, Adam Mickiewicz University in Poznań, University of British Columbia, University of Warsaw, University of Bonn

Marek Karpinski's AcademicInfluence.com Rankings

Marek Karpinski

Computer Science

#673

World Rank

#694

Historical Rank

computer-science Degrees

Marek Karpinski

Mathematics

#2821

World Rank

#4277

Historical Rank

Complexity Theory

#12

World Rank

#12

Historical Rank

Measure Theory

#1953

World Rank

#2375

Historical Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

Marek Karpinski's Degrees

Masters Mathematics University of Warsaw
Bachelors Mathematics University of Warsaw

Similar Degrees You Can Earn

Best Online Bachelor's in Math 2025

Why Is Marek Karpinski Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Marek Karpinski is a computer scientist and mathematician known for his research in the theory of algorithms and their applications, combinatorial optimization, computational complexity, and mathematical foundations. He is a recipient of several research prizes in the above areas.

(See a Problem?)

Marek Karpinski's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

An XOR-based erasure-resilient coding scheme (1995) (472)
Polynomial time approximation schemes for dense instances of NP-hard problems (1995) (408)
Resolution for Quantified Boolean Formulas (1995) (357)
On Some Tighter Inapproximability Results (1998) (250)
New Approximation Algorithms for the Steiner Tree Problems (1997) (208)
Learning read-once formulas with queries (1993) (200)
On Some Tighter Inapproximability Results (Extended Abstract) (1999) (182)
Approximation schemes for clustering problems (2003) (167)
Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks (1997) (153)
1.375-Approximation Algorithm for Sorting by Reversals (2002) (153)
Approximation Hardness of Short Symmetric Instances of MAX-3SAT (2003) (152)
Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields (1988) (136)
The matching problem for bipartite graphs with polynomially bounded permanents is in NC (1987) (134)
8/7-approximation algorithm for (1,2)-TSP (2006) (115)
New Inapproximability Bounds for TSP (2013) (112)
An exponential lower bound for depth 3 arithmetic circuits (1998) (110)
On-Line Load Balancing for Related Machines (1997) (105)
Random sampling and approximation of MAX-CSPs (2003) (105)
Polynomial bounds for VC dimension of sigmoidal neural networks (1995) (103)
Efficient algorithms for Lempel-Ziv encoding (1996) (95)
Fast parallel algorithms for graph matching problems (1998) (87)
Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament (2010) (86)
Simulating threshold circuits by majority circuits (1993) (86)
On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials Over Finite Fields (1991) (86)
An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions (1997) (79)
Efficient Algorithms for Lempel-Zip Encoding (Extended Abstract) (1996) (66)
Random sampling and approximation of MAX-CSP problems (2002) (65)
Polynomial time algorithms for modules over finite dimensional algebras (1997) (65)
Improved approximation of Max-Cut on graphs of bounded degree (2002) (64)
Improved Approximation Lower Bounds on Small Occurrence Optimization (2003) (62)
On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts (1997) (62)
Approximating dense cases of covering problems (1996) (60)
On the computational power of probabilistic and quantum branching program (2005) (57)
On Computational Power of Quantum Branching Programs (2001) (57)
Pattern-Matching for Strings with Short Descriptions (1995) (56)
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs (2001) (53)
Tensor decomposition and approximation schemes for constraint satisfaction problems (2005) (52)
Approximation Hardness of TSP with Bounded Metrics (2001) (51)
On the Power of Randomized Branching Programs (1996) (49)
Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems (2002) (48)
Lower Space Bounds for Randomized Computation (1994) (48)
Top-K color queries for document retrieval (2010) (44)
On Approximation Intractability of the Bandwidth Problem (1997) (43)
Deterministic Polynomial Time Algorithms for Matrix Completion Problems (2009) (43)
On real Turing machines that toss coins (1995) (43)
The Computational Complexity of ({\it XOR, AND\/})-Counting Problems (1990) (42)
Optimal trade-off for merkle tree traversal (2005) (41)
Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT (2003) (40)
Counting curves and their projections (1993) (40)
A lower bound for randomized algebraic decision trees (1996) (40)
Computational Complexity of Sparse Rational Interpolation (1994) (40)
Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs (1998) (38)
On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs (1993) (37)
Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems (1997) (37)
Randomized splay trees: Theoretical and experimental results (2002) (36)
Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract) (1996) (35)
Foundations of Computation Theory (1983) (35)
On a New High Dimensional Weisfeiler-Lehman Algorithm (1999) (35)
TSP with bounded metrics (2006) (34)
Generalized Wong sequences and their applications to Edmonds' problems (2013) (33)
A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals (1993) (33)
On Some Tighter Inapproximability Results, Further Improvements (1998) (32)
An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3 (1991) (32)
On the Computational Complexity of Quantified Horn Clauses (1987) (31)
Approximation Algorithms for NP-Hard Problems (2004) (30)
An Approximation Algorithm for the Bandwidth Problem on Dense Graphs (1997) (30)
On the Monte Carlo Space Constructible Functions and Seperation Results for Probabilistic Complexity Classes (1987) (30)
A note on approximating Max-Bisection on regular graphs (2001) (30)
Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems (2008) (29)
A Fast Parallel Algorithm for Computing all Maximal Cliques in a Graph and the Related Problems (Extended Abstract) (1988) (29)
The Matching Problem for Strongly Chordal Graphs is in $NC$ (1986) (28)
Learning read-once formulas using membership queries (1989) (28)
Path coupling using stopping times and counting independent sets and colorings in hypergraphs (2005) (28)
Randomness, Provability, and the Seperation of Monte Carlo Time and Space (1987) (28)
VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions (1993) (28)
Stopping Times, Metrics and Approximate Counting (2006) (28)
The Interpolation Problem for k-sparse Sums of Eigenfunctions of Operators (1991) (28)
Computational Complexity of the Perfect Matching Problem in Hypergraphs with Subcritical Density (2010) (28)
Approximating minimum unsatisfiability of linear equations (2002) (26)
Polynomial time approximation of dense weighted instances of MAX-CUT (2000) (26)
Inapproximability of dominating set on power law graphs (2012) (26)
Approximating the number of zeroes of a GF[2] polynomial (1991) (26)
Interpolation of sparse rational functions without knowing bounds on exponents (1990) (24)
Polynomial Time Approximation Schemes for Metric Min-Sum Clustering (2002) (24)
Approximability of the Minimum Bisection Problem: An Algorithmic Challenge (2002) (24)
On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials (1999) (23)
Approaching the 5/4-Approximation for Rectilinear Steiner Trees (1994) (23)
Subtree Isomorphism is NC Reducible to Bipartite Perfect Matching (1989) (22)
.375-approximation Algorithm for Sorting by Reversals (2011) (22)
A generalization of Wilkie's theorem of the complement, and an application to Pfaffian closure (1999) (22)
Cycles and paths in edge‐colored graphs with given degrees (2010) (22)
On the Power of Randomized Ordered Branching Programs (1998) (21)
Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems (2009) (20)
Efficient Amplifiers and Bounded Degree Optimization (2001) (20)
Searching for Frequent Colors in Rectangles (2008) (20)
Trading GRH for algebra: Algorithms for factoring polynomials and related structures (2008) (19)
An approximation algorithm for the number of zeros or arbitrary polynomials over GF(q) (1991) (19)
Co-learning of total recursive functions (1994) (19)
Space Efficient Multi-dimensional Range Reporting (2008) (18)
On the Approximation Hardness of Dense TSP and Other Path Problems (1999) (18)
Approximating Bounded Degree Instances of NP-Hard Problems (2001) (18)
On Approximation Lower Bounds for TSP with Bounded Metrics (2012) (18)
On Some Approximation Problems Concerning Sparse Polynomials over Finite Fields (1996) (18)
Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem (2005) (18)
Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications (2015) (18)
Approximation schemes for Metric Bisection and partitioning (2004) (18)
Improved Inapproximability Results for the Shortest Superstring and Related Problems (2013) (18)
Approximating Volumes and Integrals in o-Minimal and p-Minimal Theories (1997) (17)
Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION (2002) (17)
On randomized algebraic test complexity (1992) (17)
Approximating vertex cover in dense hypergraphs (2010) (17)
On Randomized Semi-algebraic Test Complexity (1993) (17)
The mixing time of Glauber dynamics for coloring regular trees (2008) (17)
Computational complexity of some restricted instances of 3-SAT (2007) (16)
Schemes for deterministic polynomial factoring (2008) (16)
Algorithms for sparse rational interpolation (1991) (16)
Improved lower bound on testing membership to a polyhedron by algebraic decision trees (1995) (16)
Polynomial time approximation schemes for dense instances of minimum constraint satisfaction (2003) (15)
A Fast Algorithm for Adaptive Prefix Coding (2006) (14)
Compact cellular algebras and permutation groups (1999) (14)
Eecient Algorithms for Lempel-ziv Encoding (1996) (14)
1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2 (2009) (14)
A lower bound for integer multiplication on randomized ordered read-once branching programs (2003) (13)
Embedding Point Sets into Plane Graphs of Small Dilation (2005) (13)
Subclasses of Quantified Boolean Formulas (1990) (13)
An exponential lower bound on the size of algebraic decision trees for Max (1998) (13)
Deterministic Polynomial Factoring and Association Schemes (2012) (13)
On Approximation Hardness of the Bandwidth Problem (1997) (13)
Tropical Dominating Sets in Vertex-Coloured Graphs (2015) (12)
Cycles and paths in edge-colored graphs with given degrees (2010) (12)
Approximating the Volume of General Pfaffian Bodies (1997) (12)
An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph (1989) (12)
Computational Complexity of Sparse Real Algebraic Function Interpolation (1992) (12)
Approximation hardness of graphic TSP on cubic graphs (2013) (12)
Lower Bounds on Complexity of Testing Membership to a Polygon for Algebraic and Randomized Computation Trees (1993) (12)
Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs (2010) (12)
A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs (1997) (11)
Existence of short proofs for nondivisibility of sparse polynomials under the extended Riemann hypothesis (1992) (11)
The Complexity of Perfect Matching Problems on Dense Hypergraphs (2009) (11)
Correctness of Constructing Optimal Alphabetic Trees Revisited (1997) (11)
Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem (2003) (10)
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems (2009) (10)
Perfect Matching for Regular Graphs is AC°-Hard for the General Matching Problem (1992) (10)
Sequential and parallel subquadratic work algorithms for constructing approximately optimal binary search trees (1996) (10)
Approximating Huffman Codes in Parallel (2002) (10)
Lower bound on testing membership to a polyhedron by algebraic decision and computation trees (1997) (10)
Parallel Construction of Perfect Matchings and Hamiltonian Cycles on Dense Graphs (1987) (10)
Boolean Complexity of Algebraic Interpolation Problems (1988) (10)
The computational complexity of graph problems with succinct multigraph representation (1988) (10)
Subtree Isomorphism and Bipartite Perfect Matching are Mutually $NC$-Reducible (1986) (9)
There Is No Polynomial Deterministic Space Simulation of Probabilistic Space with a Two-Way Random-Tape Generator (1986) (9)
Approximation Algorithms for MAX-BISECTION on Low Degree Reg ular Graphs and Planar Graphs (2000) (9)
Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields (2015) (9)
Approximating Subdense Instances of Covering Problems (2010) (9)
Lower bounds on testing membership to a polyhedron by algebraic decision trees (1994) (9)
Randomized Ω(n2) lower bound for knapsack (1997) (9)
Approximating Transitive Reductions for Directed Networks (2009) (9)
An algorithm to learn read-once threshold formulas, and transformations between learning models (2005) (9)
On Approximability of Minimum Bisection Problem (2002) (8)
o-Minimal Expansions of the Real Field: A Characterization, and anApplication to Pfaffian Closure (1997) (8)
Lower Bound for Randomized Linear Decision Trees Recognising a Union of Hyperplanes in a Generic Position (1994) (8)
On the Complexity of Global Constraint Satisfaction (2005) (8)
Quantum Finite Multitape Automata (1999) (8)
Algorithmic Perspectives of Network Transitive Reduction Problems and their Applications to Synthesis and Analysis of Biological Networks (2013) (8)
On Randomized versus Deterministic Computation (1992) (8)
Computational Complexity of Learning Read-Once Formulas over Different Bases (1990) (8)
Co-learnability and FIN-identifiability of Enumerable Classes of Total Recursive Functions (1994) (7)
Fast parallel algorithms for the clique separator decomposition (1989) (7)
Effects of Kolmogorov Complexity Present in Inductive Inference as Well (1997) (7)
Optimal parallel algorithm for the Hamiltonian cycle problem on dense graphs (1988) (7)
9/8-Approximation Algorithm for Random MAX-3SAT (2002) (7)
Bounding VC-dimension of neural networks: Progress and prospects (1995) (7)
On a Sublinear Time Parallel Construction of Optimal Binary Search Trees (1994) (7)
Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations (2012) (7)
The Fully Compressed String Matching for Lempel-Ziv Encoding (1995) (7)
Improved Lower Bounds for the Shortest Superstring and Related Problems (2011) (6)
1.757 and 1.267 - Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems (1994) (6)
Path Coupling Using Stopping Times (2005) (6)
Almost deterministic -automata with existential output condition (1975) (6)
An Alphabet-Independent Optimal Parallel Search for Three Dimensional Pattern (1994) (6)
Lower Time Bounds for Randomized Computation (1995) (6)
Read-Once Threshold Formulas, Justifying Assignments, and Generic Transformations (1991) (6)
Approximation of Global MAX-CSP Problems (2006) (5)
A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set (2015) (5)
On Vulnerability of Banking Networks (2011) (5)
A Polynomial Time Approximation Scheme for Metric MIN-BISECTION (2002) (5)
On the Computational Power of Randomized Branching Programs (1998) (5)
Node Expansions and Cuts in Gromov-hyperbolic Graphs (2015) (5)
On the Monte Carlo Space Constructible Functions and Separation Results for Probabilistic Complexity Classes (Revised Version) (1986) (5)
Approximate Counting of Matchings in (3, 3)-Hypergraphs (2014) (5)
A note on On-line Load Balancing for related Machines (1996) (5)
Approximation Complexity of Nondense Instances of MAX-CUT (2006) (5)
On the Power of Two-Way Random Generators and the Impossibility of Deterministic Poly-Space Simulation (1986) (5)
Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann (1996) (4)
On the Complexity of Genuinely Polynomial Computation (1990) (4)
Limits of CSP Problems and Efficient Parameter Testing (2014) (4)
1.0957-Approximation Algorithm for Random MAX-3SAT (2007) (4)
Learning by the Process of Elimination (2002) (4)
Randomization and the computational power of analytic and algebraic decision trees (1996) (4)
Computability of the Additive Complexity of Algebraic Circuits with Root Extracting (1996) (4)
Alphabet-Independent Optimal Parallel Search for Three-Dimensional Patterns (1995) (4)
Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs (2004) (4)
On the Computational Complexity of Measuring Global Stability of Banking Networks (2011) (4)
An Algorithm to Learn Read-Once Threshold Formulas, and some Generic Transformations between Learning Models (1993) (4)
A Polynomial Time Approximation Scheme for Subdense MAX-CUT (2002) (4)
Randomized E cient Algorithmsfor Compressed Strings : theFinger-Print Approach (1996) (4)
Selected papers of the international conference on "foundations of computation theory" on Topics in the theory of computation (1985) (4)
Approximating the Number of Solutions of a {\ G F [ 2 ]} Polynomial (1990) (4)
Zero testing of p-adic and modular polynomials (2000) (4)
Approximability of Dense Instances of NEAREST CODEWORD Problem (2002) (4)
A Note on Traversing Skew Merkle Trees (2004) (4)
Decidability Results on Plane Automata Searching Mazes (1979) (3)
Optimal cuts and partitions in tree metrics in polynomial time (2012) (3)
On the Complexity of Nondeterministically Testable Hypergraph Parameters (2015) (3)
VC Dimension and Learnability of Sparse Polynomials and Rational Functions (1989) (3)
Predecessor Queries in Constant Time? (2005) (3)
On the Computational Complexity of Matching on Chordal and Strongly Chordal Graphs (2007) (3)
On Systemic Stability of Banking Networks (2011) (3)
The Complexity of Two-dimensional Compressed Pattern-matching (1996) (3)
Some Separation Problems on Randomized OBBDs (1998) (3)
Probablistic Climbing and Sinking Languages (1974) (3)
Approximate Counting of Matchings in Sparse Uniform Hypergraphs (2012) (3)
Approximability of Hypergraph Minimum Bisection (2003) (3)
Fast Parallel Decomposition by Clique Separators (1988) (2)
On the Approximability of Independent Set Problem on Power Law Graphs (2015) (2)
Low-Memory Adaptive Prefix Coding (2008) (2)
Complexity of Nondeterministic Graph Parameter Testing (2014) (2)
A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs (2000) (2)
Explicit Bounds for Nondeterministically Testable Hypergraph Parameters (2015) (2)
Approximating Minimum Unsatissability of Linear Equations (2001) (2)
Valued Probabilistic Tree Functions (1976) (2)
VC dimension and sampling complexity of learning sparse polynomials and rational functions (1994) (2)
Complexity of Deciding Solvability of Polynomial Equations over p-adic Integers (1997) (2)
Efficient Parallel Algorithm for Clique Separator Decomposition (1988) (2)
Optimal Cuts and Bisections on the Real Line in Polynomial Time (2012) (2)
Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams (2018) (2)
VC Dimension of Sigmoidal and General Pfaffian Networks (1995) (2)
Boolean Circuit Complexity of Algebraic Interpolation Problems (2011) (2)
Parallel Complexity of Matching Restricted to Degree-Defined Graph Classes (1987) (2)
Approximation Hardness of TSP with Bounded Metrics ( Revised Version ) (2001) (2)
Improved Approximation Bounds for the Rectilinear Steiner Tree Problem (1994) (2)
Lower Bounds for the Number of Zeros of Multivariate Polynomials over GF[$q$] (1991) (2)
A Note on Las Vegas OBDDs (1998) (2)
A QPTAS for the Base of the Number of Triangulations of a Planar Point Set (2014) (2)
Fast Interpolation Algorithms for Sparse Polynomials with Respect to the Size of Coefficients (1994) (2)
Decision Algorithms for Havel's Branching Automata (1975) (2)
The Parallel and Sequential Complexity of Matching on Chordal and Strongly Chordal Graphs (1995) (1)
1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two (2008) (1)
Algorithms for construction of optimal and almost-optimal length-restricted codes (2005) (1)
A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two (2008) (1)
Fundamentals of Computation Theory (1993) (1)
Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs (2011) (1)
A Parallel Algorithm for Maximum Matching in Planar Graphs (1989) (1)
Efficient Deterministic Interpolation of Multivariate Polynomials over Finite Fields (1987) (1)
Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies (2015) (1)
Nearly tight approximation bounds for vertex cover on dense k-uniform k-partite hypergraphs (2015) (1)
On BPP versus NPcoNP for ordered read-once branching programs (2001) (1)
Approximate Counting of Matchings in Sparse Hypergraphs (2012) (1)
Stretching by Probabilistic Tree Automata and Santos Grammars (1974) (1)
Approximating Transitivity in Directed Networks (2008) (1)
Weak and Strong Recognition by 2-way Randomized Automata (1997) (1)
Some computational problems in linear algebra as hard as matrix multiplication (2005) (1)
Polynomial Time Decomposition of Modules over Algebras and its Application (1996) (1)
Nearly Optimal Parallel Algorithm for Maximum Matching in Planar Graphs (1990) (1)
The Equivalences Problems for Binary EOL-Systems are Decidable (1977) (1)
Computing the Additive Complexity of Algebraic Circuits with Root Extracting (1998) (1)
Approximation Complexity of Max-Cut on Power Law Graphs (2016) (1)
Complexity of Computing Functions by Quantum Branching Programs (2011) (1)
Identity Testing from High Powers of Polynomials of Large Degree over Finite Fields (2017) (1)
Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory (1983) (1)
An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract) (1989) (1)
On the Sample Complexity of MAX-CUT (2006) (1)
Work-Efficient Algorithms For The Construction Of Length-Limited Huffman Codes (2004) (1)
Topics in the theory of computation : selected papers of the International Conference on "Foundations of Computation Theory", FCT '83, Borgholm, Sweden, August 21-27, 1983 (1985) (1)
Approximability of TSP on Power Law Graphs (2015) (1)
An Efficient Parallel Algorithm for the 3MIS Problem (1989) (1)
Approximability of Vertex Cover in Dense Bipartite Hypergraphs (2011) (1)
Metric Construction, Stopping Times and Path Coupling (2005) (1)
On the Parallel Complexity of Matching for Chordal and Path Graphs (1987) (1)
Decidability of "Skolem Matrix Emptiness Problem" Entails Constructability of Exact Regular Expression (1982) (1)
A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2 (2010) (1)
Improved Approximations for General Minimum Cost Scheduling (2001) (0)
05201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms (2005) (0)
C C ] 1 M ar 2 01 8 IDENTITY TESTING AND INTERPOLATION FROM HIGH POWERS OF POLYNOMIALS OF LARGE DEGREE OVER FINITE FIELDS (2018) (0)
On Randomized versus Deterministic Computation ? Zpp a = Exptime a = Exptime (= Dtime(2 Poly )). Furthermore, for All the Sets M : M Ur a () M 2 Exptime (1993) (0)
Approximation Algorithms for Counting Problems in Finite Fields (1991) (0)
An $(\epsilon, \delta)$-Approximation Algorithm of the Number of Zeros of a Multilinear Polynomial over GF[$q$] (1991) (0)
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231) (2021) (0)
Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications (2017) (0)
Randomized Algorithms (Dagstuhl Seminar 9124) (2021) (0)
Improved Inapproximability Results for the Shortest Superstring and the Bounded Metric TSP (2013) (0)
On the Sequential and Parallel Complexity of Matching in Chordal and Strongly Chordal Graphs (2011) (0)
Polynomial Time Approximation S hemes for Metri (2002) (0)
Multiplicity Functions on Omega-Automata (1976) (0)
Fundamentals of Computation Theory: Proceedings of the 1977 International FCT-Conference. Poznan - Kornik, Poland, September 19 - 23, 1977 (1977) (0)
Approximation Schemes for Dense Variants of Feedback Arc Set , Correlation Clustering , and Other Fragile Min Constraint Satisfaction Problems (2009) (0)
Range Reporting for Moving Points on a Grid (2010) (0)
(note) Correctness of Constructing Optimal Alphabetic Trees Revisited (2011) (0)
On the Computational Complexity of Measuring Global Stability of Banking Networks (2013) (0)
Algorithmic Game Theory and the Internet (Dagstuhl Seminar 03291) (2021) (0)
2 The Banking Network Model 2 . 1 Rationale Behind the Model (2012) (0)
N T ] 2 9 O ct 2 02 0 NOISY POLYNOMIAL INTERPOLATION MODULO PRIME POWERS (2020) (0)
Learning Machine for Probabilistically Describable Concepts (1988) (0)
Polynomial Time Approximation S hemes forMAX-BISECTION on Planar and Geometri (2007) (0)
Lower Bounds on Complexity of TestingMembership to a Polygon for Algebraicand Randomized Decision (1993) (0)
Approximation S hemes for Clustering Problems inFinite Metri s and High Dimensional Spa esW (2002) (0)
A Lower Bound on the Size of Algebraic Decision Trees for the MAX Problem (1995) (0)
A Resolution Method for Quantified Boolean Formulas (1990) (0)
A Deterministic Algorithm for Rational Function Interpolations (1988) (0)
Complexity of Symbolic and Numerical Problems (Dagstuhl Seminar 15242) (2015) (0)
Algebraic Complexity and Parallelism (Dagstuhl Seminar 9230) (2021) (0)
An Improved Pattern-Matching Algorithm for Strings with Short Descriptions (1995) (0)
A New Approach to Approximation of Steiner Trees (1995) (0)
Noisy polynomial interpolation modulo prime powers (2020) (0)
On real Turing machines that toss (1995) (0)
On global word definability and constructively definable sets in Nn (1980) (0)
Eecient Ampliiers and Bounded Degree Optimization (2011) (0)
Approximating Hu man Codes in (2002) (0)
Effect of Gromov-Hyperbolicity Parameters on Cuts and Expansions in Graphs and Some Algorithmic Implications (Revised Version) (2016) (0)
The Mixing Time of Glauber Dynamics for Colouring Regular Trees (Revised Version) (2011) (0)
Quadratic Randomized Lower Boundfor the Knapsack Problem (2007) (0)
Efficient Interpolation Algorithms (Dagstuhl Seminar 9149) (2021) (0)
The Complexity ofTwo-DimensionalCompressed Pattern (1996) (0)
Free Structure Tree Automata IV (1974) (0)
1 . 375-Approximation Algorithm forSorting by ReversalsPiotr Berman (2001) (0)
Approximating Transitive Reductions for Directed Networks (Revised Version) (2011) (0)
Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem1 (0)
Randomized Complexity of Linear Arrangements and Polyhedra (1999) (0)
23 10 v 1 [ cs . C C ] 1 5 A pr 2 00 9 Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Croblems with Applications ∗ (2009) (0)
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241) (2011) (0)
Simulating Threshold Circuits by Majority Circuits 1 (revised Version) (1994) (0)
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems (Extended Version) (1998) (0)
Read-Once Threshold Formulas , JustifyingAssignments , and Generic Transformations ( Revised Version ) (2007) (0)
OPTIMAL TRADE-OFF FOR MERKLE TREE TRAVERSAL 277 (2010) (0)
26 11241 – Design and Analysis of Randomized and Approximation Algorithms 2 Table of Contents Executive Summary (2011) (0)
Approximation Schemes for Clustering Problems ( extended abstract ) (2003) (0)
NP-Hardness of the Bandwidth Problem onDense Graphs ( Revised ) (1998) (0)
Randomised $NC$-Classes and the Probably Randomised Circuit Value Problem (1987) (0)
Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP (2006) (0)
Randomized Omega(n2) Lower Bound for Knapsack (1996) (0)
Complexity of Nondeterministic Graph Parameter Testing (Revised Version) (2016) (0)
An Improved Pattern-Mat hing Algorithm for Strings with Short Des riptions (2011) (0)
Fundamentals of Computation Theory, Proceedings of the 1983 International FCT-Conference, Borgholm, Sweden, August 21-27, 1983 (1983) (0)
Mathematisches Forschungsinstitut Oberwolfach Report No . 28 / 2004 Approximation Algorithms for NP-Hard Problems (2004) (0)
The Mixing Rate of Glauber Dynamics for Sampling Colourings of Regular Trees with Few Colours (2011) (0)
Free Structure Tree Automata, III: Normalized Climbing Automata (1973) (0)
Identity testing and interpolation from high powers of polynomials of large degree over finite fields (2017) (0)
Parallel Construction of Minimum Redundancy Length-Limited Codes (2002) (0)
Proceedings of the Bonn Workshop on Foundations of Computing (1987) (0)
08201 – Abstract Collection Design and Analysis of Randomized and Approximation Algorithms — Dagstuhl Seminar — (2008) (0)
There is No Polynomial Deterministic Space Simulation of Two-Way Probabilistic Space (1985) (0)
Dense Steiner problems: Approximation algorithms and inapproximability (2020) (0)
Algorithms for Interpolation of Sparse Rational Functions Using Polynomial Number of Evaluations (1995) (0)
Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields (2017) (0)
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems (2011) (0)
Free Structure Tree Automata, II: Nondeterminstic and Deterministic Regularity (1973) (0)

This paper list is powered by the following services:

Other Resources About Marek Karpinski

en.wikipedia.org

What Schools Are Affiliated With Marek Karpinski?

Marek Karpinski is affiliated with the following schools:

Marek Karpinski's Academic­Influence.com Rankings

Marek Karpinski's Degrees

Similar Degrees You Can Earn

Why Is Marek Karpinski Influential?

Marek Karpinski's Published Works

Published Works

Other Resources About Marek Karpinski

What Schools Are Affiliated With Marek Karpinski?

Image Attributions

Marek Karpinski's AcademicInfluence.com Rankings