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

Marek Karpinski Home Page Coauthor index pubzone.org

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

DBLP keys2012
278Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Andrzej Lingas: Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. Algorithmica 64(2): 295-310 (2012)
277Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Richard Schmied: On Approximation Lower Bounds for TSP with Bounded Metrics CoRR abs/1201.5821: (2012)
276Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Andrzej Rucinski, Edyta Szymanska: Approximate Counting of Matchings in Sparse Hypergraphs CoRR abs/1202.5885: (2012)
275Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Andrzej Rucinski, Edyta Szymanska: Approximate Counting of Matchings in Sparse Uniform Hypergraphs CoRR abs/1204.5335: (2012)
274Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLManuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena: Deterministic Polynomial Factoring and Association Schemes CoRR abs/1205.5653: (2012)
273Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Richard Schmied: On Approximation Lower Bounds for TSP with Bounded Metrics. Electronic Colloquium on Computational Complexity (ECCC) 19: 8 (2012)
272Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann: Approximating vertex cover in dense hypergraphs. J. Discrete Algorithms 13: 67-77 (2012)
271Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLGábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena: Trading GRH for algebra: Algorithms for factoring polynomials and related structures. Math. Comput. 81(277): (2012)
2011
270Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Warren Schudy: Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems. APPROX-RANDOM 2011: 277-288
269Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: Top-K Color Queries for Document Retrieval. SODA 2011: 401-411
268Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Richard Schmied, Claus Viehmann: Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs CoRR abs/1107.2000: (2011)
267Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Bhaskar DasGupta, Lakshmi Kaligounder, Marek Karpinski: On Systemic Stability of Banking Networks CoRR abs/1110.3546: (2011)
266Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Richard Schmied: Improved Lower Bounds for the Shortest Superstring and Related Problems CoRR abs/1111.5442: (2011)
265Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMartin E. Dyer, Uriel Feige, Alan M. Frieze, Marek Karpinski: Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). Dagstuhl Reports 1(6): 24-53 (2011)
264Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Richard Schmied: Improved Lower Bounds for the Shortest Superstring and Related Problems. Electronic Colloquium on Computational Complexity (ECCC) 18: 156 (2011)
263Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Richard Schmied, Claus Viehmann: Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs. Electronic Colloquium on Computational Complexity (ECCC) 18: 98 (2011)
262Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann: Approximating Subdense Instances of Covering Problems. Electronic Notes in Discrete Mathematics 37: 297-302 (2011)
2010
261Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Andrzej Lingas: Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. COCOON 2010: 226-234
260Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Alexander Zelikovsky: A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2. ISAAC (1) 2010: 15-24
259Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Warren Schudy: Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. ISAAC (1) 2010: 3-14
258Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Andrzej Rucinski, Edyta Szymanska: Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs. LATIN 2010: 662-673
257Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, J. Ian Munro, Yakov Nekrich: Range Reporting for Moving Points on a Grid CoRR abs/1002.3511: (2010)
256Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Warren Schudy: Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament CoRR abs/1006.4396: (2010)
255Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: Top-K Color Queries for Document Retrieval CoRR abs/1007.1361: (2010)
254Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann: Approximating Subdense Instances of Covering Problems CoRR abs/1011.0078: (2010)
253Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann: Approximating Vertex Cover in Dense Hypergraphs CoRR abs/1012.2573: (2010)
252Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Andrzej Rucinski, Edyta Szymanska: Computational Complexity of the Perfect Matching Problem in Hypergraphs with Subcritical Density. Int. J. Found. Comput. Sci. 21(6): 905-924 (2010)
251Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLA. Abouelaoualim, Kinkar Chandra Das, Wenceslas Fernandez de la Vega, Marek Karpinski, Yannis Manoussakis, Carlos A. J. Martinhon, Rachid Saad: Cycles and paths in edge-colored graphs with given degrees. Journal of Graph Theory 64(1): 63-86 (2010)
250Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLLeslie Ann Goldberg, Mark Jerrum, Marek Karpinski: The mixing time of Glauber dynamics for coloring regular trees. Random Struct. Algorithms 36(4): 464-476 (2010)
249Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLGábor Ivanyos, Marek Karpinski, Nitin Saxena: Deterministic Polynomial Time Algorithms for Matrix Completion Problems. SIAM J. Comput. 39(8): 3736-3751 (2010)
2009
248Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: Space Efficient Multi-dimensional Range Reporting. COCOON 2009: 215-224
247Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLTravis Gagie, Marek Karpinski, Yakov Nekrich: Low-Memory Adaptive Prefix Coding. DCC 2009: 13-22
246Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Andrzej Rucinski, Edyta Szymanska: The Complexity of Perfect Matching Problems on Dense Hypergraphs. ISAAC 2009: 626-636
245Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLGábor Ivanyos, Marek Karpinski, Nitin Saxena: Schemes for deterministic polynomial factoring. ISSAC 2009: 191-198
244Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Warren Schudy: Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. STOC 2009: 313-322
243Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Bhaskar DasGupta, Marek Karpinski: Approximating Transitive Reductions for Directed Networks. WADS 2009: 74-85
242Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Alexander Zelikovsky: 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2. WADS 2009: 86-97
241Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: A Fast Algorithm for Adaptive Prefix Coding. Algorithmica 55(1): 29-41 (2009)
240Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Andrzej Lingas: Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications CoRR abs/0904.2310: (2009)
239Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLGábor Ivanyos, Marek Karpinski, Nitin Saxena: Deterministic Polynomial Time Algorithms for Matrix Completion Problems CoRR abs/0907.0774: (2009)
238Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Warren Schudy: Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems CoRR abs/0911.2214: (2009)
237Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLGábor Ivanyos, Marek Karpinski, Nitin Saxena: Deterministic Polynomial Time Algorithms for Matrix Completion Problems. Electronic Colloquium on Computational Complexity (ECCC) 16: 58 (2009)
2008
236no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: Searching for Frequent Colors in Rectangles. CCCG 2008
235Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLGábor Ivanyos, Marek Karpinski, Nitin Saxena: Schemes for Deterministic Polynomial Factoring CoRR abs/0804.1974: (2008)
234Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: Searching for Frequent Colors in Rectangles CoRR abs/0805.1348: (2008)
233Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLLeslie Ann Goldberg, Mark Jerrum, Marek Karpinski: The Mixing Time of Glauber Dynamics for Colouring Regular Trees CoRR abs/0806.0921: (2008)
232Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: Space-Efficient Multi-Dimensional Range Reporting CoRR abs/0806.4361: (2008)
231Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Bhaskar DasGupta, Marek Karpinski: Approximating Transitivity in Directed Networks CoRR abs/0809.0188: (2008)
230Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Alexander Zelikovsky: 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two CoRR abs/0810.1851: (2008)
229Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLGábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena: Trading GRH for algebra: algorithms for factoring polynomials and related structures CoRR abs/0811.3165: (2008)
228Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Warren Schudy: Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems CoRR abs/0811.3244: (2008)
227Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLTravis Gagie, Marek Karpinski, Yakov Nekrich: Low-Memory Adaptive Prefix Coding CoRR abs/0811.3602: (2008)
226Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Alexander Zelikovsky: A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two CoRR abs/0812.2137: (2008)
225Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLGábor Ivanyos, Marek Karpinski, Nitin Saxena: Schemes for Deterministic Polynomial Factoring. Electronic Colloquium on Computational Complexity (ECCC) 15(043): (2008)
224Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Alexander Zelikovsky: 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two. Electronic Colloquium on Computational Complexity (ECCC) 15(094): (2008)
223Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLGábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena: Trading GRH for algebra: algorithms for factoring polynomials and related structures. Electronic Colloquium on Computational Complexity (ECCC) 15(099): (2008)
222Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Warren Schudy: Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems. Electronic Colloquium on Computational Complexity (ECCC) 15(101): (2008)
221Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMagnus Bordewich, Martin E. Dyer, Marek Karpinski: Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Random Struct. Algorithms 32(3): 375-399 (2008)
2007
220Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Alexander D. Scott: Computational complexity of some restricted instances of 3-SAT. Discrete Applied Mathematics 155(5): 649-653 (2007)
219Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Bhaskar DasGupta, Marek Karpinski: Approximating Transitive Reductions for Directed Networks. Electronic Colloquium on Computational Complexity (ECCC) 14(119): (2007)
218Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAnnette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, Marek Karpinski, Christian Knauer, Andrzej Lingas: Embedding Point Sets into Plane Graphs of Small Dilation. Int. J. Comput. Geometry Appl. 17(3): 201-230 (2007)
217Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Yakov Nekrich: Approximating Huffman codes in parallel. J. Discrete Algorithms 5(3): 479-490 (2007)
216Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski: 1.0957-Approximation Algorithm for Random MAX-3SAT. RAIRO - Operations Research 41(1): 95-103 (2007)
215Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Yakov Nekrich: Optimal trade-off for Merkle tree traversal. Theor. Comput. Sci. 372(1): 26-36 (2007)
2006
214Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMagnus Bordewich, Martin E. Dyer, Marek Karpinski: Stopping Times, Metrics and Approximate Counting. ICALP (1) 2006: 108-119
213Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: 8/7-approximation algorithm for (1, 2)-TSP. SODA 2006: 641-648
212Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski: Approximation Complexity of Nondense Instances of MAX-CUT. Electronic Colloquium on Computational Complexity (ECCC) 13(101): (2006)
211Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski: On the Sample Complexity of MAX-CUT. Electronic Colloquium on Computational Complexity (ECCC) 13(104): (2006)
210Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Approximation of Global MAX-CSP Problems. Electronic Colloquium on Computational Complexity (ECCC) 13(124): (2006)
209Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski: Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP. Electronic Colloquium on Computational Complexity (ECCC) 13(155): (2006)
208Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLLars Engebretsen, Marek Karpinski: TSP with bounded metrics. J. Comput. Syst. Sci. 72(4): 509-546 (2006)
207Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: Algorithms for Construction of Optimal and Almost-optimal Length-restricted Codes. Parallel Processing Letters 16(1): 81-92 (2006)
2005
206Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: Algorithms for Construction of Optimal and Almost-Optimal Length-Restricted Codes. DCC 2005: 464
205Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: Predecessor Queries in Constant Time?. ESA 2005: 238-248
204Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMagnus Bordewich, Martin E. Dyer, Marek Karpinski: Path Coupling Using Stopping Times. FCT 2005: 19-31
203no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: Optimal trade-off for merkle tree traversal. ICETE 2005: 275-282
202Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAnnette Ebbers-Baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas: Embedding Point Sets into Plane Graphs of Small Dilation. ISAAC 2005: 5-16
201Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLCristina Bazgan, Marek Karpinski: On the Complexity of Global Constraint Satisfaction. ISAAC 2005: 624-633
200Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala: Tensor decomposition and approximation schemes for constraint satisfaction problems. STOC 2005: 747-754
199Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky: Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem. Algorithmica 42(2): 109-120 (2005)
198Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMagnus Bordewich, Martin E. Dyer, Marek Karpinski: Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs Electronic Colloquium on Computational Complexity (ECCC)(002): (2005)
197Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: 8/7-Approximation Algorithm for (1,2)-TSP Electronic Colloquium on Computational Complexity (ECCC)(069): (2005)
196Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMagnus Bordewich, Martin E. Dyer, Marek Karpinski: Metric Construction, Stopping Times and Path Coupling. Electronic Colloquium on Computational Complexity (ECCC)(151): (2005)
195Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLFarid M. Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, Chris Pollett: On the computational power of probabilistic and quantum branching program. Inf. Comput. 203(2): 145-162 (2005)
194Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLKlaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel: Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. SIAM J. Comput. 35(1): 110-119 (2005)
2004
193Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon: Approximation schemes for Metric Bisection and partitioning. SODA 2004: 506-515
192Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Yakov Nekrich: Optimal Trade-Off for Merkle Tree Traversal Electronic Colloquium on Computational Complexity (ECCC)(049): (2004)
191Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Alexander D. Scott: Computational Complexity of Some Restricted Instances of 3SAT Electronic Colloquium on Computational Complexity (ECCC)(111): (2004)
190Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: A Note on Traversing Skew Merkle Trees Electronic Colloquium on Computational Complexity (ECCC)(118): (2004)
189Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Miroslaw Kowaluk, Andrzej Lingas: Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs. Fundam. Inform. 62(3-4): 369-375 (2004)
188Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Lawrence L. Larmore, Yakov Nekrich: Work-Efficient Algorithms For The Construction Of Length-Limited Huffman Codes. Parallel Processing Letters 14(1): 99-105 (2004)
2003
187Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani: Approximation schemes for clustering problems. STOC 2003: 50-58
186Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky: Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem. WADS 2003: 401-411
185Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: Improved Approximation Lower Bounds on Small Occurrence Optimization Electronic Colloquium on Computational Complexity (ECCC) 10(008): (2003)
184Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Alex D. Scott: Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT Electronic Colloquium on Computational Complexity (ECCC) 10(022): (2003)
183Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Alex D. Scott: Approximation Hardness of Short Symmetric Instances of MAX-3SAT Electronic Colloquium on Computational Complexity (ECCC)(049): (2003)
182Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: Approximability of Hypergraph Minimum Bisection Electronic Colloquium on Computational Complexity (ECCC)(056): (2003)
181Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLFarid M. Ablayev, Marek Karpinski: A lower bound for integer multiplication on randomized ordered read-once branching programs. Inf. Comput. 186(1): 78-89 (2003)
180Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLNoga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Random sampling and approximation of MAX-CSPs. J. Comput. Syst. Sci. 67(2): 212-243 (2003)
179Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLCristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski: Polynomial time approximation schemes for dense instances of minimum constraint satisfaction. Random Struct. Algorithms 23(1): 73-91 (2003)
2002
178Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Sridhar Hannenhalli, Marek Karpinski: 1.375-Approximation Algorithm for Sorting by Reversals. ESA 2002: 200-210
177Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION. ICALP 2002: 623-632
176Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Yakov Nekrich: Approximating Huffman Codes in Parallel. ICALP 2002: 845-855
175Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Approximability of the Minimum Bisection Problem: An Algorithmic Challenge. MFCS 2002: 59-67
174Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: Approximating minimum unsatisfiability of linear equations. SODA 2002: 514-516
173Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLBéla Csaba, Marek Karpinski, Piotr Krysta: Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems. SODA 2002: 74-83
172Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLNoga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Random sampling and approximation of MAX-CSP problems. STOC 2002: 232-239
171Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLCristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski: Approximability of Dense Instances of NEAREST CODEWORD Problem. SWAT 2002: 298-307
170Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Yakov Nekrich: Approximating Huffman Codes in Parallel Electronic Colloquium on Computational Complexity (ECCC)(018): (2002)
169Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani: Polynomial Time Approximation Schemes for Metric Min-Sum Clustering Electronic Colloquium on Computational Complexity (ECCC)(025): (2002)
168Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Yakov Nekrich: Parallel Construction of Minimum Redundancy Length-Limited Codes Electronic Colloquium on Computational Complexity (ECCC)(029): (2002)
167Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon: A Polynomial Time Approximation Scheme for Metric MIN-BISECTION Electronic Colloquium on Computational Complexity (ECCC)(041): (2002)
166Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski: A Polynomial Time Approximation Scheme for Subdense MAX-CUT Electronic Colloquium on Computational Complexity (ECCC)(044): (2002)
165Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: On Approximability of Minimum Bisection Problem Electronic Colloquium on Computational Complexity (ECCC)(046): (2002)
164Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski: 9/8-Approximation Algorithm for Random MAX-3SAT Electronic Colloquium on Computational Complexity (ECCC)(070): (2002)
163Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRusins Freivalds, Marek Karpinski, Carl H. Smith, Rolf Wiehagen: Learning by the Process of Elimination. Inf. Comput. 176(1): 37-50 (2002)
162Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLSusanne Albers, Marek Karpinski: Randomized splay trees: Theoretical and experimental results. Inf. Process. Lett. 81(4): 213-221 (2002)
161Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLUriel Feige, Marek Karpinski, Michael Langberg: Improved approximation of Max-Cut on graphs of bounded degree. J. Algorithms 43(2): 201-219 (2002)
160Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter: On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. J. Comput. Syst. Sci. 65(2): 332-350 (2002)
2001
159Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Approximating Bounded Degree Instances of NP-Hard Problems. FCT 2001: 24-34
158Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLFarid M. Ablayev, Aida Gainutdinova, Marek Karpinski: On Computational Power of Quantum Branching Programs. FCT 2001: 59-70
157Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLLars Engebretsen, Marek Karpinski: Approximation Hardness of TSP with Bounded Metrics. ICALP 2001: 201-212
156Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLKlaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel: Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. STACS 2001: 365-375
155Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems. Algorithmica 30(3): 386-397 (2001)
154Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: Improved Approximations for General Minimum Cost Scheduling Electronic Colloquium on Computational Complexity (ECCC)(097): (2001)
153Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLNoga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski: Random Sampling and Approximation of MAX-CSP Problems Electronic Colloquium on Computational Complexity (ECCC)(100): (2001)
152Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: Approximating Minimum Unsatisfiability of Linear Equations Electronic Colloquium on Computational Complexity (ECCC) 8(25): (2001)
151Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION Electronic Colloquium on Computational Complexity (ECCC) 8(26): (2001)
150Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLCristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski: Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction Electronic Colloquium on Computational Complexity (ECCC) 8(34): (2001)
149Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Approximating Bounded Degree Instances of NP-Hard Problems Electronic Colloquium on Computational Complexity (ECCC) 8(42): (2001)
148Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Sridhar Hannenhalli, Marek Karpinski: 1.375-Approximation Algorithm for Sorting by Reversals Electronic Colloquium on Computational Complexity (ECCC) 8(47): (2001)
147Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: Efficient Amplifiers and Bounded Degree Optimization Electronic Colloquium on Computational Complexity (ECCC) 8(53): (2001)
146Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLUriel Feige, Marek Karpinski, Michael Langberg: A note on approximating Max-Bisection on regular graphs. Inf. Process. Lett. 79(4): 181-188 (2001)
145Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLFarid M. Ablayev, Marek Karpinski, Rustam Mubarakzjanov: On BPP versus NPcoNP for ordered read-once branching programs. Theor. Comput. Sci. 264(1): 127-137 (2001)
2000
144Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Moses Charikar, Marek Karpinski: On-Line Load Balancing for Related Machines Electronic Colloquium on Computational Complexity (ECCC) 7(1): (2000)
143Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLUriel Feige, Marek Karpinski, Michael Langberg: Improved Approximation of MAX-CUT on Graphs of Bounded Degree Electronic Colloquium on Computational Complexity (ECCC) 7(21): (2000)
142Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLUriel Feige, Marek Karpinski, Michael Langberg: A Note on Approximating MAX-BISECTION on Regular Graphs Electronic Colloquium on Computational Complexity (ECCC) 7(43): (2000)
141Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Miroslaw Kowaluk, Andrzej Lingas: Approximation Algorithms for MAX-BISECTION on Low Degree Reg ular Graphs and Planar Graphs Electronic Colloquium on Computational Complexity (ECCC) 7(51): (2000)
140Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLKlaus Jansen, Marek Karpinski, Andrzej Lingas: A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs Electronic Colloquium on Computational Complexity (ECCC) 7(64): (2000)
139Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLLars Engebretsen, Marek Karpinski: Approximation Hardness of TSP with Bounded Metrics Electronic Colloquium on Computational Complexity (ECCC) 7(89): (2000)
138Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLCristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski: Approximability of Dense Instances of NEAREST CODEWORD Problem Electronic Colloquium on Computational Complexity (ECCC) 7(91): (2000)
137Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Moses Charikar, Marek Karpinski: On-Line Load Balancing for Related Machines. J. Algorithms 35(1): 108-121 (2000)
136Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski: Polynomial time approximation of dense weighted instances of MAX-CUT. Random Struct. Algorithms 16(4): 314-332 (2000)
135Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Alfred J. van der Poorten, Igor Shparlinski: Zero testing of p-adic and modular polynomials. Theor. Comput. Sci. 233(1-2): 309-317 (2000)
1999
134Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Igor Shparlinski: On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials. AAECC 1999: 492-497
133Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Randomized Complexity of Linear Arrangements and Polyhedra. FCT 1999: 1-12
132Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: On Some Tighter Inapproximability Results (Extended Abstract). ICALP 1999: 200-209
131Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAndris Ambainis, Richard F. Bonner, Rusins Freivalds, Marats Golovkins, Marek Karpinski: Quantum Finite Multitape Automata. SOFSEM 1999: 340-348
130Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLSergei Evdokimov, Marek Karpinski, Ilia N. Ponomarenko: Compact cellular algebras and permutation groups. Discrete Mathematics 197-198: 247-267 (1999)
129Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Randomized Complexity of Linear Arrangements and Polyhedra Electronic Colloquium on Computational Complexity (ECCC) 6(20): (1999)
128Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Igor Shparlinski: On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials Electronic Colloquium on Computational Complexity (ECCC) 6(27): (1999)
127Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Rustam Mubarakzjanov: A Note on Las Vegas OBDDs Electronic Colloquium on Computational Complexity (ECCC) 6(9): (1999)
126Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski: On the Approximation Hardness of Dense TSP and Other Path Problems. Inf. Process. Lett. 70(2): 53-55 (1999)
125Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLSanjeev Arora, David R. Karger, Marek Karpinski: Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems. J. Comput. Syst. Sci. 58(1): 193-210 (1999)
1998
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)
122Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLElias Dahlhaus, Marek Karpinski: Matching and Multidimensional Matching in Chordal and Strongly Chordal Graphs. Discrete Applied Mathematics 84(1-3): 79-91 (1998)
121Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLFarid M. Ablayev, Marek Karpinski: A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs Electronic Colloquium on Computational Complexity (ECCC) 5(11): (1998)
120Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLGunter Blache, Marek Karpinski, Juergen Wirtgen: On Approximation Intractability of the Bandwidth Problem Electronic Colloquium on Computational Complexity (ECCC) 5(14): (1998)
119Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski: On Approximation Hardness of Dense TSP and other Path Problems Electronic Colloquium on Computational Complexity (ECCC) 5(24): (1998)
118Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: On Some Tighter Inapproximability Results Electronic Colloquium on Computational Complexity (ECCC) 5(29): (1998)
117Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: On the Computational Power of Randomized Branching Programs Electronic Colloquium on Computational Complexity (ECCC) 5(38): (1998)
116Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLFarid M. Ablayev, Marek Karpinski: On the Power of Randomized Ordered Branching Programs Electronic Colloquium on Computational Complexity (ECCC) 5(4): (1998)
115Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLWenceslas Fernandez de la Vega, Marek Karpinski: Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT Electronic Colloquium on Computational Complexity (ECCC) 5(64): (1998)
114Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski: On Some Tighter Inapproximability Results, Further Improvements Electronic Colloquium on Computational Complexity (ECCC) 5(65): (1998)
113no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Wojciech Rytter: On a Sublinear Time Parallel Construction of Optimal Binary Search Trees. Parallel Processing Letters 8(3): 387-397 (1998)
112Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMikael Goldmann, Marek Karpinski: Simulating Threshold Circuits by Majority Circuits. SIAM J. Comput. 27(1): 230-246 (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)
110Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Wojciech Rytter: Alphabet-Independent Optimal Parallel Search for Three-Dimensional Patterns. Theor. Comput. Sci. 205(1-2): 243-260 (1998)
1997
109Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAndris Ambainis, Kalvis Apsitis, Cristian Calude, Rusins Freivalds, Marek Karpinski, Tomas Larfeldt, Iveta Sala, Juris Smotrovs: Effects of Kolmogorov Complexity Present in Inductive Inference as Well. ALT 1997: 244-259
108Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Marek Karpinski, Lawrence L. Larmore, Wojciech Plandowski, Wojciech Rytter: On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. CPM 1997: 40-51
107no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAlexander L. Chistov, Gábor Ivanyos, Marek Karpinski: Polynomial Time Algorithms for Modules over Finite Dimensional Algebras. ISSAC 1997: 68-74
106Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Polynominal Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems. RANDOM 1997: 1-14
105Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAndris Ambainis, Rusins Freivalds, Marek Karpinski: Weak and Strong Recognition by 2-way Randomized Automata. RANDOM 1997: 175-185
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
103Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Angus Macintyre: Approximating the Volume of General Pfaffian Bodies. Structures in Logic and Computer Science 1997: 162-173
102Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Moses Charikar, Marek Karpinski: On-line Load Balancing for Related Machines. WADS 1997: 116-125
101Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJoachim von zur Gathen, Marek Karpinski, Igor Shparlinski: Counting Curves and Their Projections. Computational Complexity 6(1): 64-99 (1997)
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)
97Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Juergen Wirtgen, Alexander Zelikovsky: An Approximation Algorithm for the Bandwidth Problem on Dense Graphs Electronic Colloquium on Computational Complexity (ECCC) 4(17): (1997)
96Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems Electronic Colloquium on Computational Complexity (ECCC) 4(24): (1997)
95Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Alexander Zelikovsky: Approximating Dense Cases of Covering Problems Electronic Colloquium on Computational Complexity (ECCC) 4(4): (1997)
94Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Juergen Wirtgen: On Approximation Hardness of the Bandwidth Problem Electronic Colloquium on Computational Complexity (ECCC) 4(41): (1997)
93Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Alexander Zelikovsky: New Approximation Algorithms for the Steiner Tree Problems. J. Comb. Optim. 1(1): 47-65 (1997)
92Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Angus Macintyre: Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks. J. Comput. Syst. Sci. 54(1): 169-176 (1997)
91no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Wojciech Rytter, Ayumi Shinohara: An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions. Nord. J. Comput. 4(2): 172-186 (1997)
90Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Lawrence L. Larmore, Wojciech Rytter: Correctness of Constructing Optimal Alphabetic Trees Revisited. Theor. Comput. Sci. 180(1-2): 309-324 (1997)
1996
89Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLLeszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter: Randomized Efficient Algorithms for Compressed Strings: The Finger-Print Approach (Extended Abstract). CPM 1996: 39-49
88Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLFarid M. Ablayev, Marek Karpinski: On the Power of Randomized Branching Programs. ICALP 1996: 348-356
87Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Lawrence L. Larmore, Wojciech Rytter: Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees. SODA 1996: 36-41
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
85Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLLeszek Gasieniec, Marek Karpinski, Wojciech Plandowski, Wojciech Rytter: Efficient Algorithms for Lempel-Zip Encoding (Extended Abstract). SWAT 1996: 392-403
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)
82Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Rutger Verbeek: On Randomized versus Deterministic Computation. Theor. Comput. Sci. 154(1): 23-39 (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)
80Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Igor Shparlinski: On Some Approximation Problems Concerning Sparse Polynomials over Finite Fields. Theor. Comput. Sci. 157(2): 259-266 (1996)
1995
79Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Wojciech Rytter, Ayumi Shinohara: Pattern-Matching for Strings with Short Descriptions. CPM 1995: 205-214
78Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Angus Macintyre: Bounding VC-dimension of neural networks: Progress and prospects. EuroCOLT 1995: 337-341
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
76Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRusins Freivalds, Marek Karpinski: Lower Time Bounds for Randomized Computation. ICALP 1995: 183-195
75Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Angus Macintyre: Polynomial bounds for VC dimension of sigmoidal neural networks. STOC 1995: 200-208
74Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLSanjeev Arora, David R. Karger, Marek Karpinski: Polynomial time approximation schemes for dense instances of NP-hard problems. STOC 1995: 284-293
73Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLFelipe Cucker, Marek Karpinski, Pascal Koiran, Thomas Lickteig, Kai Werther: On real Turing machines that toss coins. STOC 1995: 335-342
72Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Rutger Verbeek: On Randomized Versus Deterministic Computation Electronic Colloquium on Computational Complexity (ECCC) 2(21): (1995)
71Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Wojciech Rytter, Ayumi Shinohara: Pattern-Matching for Strings with Short Descriptions Electronic Colloquium on Computational Complexity (ECCC) 2(22): (1995)
70Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Alexander Zelikovsky: 1.757 and 1.267 - Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems Electronic Colloquium on Computational Complexity (ECCC) 2(3): (1995)
69Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Alexander Zelikovsky: New Approximation Algorithms for the Steiner Tree Problems Electronic Colloquium on Computational Complexity (ECCC) 2(30): (1995)
68Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLFarid M. Ablayev, Marek Karpinski: On the Power of Randomized Branching Programs Electronic Colloquium on Computational Complexity (ECCC) 2(54): (1995)
67Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Angus Macintyre: VC Dimension of Sigmoidal and General Pfaffian Networks Electronic Colloquium on Computational Complexity (ECCC) 2(55): (1995)
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)
64Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLHans Kleine Büning, Marek Karpinski, Andreas Flögel: Resolution for Quantified Boolean Formulas Inf. Comput. 117(1): 12-18 (1995)
1994
63Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRusins Freivalds, Dace Gobleja, Marek Karpinski, Carl H. Smith: Co-learnability and FIN-identifiability of Enumerable Classes of Total Recursive Functions. AII/ALT 1994: 100-105
62Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRusins Freivalds, Marek Karpinski, Carl H. Smith: Co-Learning of Total Recursive Functions. COLT 1994: 190-197
61Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Wojciech Rytter: An Alphabet-Independent Optimal Parallel Search for Three Dimensional Pattern. CPM 1994: 125-135
60Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPiotr Berman, Ulrich Fößmeier, Marek Karpinski, Michael Kaufmann, Alexander Zelikovsky: Approaching the 5/4-Approximation for Rectilinear Steiner Trees. ESA 1994: 60-71
59Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRusins Freivalds, Marek Karpinski: Lower Space Bounds for Randomized Computation. ICALP 1994: 580-592
58Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Wojciech Rytter: On a Sublinear Time Parallel Construction of Optimal Binary Search Trees. MFCS 1994: 453-461
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
56Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLNader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein, Marek Karpinski: An Algorithm to Learn Read-Once Threshold Formulas, and Transformations Between Learning Models. Computational Complexity 4: 37-61 (1994)
55Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Angus Macintyre: Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks Electronic Colloquium on Computational Complexity (ECCC) 1(24): (1994)
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)
53Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLElias Dahlhaus, Marek Karpinski: An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph. Theor. Comput. Sci. 134(2): 493-528 (1994)
1993
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
51Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Rutger Verbeek: On Randomized Versus Deterministic Computation. ICALP 1993: 227-240
50Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMikael Goldmann, Marek Karpinski: Simulating threshold circuits by majority circuits. STOC 1993: 551-560
49Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLJoachim von zur Gathen, Marek Karpinski, Igor Shparlinski: Counting curves and their projections. STOC 1993: 805-812
48Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLDana Angluin, Lisa Hellerstein, Marek Karpinski: Learning Read-Once Formulas with Queries. J. ACM 40(1): 185-210 (1993)
47Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Michael Luby: Approximating the Number of Zeroes of a GF[2] Polynomial. J. Algorithms 14(2): 280-287 (1993)
46Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLElias Dahlhaus, Péter Hajnal, Marek Karpinski: On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs. J. Algorithms 15(3): 367-384 (1993)
45Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPeter Bürgisser, Marek Karpinski, Thomas Lickteig: On Randomized Semi-algebraic Test Complexity. J. Complexity 9(2): 231-251 (1993)
44Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Thorsten Werther: VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions. SIAM J. Comput. 22(6): 1276-1285 (1993)
1992
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
42Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLElias Dahlhaus, Marek Karpinski, Pierre Kelsen: An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3. Inf. Process. Lett. 42(6): 309-313 (1992)
41Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLElias Dahlhaus, Marek Karpinski: Perfect Matching for Regular Graphs is AC°-Hard for the General Matching Problem. J. Comput. Syst. Sci. 44(1): 94-102 (1992)
1991
40Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Approximation Algorithms for Counting Problems in Finite Fields. FCT 1991: 45-46
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
37Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Michael Luby: Approximating the Number of Zeroes of a GF[2] Polynomial. SODA 1991: 300-303
36Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLPeter Bürgisser, Marek Karpinski, Thomas Lickteig: Some Computational Problems in Linear Algebra as Hard as Matrix Multiplication. Computational Complexity 1: 131-155 (1991)
35Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMichael Clausen, Andreas W. M. Dress, Johannes Grabmeier, Marek Karpinski: On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials Over Finite Fields. Theor. Comput. Sci. 84(2): 151-164 (1991)
1990
34Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAndreas Flögel, Marek Karpinski, Hans Kleine Büning: Subclasses of Quantified Boolean Formulas. CSL 1990: 145-155
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
32Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Friedhelm Meyer auf der Heide: On the Complexity of Genuinely Polynomial Computation. MFCS 1990: 362-368
31Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLElias Dahlhaus, Marek Karpinski, Mark B. Novick: Fast Parallel Algorithms for the Clique Separator Decomposition. SODA 1990: 244-251
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)
1989
29Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLLisa Hellerstein, Marek Karpinski: Learning Read-Once Formulas Using Membership Queries. COLT 1989: 146-161
28Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLElias Dahlhaus, Marek Karpinski: An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract) FOCS 1989: 454-459
27Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLAndrzej Lingas, Marek Karpinski: Subtree Isomorphism is NC Reducible to Bipartite Perfect Matching. Inf. Process. Lett. 30(1): 27-32 (1989)
1988
26Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Boolean Complexity of Algebraic Interpolation Problems. CSL 1988: 138-147
25Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLElias Dahlhaus, Péter Hajnal, Marek Karpinski: Optimal Parallel Algorithm for the Hamiltonian Cycle Problem on Dense Graphs FOCS 1988: 186-193
24no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Zbigniew W. Ras: Learning Machine for Probabilistically Describable Concepts. ISMIS 1988: 353-362
23Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLElias Dahlhaus, Marek Karpinski: A Fast Parallel Algorithm for Computing all Maximal Cliques in a Graph and the Related Problems (Extended Abstract). SWAT 1988: 139-144
22Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLElias Dahlhaus, Marek Karpinski: Parallel Construction of Perfect Matchings and Hamiltonian Cycles on Dense Graphs. Theor. Comput. Sci. 61: 121-136 (1988)
1987
21Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Hans Kleine Büning, Peter H. Schmitt: On the Computational Complexity of Quantified Horn Clauses. CSL 1987: 129-137
20Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Rutger Verbeek: Randomness, Provability, and the Seperation of Monte Carlo Time and Space. Computation Theory and Logic 1987: 189-207
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
18Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Rutger Verbeek: On the Monte Carlo Space Constructible Functions and Seperation Results for Probabilistic Complexity Classes Inf. Comput. 75(2): 178-189 (1987)
1986
17Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Rutger Verbeek: On the Power of Two-Way Random Generators and the Impossibility of Deterministic Poly-Space Simulation Information and Control 71(1/2): 131-142 (1986)
1985
16Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Jan van Leeuwen: Preface Information and Control 64(1-3): 1 (1985)
15Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski, Rutger Verbeek: There Is No Polynomial Deterministic Space Simulation of Probabilistic Space with a Two-Way Random-Tape Generator Information and Control 67(1-3): 158-162 (1985)
1983
14no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Fundamentals of Computation Theory, Proceedings of the 1983 International FCT-Conference, Borgholm, Sweden, August 21-27, 1983 Springer 1983
1982
13Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Decidability of "Skolem Matrix Emptiness Problem" Entails Constructability of Exact Regular Expression. Theor. Comput. Sci. 17: 99-102 (1982)
1980
12no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: On global word definability and constructively definable sets in Nn. CLAAP 1980: 225-227
1979
11no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLRyszard Danecki, Marek Karpinski: Decidability Results on Plane Automata Searching Mazes. FCT 1979: 84-91
1977
10no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Fundamentals of Computation Theory, Proceedings of the 1977 International FCT-Conference, Poznan-Kórnik, Poland, September 19-23, 1977 Springer 1977
9Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: The Equivalences Problems for Binary EOL-Systems are Decidable. FCT 1977: 423-434
1976
8Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Multiplicity Functions on Omega-Automata. MFCS 1976: 596-601
7no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Valued Probabilistic Tree Functions. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 24: 927-930 (1976)
1975
6Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Decision Algorithms for Havel's Branching Automata. MFCS 1975: 273-279
1974
5Electronic Edition pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Stretching by Probabilistic Tree Automata and Santos Grammars. MFCS 1974: 249-255
4no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Probablistic Climbing and Sinking Languages. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 22: 1057-1062 (1974)
3no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Free Structure Tree Automata IV. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 22: 87-91 (1974)
1973
2no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Free Structure Tree Automata, II: Nondeterminstic and Deterministic Regularity. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 21(5): 447-450 (1973)
1no EE pubzone.org CiteSeerX Google scholar BibTeX bibliographical record in XMLMarek Karpinski: Free Structure Tree Automata, III: Normalized Climbing Automata. Bull. Acad. Polon. Sci., Sér. Sci. Math. Astronom. Phys. 21(6): 567-572 (1973)

