Marek Karpinski

Affiliations:
  • University of Bonn, Germany


According to our database1, Marek Karpinski authored at least 252 papers between 1973 and 2021.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2021
Noisy polynomial interpolation modulo prime powers.
J. Complex., 2021

2020
Dense Steiner problems: Approximation algorithms and inapproximability.
CoRR, 2020

2018
A QPTAS for the base of the number of crossing-free structures on a planar point set.
Theor. Comput. Sci., 2018

Tropical dominating sets in vertex-coloured graphs.
J. Discrete Algorithms, 2018

Identity testing and interpolation from high powers of polynomials of large degree over finite fields.
J. Complex., 2018

Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields.
Algorithmica, 2018

Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications.
Algorithmica, 2018

2017
Identity Testing from High Powers of Polynomials of Large Degree over Finite Fields.
CoRR, 2017

2016
Approximation Complexity of Max-Cut on Power Law Graphs.
CoRR, 2016

Tropical Dominating Sets in Vertex-Coloured Graphs.
Proceedings of the WALCOM: Algorithms and Computation - 10th International Workshop, 2016

2015
Inapproximability of dominating set on power law graphs.
Theor. Comput. Sci., 2015

Approximation hardness of graphic TSP on cubic graphs.
RAIRO Oper. Res., 2015

Nearly tight approximation bounds for vertex cover on dense k-uniform k-partite hypergraphs.
J. Discrete Algorithms, 2015

New inapproximability bounds for TSP.
J. Comput. Syst. Sci., 2015

Generalized Wong sequences and their applications to Edmonds' problems.
J. Comput. Syst. Sci., 2015

Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies.
Electron. Colloquium Comput. Complex., 2015

Complexity of Symbolic and Numerical Problems (Dagstuhl Seminar 15242).
Dagstuhl Reports, 2015

Explicit Bounds for Nondeterministically Testable Hypergraph Parameters.
CoRR, 2015

On the Complexity of Nondeterministically Testable Hypergraph Parameters.
CoRR, 2015

On the Approximability of Independent Set Problem on Power Law Graphs.
CoRR, 2015

Approximability of TSP on Power Law Graphs.
CoRR, 2015

Node Expansions and Cuts in Gromov-hyperbolic Graphs.
CoRR, 2015

2014
Approximate Counting of Matchings in (3,3)-Hypergraphs.
Electron. Colloquium Comput. Complex., 2014

Complexity of Nondeterministic Graph Parameter Testing.
CoRR, 2014

Limits of CSP Problems and Efficient Parameter Testing.
CoRR, 2014

A QPTAS for the Base of the Number of Triangulations of a Planar Point Set.
CoRR, 2014

On the Computational Complexity of Measuring Global Stability of Banking Networks.
Algorithmica, 2014

Approximate Counting of Matchings in (3, 3)-Hypergraphs.
Proceedings of the Algorithm Theory - SWAT 2014, 2014

2013
Optimal cuts and partitions in tree metrics in polynomial time.
Inf. Process. Lett., 2013

Algorithmic Perspectives of Network Transitive Reduction Problems and their Applications to Synthesis and Analysis of Biological Networks.
CoRR, 2013

Improved Inapproximability Results for the Shortest Superstring and Related Problems.
Proceedings of the Nineteenth Computing: The Australasian Theory Symposium, 2013

Approximate Counting of Matchings in Sparse Uniform Hypergraphs.
Proceedings of the 10th Meeting on Analytic Algorithmics and Combinatorics, 2013

2012
Approximating vertex cover in dense hypergraphs.
J. Discrete Algorithms, 2012

On Approximation Lower Bounds for TSP with Bounded Metrics.
Electron. Colloquium Comput. Complex., 2012

Deterministic Polynomial Factoring and Association Schemes.
Electron. Colloquium Comput. Complex., 2012

Improved Approximation Lower Bounds for Vertex Cover on Power Law Graphs and Some Generalizations
CoRR, 2012

Optimal Cuts and Bisections on the Real Line in Polynomial Time
CoRR, 2012

Approximate Counting of Matchings in Sparse Hypergraphs
CoRR, 2012

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems.
Algorithmica, 2012

2011
Approximating Subdense Instances of Covering Problems.
Electron. Notes Discret. Math., 2011

Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs.
Electron. Colloquium Comput. Complex., 2011

Improved Lower Bounds for the Shortest Superstring and Related Problems.
Electron. Colloquium Comput. Complex., 2011

Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241).
Dagstuhl Reports, 2011

On Systemic Stability of Banking Networks
CoRR, 2011

