Marek Karpinski

Proceedings of the Automata, 1999

1998

Alphabet-Independent Optimal Parallel Search for Three-Dimensional Patterns.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

Computing the Additive Complexity of Algebraic Circuits with Root Extracting.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Simulating Threshold Circuits by Majority Circuits.

[BibT_eX]

[DOI]

Mikael Goldmann

SIAM J. Comput., 1998

On a Sublinear Time Parallel Construction of Optimal Binary Search Trees.

[BibT_eX]

[DOI]

Parallel Process. Lett., 1998

On Some Tighter Inapproximability Results, Further Improvements

[BibT_eX]

[DOI]

Piotr Berman

Wenceslas Fernandez de la Vega

Electron. Colloquium Comput. Complex., 1998

Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

On the Computational Power of Randomized Branching Programs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

On Some Tighter Inapproximability Results

[BibT_eX]

[DOI]

Piotr Berman

Electron. Colloquium Comput. Complex., 1998

On Approximation Intractability of the Bandwidth Problem

[BibT_eX]

[DOI]

Gunter Blache

Juergen Wirtgen

Electron. Colloquium Comput. Complex., 1998

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

[BibT_eX]

[DOI]

Farid M. Ablayev

Electron. Colloquium Comput. Complex., 1998

On the Power of Randomized Ordered Branching Programs

[BibT_eX]

[DOI]

Farid M. Ablayev

Electron. Colloquium Comput. Complex., 1998

Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1998

An exponential lower bound on the size of algebraic decision trees for Max.

[BibT_eX]

[DOI]

Andrew Chi-Chih Yao

Comput. Complex., 1998

An Exponential Lower Bound for Depth 3 Arithmetic Circuits.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997

Correctness of Constructing Optimal Alphabetic Trees Revisited.

[BibT_eX]

[DOI]

Lawrence L. Larmore

Theor. Comput. Sci., 1997

An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions.

[BibT_eX]

Ayumi Shinohara

Nord. J. Comput., 1997

Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1997

On Approximation Hardness of the Bandwidth Problem

[BibT_eX]

[DOI]

Juergen Wirtgen

Electron. Colloquium Comput. Complex., 1997

An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

[BibT_eX]

[DOI]

Juergen Wirtgen

Electron. Colloquium Comput. Complex., 1997

Approximating Dense Cases of Covering Problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees.

[BibT_eX]

[DOI]

Nicolai N. Vorobjov Jr.

Discret. Comput. Geom., 1997

Randomization and the Computational Power of Analytic and Algebraic Decision Trees.

[BibT_eX]

[DOI]

Roman Smolensky

Comput. Complex., 1997

A Lower Bound for Randomized Algebraic Decision Trees.

[BibT_eX]

[DOI]

Friedhelm Meyer auf der Heide

Roman Smolensky

Comput. Complex., 1997

Counting Curves and Their Projections.

[BibT_eX]

[DOI]

Joachim von zur Gathen

Igor E. Shparlinski

Comput. Complex., 1997

Polynominal Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems.

[BibT_eX]

[DOI]

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

Weak and Strong Recognition by 2-way Randomized Automata.

[BibT_eX]

[DOI]

Andris Ambainis

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

Polynomial Time Algorithms for Modules over Finite Dimensional Algebras.

[BibT_eX]

[DOI]

Alexander L. Chistov

Gábor Ivanyos

Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, 1997

Approximating the Volume of General Pfaffian Bodies.

[BibT_eX]

[DOI]

Proceedings of the Structures in Logic and Computer Science, 1997

Effects of Kolmogorov Complexity Present in Inductive Inference as Well.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 8th International Conference, 1997

1996

On Randomized versus Deterministic Computation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

On Some Approximation Problems Concerning Sparse Polynomials over Finite Fields.

[BibT_eX]

[DOI]

Igor E. Shparlinski

Theor. Comput. Sci., 1996

Computability of the Additive Complexity of Algebraic Circuits with Root Extracting.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann.

[BibT_eX]

[DOI]

Andrew M. Odlyzko

Fundam. Informaticae, 1996

Randomized Omega(n2) Lower Bound for Knapsack

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