Coauthor Index

1Farid M. Ablayev [68] [88] [116] [121] [145] [158] [181] [195]
2A. Abouelaoualim [251]
3Susanne Albers [162]
4Noga Alon [153] [172] [180]
5Andris Ambainis [105] [109] [131]
6Dana Angluin [48]
7Kalvis Apsitis [109]
8Manuel Arora [274]
9Sanjeev Arora [74] [125]
10Cristina Bazgan [138] [150] [171] [179] [201]
11Piotr Berman [60] [102] [108] [114] [118] [132] [137] [144] [147] [148] [151] [152] [154] [160] [170] [174] [176] [177] [178] [182] [183] [184] [185] [191] [192] [197] [213] [215] [217] [219] [220] [224] [226] [230] [231] [240] [242] [243] [260] [261] [267] [278]
12Gunter Blache [120]
13Richard F. Bonner [131]
14Magnus Bordewich [196] [198] [204] [214] [221]
15Nader H. Bshouty [56]
16Hans Kleine Büning [21] [34] [64]
17Peter Bürgisser (Peter Buergisser) [36] [45]
18Cristian S. Calude (Cristian Calude) [109]
19Jean Cardinal [253] [254] [262] [272]
20Moses Charikar [102] [137] [144]
21Alexander L. Chistov [107]
22Michael Clausen [35]
23Béla Csaba [173]
24Felipe Cucker [73]
25Elias Dahlhaus [22] [23] [25] [28] [31] [41] [42] [46] [53] [122]
26Ryszard Danecki [11]
27Kinkar Chandra Das [251]
28Bhaskar DasGupta [219] [231] [243] [267]
29Andreas W. M. Dress [35]
30Martin E. Dyer [196] [198] [204] [214] [221] [265]
31Annette Ebbers-Baumann [202] [218]
32Lars Engebretsen [139] [157] [208]
33Sergei Evdokimov [130]
34Uriel Feige [142] [143] [146] [161] [265]
35Andreas Flögel [34] [64]
36Ulrich Fößmeier [60]
37Rusins Freivalds [59] [62] [63] [76] [105] [109] [131] [163]
38Alan M. Frieze [265]
39Travis Gagie [227] [247]
40Aida Gainutdinova [158] [195]
41Leszek Gasieniec [85] [89]
42Joachim von zur Gathen [49] [101]
43Dace Gobleja [63]
44Leslie Ann Goldberg (Leslie A. Henderson) [233] [250]
45Mikael Goldmann [50] [112]
46Marats Golovkins [131]
47Johannes Grabmeier [35]
48Dima Grigoriev [19] [30] [33] [38] [39] [43] [52] [54] [57] [65] [66] [77] [81] [83] [84] [86] [98] [99] [100] [104] [111] [123] [124]
49Ansgar Grüne [202] [218]
50Péter Hajnal [25] [46]
51Thomas R. Hancock [56]
52Sridhar Hannenhalli [148] [178]
53Friedhelm Meyer auf der Heide [32] [65] [86] [100]
54Lisa Hellerstein [29] [48] [56]
55Gábor Ivanyos [107] [223] [225] [229] [235] [237] [239] [245] [249] [271] [274]
56Klaus Jansen [140] [156] [194]
57Mark Jerrum [233] [250]
58Lakshmi Kaligounder [267]
59Ravi Kannan (Ravindran Kannan) [153] [172] [180] [200] [210]
60David R. Karger [74] [125]
61Michael Kaufmann [60]
62Pierre Kelsen [42]
63Rolf Klein [202] [218]
64Christian Knauer [202] [218]
65Pascal Koiran [73]
66Miroslaw Kowaluk [141] [189]
67Piotr Krysta [173]
68Michael Langberg [142] [143] [146] [161]
69Tomas Larfeldt [109]
70Lawrence L. Larmore [87] [90] [108] [160] [188]
71Jan van Leeuwen [16]
72Thomas Lickteig [36] [45] [73]
73Andrzej Lingas [27] [140] [141] [156] [189] [194] [202] [218] [240] [261] [278]
74Michael Luby [37] [47]
75Angus Macintyre [55] [67] [75] [78] [92] [103]
76Ion I. Mandoiu [186] [199]
77Yannis Manoussakis [251]
78Carlos A. J. Martinhon [251]
79Claire Mathieu (Claire Kenyon, Claire Kenyon-Mathieu) [167] [169] [187] [193]
80Cristopher Moore [195]
81Rustam Mubarakzjanov [127] [145]
82J. Ian Munro [257]
83Yakov Nekrich [168] [170] [176] [188] [190] [192] [203] [205] [206] [207] [215] [217] [227] [232] [234] [236] [241] [247] [248] [255] [257] [269]
84Mark B. Novick [31]
85Andrew M. Odlyzko [43] [83]
86Alexander Olshevsky [186] [199]
87Wojciech Plandowski [85] [89] [108] [160]
88Chris Pollett (Christopher Pollett) [195]
89Ilia N. Ponomarenko [130]
90Alfred J. van der Poorten [135]
91Yuval Rabani [169] [187]
92Zbigniew W. Ras [24]
93Lajos Rónyai [223] [229] [271]
94Andrzej Rucinski [246] [252] [258] [275] [276]
95Wojciech Rytter [58] [61] [71] [79] [85] [87] [89] [90] [91] [108] [110] [113] [160]
96Rachid Saad [251]
97Iveta Sala [109]
98Nitin Saxena [223] [225] [229] [235] [237] [239] [245] [249] [271] [274]
99Richard Schmied [253] [254] [262] [263] [264] [266] [268] [272] [273] [277]
100Peter H. Schmitt [21]
101Warren Schudy [222] [228] [238] [244] [256] [259] [270]
102Alex D. Scott (Alexander D. Scott) [183] [184] [191] [220]
103Eike Seidel [156] [194]
104Ayumi Shinohara [71] [79] [91]
105Igor Shparlinski [49] [80] [101] [128] [134] [135]
106Michael F. Singer [30] [33] [54]
107Carl H. Smith [62] [63] [163]
108Roman Smolensky [65] [86] [99] [100]
109Juris Smotrovs [109]
110Edyta Szymanska [246] [252] [258] [275] [276]
111Wenceslas Fernandez de la Vega [115] [119] [126] [136] [138] [150] [153] [164] [166] [167] [169] [171] [172] [179] [180] [187] [193] [200] [209] [210] [211] [212] [216] [251]
112Santosh Vempala [200]
113Rutger Verbeek [15] [17] [18] [20] [51] [72] [82]
114Claus Viehmann [253] [254] [262] [263] [268] [272]
115Nicolai Vorobjov [57] [77] [98]
116Kai Werther [73]
117Thorsten Werther [44]
118Rolf Wiehagen [163]
119Juergen Wirtgen [94] [97] [120]
120Andrew Chi-Chih Yao (Andrew C. Yao) [66] [123]
121Alexander Zelikovsky [60] [69] [70] [93] [95] [97] [186] [199] [224] [226] [230] [242] [260]

Colors in the list of coauthors

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Free | Complete | Author
Last update Fri Jun 1 15:44:53 2012 CET by the DBLP Team — This material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page