Top-K Color Queries for Document Retrieval.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
The mixing time of Glauber dynamics for coloring regular trees.
Random Struct. Algorithms, 2010

Cycles and paths in edge-colored graphs with given degrees.
J. Graph Theory, 2010

Computational Complexity of the Perfect Matching Problem in Hypergraphs with Subcritical Density.
Int. J. Found. Comput. Sci., 2010

Range Reporting for Moving Points on a Grid
CoRR, 2010

Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs.
Proceedings of the LATIN 2010: Theoretical Informatics, 2010

Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament.
Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2.
Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

2009
Deterministic Polynomial Time Algorithms for Matrix Completion Problems.
Electron. Colloquium Comput. Complex., 2009

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications
CoRR, 2009

A Fast Algorithm for Adaptive Prefix Coding.
Algorithmica, 2009

1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2.
Proceedings of the Algorithms and Data Structures, 11th International Symposium, 2009

The Complexity of Perfect Matching Problems on Dense Hypergraphs.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Low-Memory Adaptive Prefix Coding.
Proceedings of the 2009 Data Compression Conference (DCC 2009), 2009

Space Efficient Multi-dimensional Range Reporting.
Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

2008
Path coupling using stopping times and counting independent sets and colorings in hypergraphs.
Random Struct. Algorithms, 2008

Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems.
Electron. Colloquium Comput. Complex., 2008

Schemes for Deterministic Polynomial Factoring.
Electron. Colloquium Comput. Complex., 2008

Trading GRH for algebra: algorithms for factoring polynomials and related structures.
Electron. Colloquium Comput. Complex., 2008

1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two.
Electron. Colloquium Comput. Complex., 2008

A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two
CoRR, 2008

Approximating Transitivity in Directed Networks
CoRR, 2008

The Mixing Time of Glauber Dynamics for Colouring Regular Trees
CoRR, 2008

08201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms.
Proceedings of the Design and Analysis of Randomized and Approximation Algorithms, 11.05., 2008

Searching for Frequent Colors in Rectangles.
Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

2007
Optimal trade-off for Merkle tree traversal.
Theor. Comput. Sci., 2007

1.0957-Approximation Algorithm for Random MAX-3SAT.
RAIRO Oper. Res., 2007

Embedding Point Sets into Plane Graphs of Small Dilation.
Int. J. Comput. Geom. Appl., 2007

Approximating Transitive Reductions for Directed Networks.
Electron. Colloquium Comput. Complex., 2007

Computational complexity of some restricted instances of 3-SAT.
Discret. Appl. Math., 2007

2006
Algorithms for Construction of Optimal and Almost-optimal Length-restricted Codes.
Parallel Process. Lett., 2006

TSP with bounded metrics.
J. Comput. Syst. Sci., 2006

Approximation of Global MAX-CSP Problems.
Electron. Colloquium Comput. Complex., 2006

Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP.
Electron. Colloquium Comput. Complex., 2006

On the Sample Complexity of MAX-CUT.
Electron. Colloquium Comput. Complex., 2006

Approximation Complexity of Nondense Instances of MAX-CUT.
Electron. Colloquium Comput. Complex., 2006

8/7-approximation algorithm for (1, 2)-TSP.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Stopping Times, Metrics and Approximate Counting.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

2005
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs.
SIAM J. Comput., 2005

On the computational power of probabilistic and quantum branching program.
Inf. Comput., 2005

Metric Construction, Stopping Times and Path Coupling.
Electron. Colloquium Comput. Complex., 2005

8/7-Approximation Algorithm for (1,2)-TSP
Electron. Colloquium Comput. Complex., 2005

Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs
Electron. Colloquium Comput. Complex., 2005

Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem.
Algorithmica, 2005

Tensor decomposition and approximation schemes for constraint satisfaction problems.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

On the Complexity of Global Constraint Satisfaction.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Optimal trade-off for merkle tree traversal.
Proceedings of the ICETE 2005, 2005

Path Coupling Using Stopping Times.
Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

Predecessor Queries in Constant Time?.
Proceedings of the Algorithms, 2005

05201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms.
Proceedings of the Design and Analysis of Randomized and Approximation Algorithms, 15.05., 2005

2004
Work-Efficient Algorithms For The Construction Of Length-Limited Huffman Codes.
Parallel Process. Lett., 2004

Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs.
Fundam. Informaticae, 2004

A Note on Traversing Skew Merkle Trees
Electron. Colloquium Comput. Complex., 2004

Computational Complexity of Some Restricted Instances of 3SAT
Electron. Colloquium Comput. Complex., 2004

Approximation schemes for Metric Bisection and partitioning.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003
Random sampling and approximation of MAX-CSPs.
J. Comput. Syst. Sci., 2003