Efficient Algorithms for Lempel-Zip Encoding (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1996

Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees.

[BibT_eX]

[DOI]

Lawrence L. Larmore

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 7th Annual Symposium, 1996

1995

Resolution for Quantified Boolean Formulas

[BibT_eX]

[DOI]

Hans Kleine Büning

Andreas Flögel

Inf. Comput., February, 1995

VC Dimension of Sigmoidal and General Pfaffian Networks

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

On the Power of Randomized Branching Programs

[BibT_eX]

[DOI]

Farid M. Ablayev

Electron. Colloquium Comput. Complex., 1995

New Approximation Algorithms for the Steiner Tree Problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

Pattern-Matching for Strings with Short Descriptions

[BibT_eX]

[DOI]

Ayumi Shinohara

Electron. Colloquium Comput. Complex., 1995

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

On real Turing machines that toss coins.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Polynomial time approximation schemes for dense instances of NP-hard problems.

[BibT_eX]

[DOI]

Sanjeev Arora

David R. Karger

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Lower Time Bounds for Randomized Computation.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 22nd International Colloquium, 1995

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

[BibT_eX]

[DOI]

Nicolai N. Vorobjov Jr.

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Bounding VC-dimension of neural networks: Progress and prospects.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

Computational Complexity of Sparse Rational Interpolation.

[BibT_eX]

[DOI]

Michael F. Singer

SIAM J. Comput., 1994

Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1994

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

[BibT_eX]

[DOI]

Comput. Complex., 1994

Lower bounds on testing membership to a polyhedron by algebraic decision trees.

[BibT_eX]

[DOI]

Nicolai N. Vorobjov Jr.

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Lower Space Bounds for Randomized Computation.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Approaching the 5/4-Approximation for Rectilinear Steiner Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1994

An Alphabet-Independent Optimal Parallel Search for Three Dimensional Pattern.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 5th Annual Symposium, 1994

Co-Learning of Total Recursive Functions.

[BibT_eX]

[DOI]

Carl H. Smith

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

Co-learnability and FIN-identifiability of Enumerable Classes of Total Recursive Functions.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 1994

1993

VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions.

[BibT_eX]

[DOI]

Thorsten Werther

SIAM J. Comput., 1993

On Randomized Semi-algebraic Test Complexity.

[BibT_eX]

[DOI]

Peter Bürgisser

Thomas Lickteig

J. Complex., 1993

Approximating the Number of Zeroes of a GF[2] Polynomial.

[BibT_eX]

[DOI]

Michael Luby

J. Algorithms, 1993

On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs.

[BibT_eX]

[DOI]

Péter Hajnal

J. Algorithms, 1993

Learning Read-Once Formulas with Queries.

[BibT_eX]

[DOI]

Dana Angluin

Lisa Hellerstein

J. ACM, 1993

A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals.

[BibT_eX]

[DOI]

Proceedings of the Applied Algebra, 1993

1992

Perfect Matching for Regular Graphs is AC°-Hard for the General Matching Problem.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1992

An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3.

[BibT_eX]

[DOI]

Pierre Kelsen

Inf. Process. Lett., 1992

Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis.

[BibT_eX]

[DOI]

Andrew M. Odlyzko

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.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1991

Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication.

[BibT_eX]

[DOI]

Peter Bürgisser

Thomas Lickteig

Comput. Complex., 1991

Algorithms for Sparse Rational Interpolation.

[BibT_eX]

[DOI]

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]

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Approximation Algorithms for Counting Problems in Finite Fields.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1990

Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields.

[BibT_eX]

[DOI]

Michael F. Singer

SIAM J. Comput., 1990

Fast Parallel Algorithms for the Clique Separator Decomposition.

[BibT_eX]

[DOI]

Mark B. Novick

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

On the Complexity of Genuinely Polynomial Computation.

[BibT_eX]

[DOI]

Friedhelm Meyer auf der Heide

Proceedings of the Mathematical Foundations of Computer Science 1990, 1990

Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents

[BibT_eX]

[DOI]

Michael F. Singer

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Subclasses of Quantified Boolean Formulas.

[BibT_eX]

[DOI]

Andreas Flögel

Hans Kleine Büning

Proceedings of the Computer Science Logic, 4th Workshop, 1990

1989

Subtree Isomorphism is NC Reducible to Bipartite Perfect Matching.

[BibT_eX]

[DOI]

Andrzej Lingas

Inf. Process. Lett., 1989

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Lisa Hellerstein

Proceedings of the Second Annual Workshop on Computational Learning Theory, 1989

1988

Parallel Construction of Perfect Matchings and Hamiltonian Cycles on Dense Graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1988

The computational complexity of graph problems with succinct multigraph representation.

[BibT_eX]

[DOI]

Klaus W. Wagner

ZOR Methods Model. Oper. Res., 1988

A Fast Parallel Algorithm for Computing all Maximal Cliques in a Graph and the Related Problems (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the SWAT 88, 1988

Learning Machine for Probabilistically Describable Concepts.

[BibT_eX]

Zbigniew W. Ras

Proceedings of the Methodologies for Intelligent Systems, 1988

Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs

[BibT_eX]

[DOI]

Péter Hajnal

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Boolean Complexity of Algebraic Interpolation Problems.

[BibT_eX]

[DOI]

Proceedings of the CSL '88, 1988

1987

On the Monte Carlo Space Constructible Functions and Seperation Results for Probabilistic Complexity Classes

[BibT_eX]

[DOI]

Inf. Comput., November, 1987

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

[BibT_eX]

[DOI]

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

On the Computational Complexity of Quantified Horn Clauses.

[BibT_eX]

[DOI]

Hans Kleine Büning

Peter H. Schmitt

Proceedings of the CSL '87, 1987

Randomness, Provability, and the Seperation of Monte Carlo Time and Space.

[BibT_eX]

[DOI]

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

[BibT_eX]

[DOI]

Inf. Control., 1986

1985

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

[BibT_eX]

[DOI]

Inf. Control., 1985

Preface

[BibT_eX]

[DOI]

Jan van Leeuwen

Inf. Control., 1985

1982

Decidability of "Skolem Matrix Emptiness Problem" Entails Constructability of Exact Regular Expression.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1982

1980

On global word definability and constructively definable sets in Nn.

[BibT_eX]

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.

[BibT_eX]

Ryszard Danecki

Proceedings of the Fundamentals of Computation Theory, 1979

1977

The Equivalences Problems for Binary EOL-Systems are Decidable.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 1977

1976

Valued Probabilistic Tree Functions.

[BibT_eX]

Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys., 1976

Multiplicity Functions on Omega-Automata.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1976, 1976

1975

Decision Algorithms for Havel's Branching Automata.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1975, 1975

1974

Probablistic Climbing and Sinking Languages.

[BibT_eX]

Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys., 1974

Free Structure Tree Automata IV.

[BibT_eX]

Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys., 1974

Stretching by Probabilistic Tree Automata and Santos Grammars.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science, 1974

1973

Free Structure Tree Automata, III: Normalized Climbing Automata.

[BibT_eX]

Bull. Acad. Pol. des Sci. Ser. Sci. Math. Astron. Phys., 1973

Free Structure Tree Automata, II: Nondeterminstic and Deterministic Regularity.

[BibT_eX]