dblp.uni-trier.dewww.dagstuhl.dewww.uni-trier.de

Marek Karpinski (Selection)

List of publications from the DBLP Bibliography Server - FAQ
Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo


124Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski: An Exponential Lower Bound for Depth 3 Arithmetic Circuits. STOC 1998: 577-582
123Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao: An exponential lower bound on the size of algebraic decision trees for Max. Computational Complexity 7(3): 193-203 (1998)
111Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski: Computing the Additive Complexity of Algebraic Circuits with Root Extracting. SIAM J. Comput. 27(3): 694-701 (1998)
104Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski: Randomized Omega(n2) Lower Bound for Knapsack. STOC 1997: 76-85
100Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees. Computational Complexity 6(4): 357-375 (1997)
99Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Roman Smolensky: Randomization and the Computational Power of Analytic and Algebraic Decision Trees. Computational Complexity 6(4): 376-388 (1997)
98Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Nicolai Vorobjov: Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees. Discrete & Computational Geometry 17(2): 191-215 (1997)
86Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees. STOC 1996: 612-619
84Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski: Randomized Omega(n2) Lower Bound for Knapsack Electronic Colloquium on Computational Complexity (ECCC) 3(58): (1996)
83Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Andrew M. Odlyzko: Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann. Fundam. Inform. 28(3-4): 297-301 (1996)
81Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski: Computability of the Additive Complexity of Algebraic Circuits with Root Extracting. Theor. Comput. Sci. 157(1): 91-99 (1996)
77Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Nicolai Vorobjov: Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. FOCS 1995: 258-265
66Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Andrew Chi-Chih Yao: An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX Electronic Colloquium on Computational Complexity (ECCC) 2(57): (1995)
65Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees Electronic Colloquium on Computational Complexity (ECCC) 2(63): (1995)
57Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Nicolai Vorobjov: Lower bounds on testing membership to a polyhedron by algebraic decision trees. STOC 1994: 635-644
54Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Michael F. Singer: Computational Complexity of Sparse Rational Interpolation. SIAM J. Comput. 23(1): 1-11 (1994)
52Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski: A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals. AAECC 1993: 162-169
43Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Andrew M. Odlyzko: Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis. ISSAC 1992: 117-122
39Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski: An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q] FOCS 1991: 662-669
38Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski: Algorithms for Sparse Rational Interpolation. ISSAC 1991: 7-13
33Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Michael F. Singer: Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents FOCS 1990: 840-846
30Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski, Michael F. Singer: Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields. SIAM J. Comput. 19(6): 1059-1063 (1990)
19Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDima Grigoriev, Marek Karpinski: The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract) FOCS 1987: 166-172

Selection of 23 from 280 records - Marek Karpinski has 122 coauthors

Last update 2012-09-10 CET by the DBLP TeamThis material is Open Data Content released under the ODC-BY 1.0 license — See also our legal information page