A lower bound for integer multiplication on randomized ordered read-once branching programs.
Inf. Comput., 2003

Approximability of Hypergraph Minimum Bisection.
Electron. Colloquium Comput. Complex., 2003

Approximation Hardness of Short Symmetric Instances of MAX-3SAT.
Electron. Colloquium Comput. Complex., 2003

Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT
Electron. Colloquium Comput. Complex., 2003

Improved Approximation Lower Bounds on Small Occurrence Optimization
Electron. Colloquium Comput. Complex., 2003

Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem.
Proceedings of the Algorithms and Data Structures, 8th International Workshop, 2003

Approximation schemes for clustering problems.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002
On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts.
J. Comput. Syst. Sci., 2002

Randomized splay trees: Theoretical and experimental results.
Inf. Process. Lett., 2002

Learning by the Process of Elimination.
Inf. Comput., 2002

9/8-Approximation Algorithm for Random MAX-3SAT
Electron. Colloquium Comput. Complex., 2002

On Approximability of Minimum Bisection Problem
Electron. Colloquium Comput. Complex., 2002

A Polynomial Time Approximation Scheme for Subdense MAX-CUT
Electron. Colloquium Comput. Complex., 2002

A Polynomial Time Approximation Scheme for Metric MIN-BISECTION
Electron. Colloquium Comput. Complex., 2002

Parallel Construction of Minimum Redundancy Length-Limited Codes
Electron. Colloquium Comput. Complex., 2002

Polynomial Time Approximation Schemes for Metric Min-Sum Clustering
Electron. Colloquium Comput. Complex., 2002

Approximating Huffman Codes in Parallel
Electron. Colloquium Comput. Complex., 2002

Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Approximability of the Minimum Bisection Problem: An Algorithmic Challenge.
Proceedings of the Mathematical Foundations of Computer Science 2002, 2002

2001
On BPP versus NPcoNP for ordered read-once branching programs.
Theor. Comput. Sci., 2001

A note on approximating Max-Bisection on regular graphs.
Inf. Process. Lett., 2001

Random Sampling and Approximation of MAX-CSP Problems
Electron. Colloquium Comput. Complex., 2001

Improved Approximations for General Minimum Cost Scheduling
Electron. Colloquium Comput. Complex., 2001

Efficient Amplifiers and Bounded Degree Optimization.
Electron. Colloquium Comput. Complex., 2001

1.375-Approximation Algorithm for Sorting by Reversals
Electron. Colloquium Comput. Complex., 2001

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

Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction
Electron. Colloquium Comput. Complex., 2001

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION
Electron. Colloquium Comput. Complex., 2001

Approximating Minimum Unsatisfiability of Linear Equations
Electron. Colloquium Comput. Complex., 2001

Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems.
Algorithmica, 2001

On Computational Power of Quantum Branching Programs.
Proceedings of the Fundamentals of Computation Theory, 13th International Symposium, 2001

2000
Zero testing of p-adic and modular polynomials.
Theor. Comput. Sci., 2000

Approximability of Dense Instances of NEAREST CODEWORD Problem
Electron. Colloquium Comput. Complex., 2000

Approximation Hardness of TSP with Bounded Metrics
Electron. Colloquium Comput. Complex., 2000

A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs
Electron. Colloquium Comput. Complex., 2000

Approximation Algorithms for MAX-BISECTION on Low Degree Reg ular Graphs and Planar Graphs
Electron. Colloquium Comput. Complex., 2000

Improved Approximation of MAX-CUT on Graphs of Bounded Degree
Electron. Colloquium Comput. Complex., 2000

On-Line Load Balancing for Related Machines
Electron. Colloquium Comput. Complex., 2000

1999
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems.
J. Comput. Syst. Sci., 1999

On the Approximation Hardness of Dense TSP and Other Path Problems.
Inf. Process. Lett., 1999

On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials
Electron. Colloquium Comput. Complex., 1999

Randomized Complexity of Linear Arrangements and Polyhedra
Electron. Colloquium Comput. Complex., 1999

A Note on Las Vegas OBDDs
Electron. Colloquium Comput. Complex., 1999

Compact cellular algebras and permutation groups.
Discret. Math., 1999

Quantum Finite Multitape Automata.
Proceedings of the SOFSEM '99, Theory and Practice of Informatics, 26th Conference on Current Trends in Theory and Practice of Informatics, Milovy, Czech Republic, November 27, 1999

On Some Tighter Inapproximability Results (Extended Abstract).
Proceedings of the Automata, 1999

1998
Alphabet-Independent Optimal Parallel Search for Three-Dimensional Patterns.
Theor. Comput. Sci., 1998

Computing the Additive Complexity of Algebraic Circuits with Root Extracting.
SIAM J. Comput., 1998

Simulating Threshold Circuits by Majority Circuits.
SIAM J. Comput., 1998

On a Sublinear Time Parallel Construction of Optimal Binary Search Trees.
Parallel Process. Lett., 1998

On Some Tighter Inapproximability Results, Further Improvements
Electron. Colloquium Comput. Complex., 1998

Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT
Electron. Colloquium Comput. Complex., 1998

On the Computational Power of Randomized Branching Programs
Electron. Colloquium Comput. Complex., 1998

On Some Tighter Inapproximability Results
Electron. Colloquium Comput. Complex., 1998

On Approximation Intractability of the Bandwidth Problem
Electron. Colloquium Comput. Complex., 1998

A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs
Electron. Colloquium Comput. Complex., 1998

On the Power of Randomized Ordered Branching Programs
Electron. Colloquium Comput. Complex., 1998

Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs.
Discret. Appl. Math., 1998

An exponential lower bound on the size of algebraic decision trees for Max.
Comput. Complex., 1998

An Exponential Lower Bound for Depth 3 Arithmetic Circuits.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997
Correctness of Constructing Optimal Alphabetic Trees Revisited.
Theor. Comput. Sci., 1997

An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions.
Nord. J. Comput., 1997

Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks.
J. Comput. Syst. Sci., 1997

On Approximation Hardness of the Bandwidth Problem
Electron. Colloquium Comput. Complex., 1997

An Approximation Algorithm for the Bandwidth Problem on Dense Graphs
Electron. Colloquium Comput. Complex., 1997

Approximating Dense Cases of Covering Problems
Electron. Colloquium Comput. Complex., 1997

Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees.
Discret. Comput. Geom., 1997

Randomization and the Computational Power of Analytic and Algebraic Decision Trees.
Comput. Complex., 1997

A Lower Bound for Randomized Algebraic Decision Trees.
Comput. Complex., 1997

Counting Curves and Their Projections.
Comput. Complex., 1997

Polynominal Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

Weak and Strong Recognition by 2-way Randomized Automata.
Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

Polynomial Time Algorithms for Modules over Finite Dimensional Algebras.
Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, 1997

Approximating the Volume of General Pfaffian Bodies.
Proceedings of the Structures in Logic and Computer Science, 1997

Effects of Kolmogorov Complexity Present in Inductive Inference as Well.
Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

1996
On Randomized versus Deterministic Computation.
Theor. Comput. Sci., 1996

On Some Approximation Problems Concerning Sparse Polynomials over Finite Fields.
Theor. Comput. Sci., 1996

Computability of the Additive Complexity of Algebraic Circuits with Root Extracting.
Theor. Comput. Sci., 1996

Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann.
Fundam. Informaticae, 1996

Randomized Omega(n<sup>2</sup>) Lower Bound for Knapsack
Electron. Colloquium Comput. Complex., 1996

Efficient Algorithms for Lempel-Zip Encoding (Extended Abstract).
Proceedings of the Algorithm Theory, 1996

Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract).
Proceedings of the Combinatorial Pattern Matching, 7th Annual Symposium, 1996

1995
Resolution for Quantified Boolean Formulas
Inf. Comput., February, 1995

VC Dimension of Sigmoidal and General Pfaffian Networks
Electron. Colloquium Comput. Complex., 1995

On the Power of Randomized Branching Programs
Electron. Colloquium Comput. Complex., 1995

New Approximation Algorithms for the Steiner Tree Problems
Electron. Colloquium Comput. Complex., 1995

Pattern-Matching for Strings with Short Descriptions
Electron. Colloquium Comput. Complex., 1995

1.757 and 1.267 - Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems
Electron. Colloquium Comput. Complex., 1995

On real Turing machines that toss coins.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Polynomial time approximation schemes for dense instances of <i>NP</i>-hard problems.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Lower Time Bounds for Randomized Computation.
Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Bounding VC-dimension of neural networks: Progress and prospects.
Proceedings of the Computational Learning Theory, Second European Conference, 1995

1994
An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph.
Theor. Comput. Sci., 1994

Computational Complexity of Sparse Rational Interpolation.
SIAM J. Comput., 1994

Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks
Electron. Colloquium Comput. Complex., 1994

An Algorithm to Learn Read-Once Threshold Formulas, and Transformations Between Learning Models.
Comput. Complex., 1994

Lower bounds on testing membership to a polyhedron by algebraic decision trees.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Lower Space Bounds for Randomized Computation.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Approaching the 5/4-Approximation for Rectilinear Steiner Trees.
Proceedings of the Algorithms, 1994

An Alphabet-Independent Optimal Parallel Search for Three Dimensional Pattern.
Proceedings of the Combinatorial Pattern Matching, 5th Annual Symposium, 1994

Co-Learning of Total Recursive Functions.
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

Co-learnability and FIN-identifiability of Enumerable Classes of Total Recursive Functions.
Proceedings of the Algorithmic Learning Theory, 1994

1993
VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions.
SIAM J. Comput., 1993

On Randomized Semi-algebraic Test Complexity.
J. Complex., 1993

Approximating the Number of Zeroes of a GF[2] Polynomial.
J. Algorithms, 1993

On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs.
J. Algorithms, 1993

Learning Read-Once Formulas with Queries.
J. ACM, 1993

A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals.
Proceedings of the Applied Algebra, 1993

1992
Perfect Matching for Regular Graphs is AC°-Hard for the General Matching Problem.
J. Comput. Syst. Sci., 1992

An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3.
Inf. Process. Lett., 1992

Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis.
Proceedings of the 1992 International Symposium on Symbolic and Algebraic Computation, 1992

1991
On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials Over Finite Fields.
Theor. Comput. Sci., 1991

Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication.
Comput. Complex., 1991

Algorithms for Sparse Rational Interpolation.
Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, 1991

An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Approximation Algorithms for Counting Problems in Finite Fields.
Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1990
Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields.
SIAM J. Comput., 1990

Fast Parallel Algorithms for the Clique Separator Decomposition.
Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

On the Complexity of Genuinely Polynomial Computation.
Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Subclasses of Quantified Boolean Formulas.
Proceedings of the Computer Science Logic, 4th Workshop, 1990

1989
Subtree Isomorphism is NC Reducible to Bipartite Perfect Matching.
Inf. Process. Lett., 1989

An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract)
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Learning Read-Once Formulas Using Membership Queries.
Proceedings of the Second Annual Workshop on Computational Learning Theory, 1989

1988
Parallel Construction of Perfect Matchings and Hamiltonian Cycles on Dense Graphs.
Theor. Comput. Sci., 1988

The computational complexity of graph problems with succinct multigraph representation.
ZOR Methods Model. Oper. Res., 1988

A Fast Parallel Algorithm for Computing all Maximal Cliques in a Graph and the Related Problems (Extended Abstract).
Proceedings of the SWAT 88, 1988

Learning Machine for Probabilistically Describable Concepts.
Proceedings of the Methodologies for Intelligent Systems, 1988

Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Boolean Complexity of Algebraic Interpolation Problems.
Proceedings of the CSL '88, 1988

1987
On the Monte Carlo Space Constructible Functions and Seperation Results for Probabilistic Complexity Classes
Inf. Comput., November, 1987

The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract)
Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

On the Computational Complexity of Quantified Horn Clauses.
Proceedings of the CSL '87, 1987

Randomness, Provability, and the Seperation of Monte Carlo Time and Space.
Proceedings of the Computation Theory and Logic, In Memory of Dieter Rödding, 1987

1986
On the Power of Two-Way Random Generators and the Impossibility of Deterministic Poly-Space Simulation
Inf. Control., 1986

1985
There Is No Polynomial Deterministic Space Simulation of Probabilistic Space with a Two-Way Random-Tape Generator
Inf. Control., 1985

Preface
Inf. Control., 1985

1982
Decidability of "Skolem Matrix Emptiness Problem" Entails Constructability of Exact Regular Expression.
Theor. Comput. Sci., 1982

1980
On global word definability and constructively definable sets in N<sub>n</sub>.
Proceedings of the Proc. 5eme Colleque de Lille sur les Arbres en Algebre et en Programmation, 1980

1979
Decidability Results on Plane Automata Searching Mazes.
Proceedings of the Fundamentals of Computation Theory, 1979

1977
The Equivalences Problems for Binary EOL-Systems are Decidable.
Proceedings of the Fundamentals of Computation Theory, 1977

1976
Valued Probabilistic Tree Functions.
Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys., 1976

Multiplicity Functions on Omega-Automata.
Proceedings of the Mathematical Foundations of Computer Science 1976, 1976

1975
Decision Algorithms for Havel's Branching Automata.
Proceedings of the Mathematical Foundations of Computer Science 1975, 1975

1974
Probablistic Climbing and Sinking Languages.
Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys., 1974

Free Structure Tree Automata IV.
Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys., 1974

Stretching by Probabilistic Tree Automata and Santos Grammars.
Proceedings of the Mathematical Foundations of Computer Science, 1974

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

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


  Loading...