BibSLEIGH — Marek

Travelled to:

1 × Czech Republic
1 × Greece
1 × Hungary
1 × Israel
1 × Italy
1 × Japan
1 × Spain
1 × Sweden
2 × Canada
4 × Germany
8 × USA

Collaborated with:

D.Grigoriev P.Berman R.Freivalds W.F.d.l.Vega H.K.Büning W.Schudy R.Kannan L.Engebretsen F.M.Ablayev A.Macintyre R.Verbeek M.Goldmann ∅ A.Lingas D.Sledneu M.Bordewich M.E.Dyer Y.Nekrich S.Arora D.R.Karger N.Vorobjov J.v.z.Gathen I.Shparlinski A.Flögel P.H.Schmitt S.Vempala C.Kenyon Y.Rabani N.Alon F.M.a.d.Heide R.Smolensky F.Cucker P.Koiran T.Lickteig K.Werther

Talks about:

approxim (9) bound (9) random (7) problem (6) lower (6) scheme (4) comput (4) time (4) circuit (3) algebra (3)

Person: Marek Karpinski

DBLP: Karpinski:Marek

Contributed to:

2015

2009

2006

2005

2003

2002

2001

1999

1998

1997

1996

1995

1994

1993

1990

1988

1987

Wrote 26 papers:

ICALP-v1-2015-KarpinskiLS #set: A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set (MK, AL, DS), pp. 785–796.
STOC-2009-KarpinskiS #approximate #game studies #linear #problem: Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems (MK, WS), pp. 313–322.
ICALP-v1-2006-BordewichDK #approximate #metric: Stopping Times, Metrics and Approximate Counting (MB, MED, MK), pp. 108–119.
STOC-2005-VegaKKV #approximate #composition #constraints #problem: Tensor decomposition and approximation schemes for constraint satisfaction problems (WFdlV, MK, RK, SV), pp. 747–754.
STOC-2003-VegaKKR #approximate #clustering #problem: Approximation schemes for clustering problems (WFdlV, MK, CK, YR), pp. 50–58.
ICALP-2002-BermanK #approximate #bound: Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION (PB, MK), pp. 623–632.
ICALP-2002-BermanKN #approximate #parallel: Approximating Huffman Codes in Parallel (PB, MK, YN), pp. 845–855.
STOC-2002-AlonVKK #approximate #problem #random: Random sampling and approximation of MAX-CSP problems (NA, WFdlV, RK, MK), pp. 232–239.
ICALP-2001-EngebretsenK #approximate #bound #metric: Approximation Hardness of TSP with Bounded Metrics (LE, MK), pp. 201–212.
ICALP-1999-BermanK #on the: On Some Tighter Inapproximability Results (PB, MK), pp. 200–209.
STOC-1998-GrigorievK #bound #exponential: An Exponential Lower Bound for Depth 3 Arithmetic Circuits (DG, MK), pp. 577–582.
STOC-1997-GrigorievK #bound #random: Randomized Ω(n²) Lower Bound for Knapsack (DG, MK), pp. 76–85.
ICALP-1996-AblayevK #branch #on the #power of #random #source code: On the Power of Randomized Branching Programs (FMA, MK), pp. 348–356.
STOC-1996-GrigorievKHS #algebra #bound #random: A Lower Bound for Randomized Algebraic Decision Trees (DG, MK, FMadH, RS), pp. 612–619.
ICALP-1995-FreivaldsK #bound #random: Lower Time Bounds for Randomized Computation (RF, MK), pp. 183–195.
STOC-1995-AroraKK #approximate #np-hard #polynomial #problem: Polynomial time approximation schemes for dense instances of NP-hard problems (SA, DRK, MK), pp. 284–293.
STOC-1995-CuckerKKLW #on the #turing machine: On real Turing machines that toss coins (FC, MK, PK, TL, KW), pp. 335–342.
STOC-1995-KarpinskiM #bound #network #polynomial: Polynomial bounds for VC dimension of sigmoidal neural networks (MK, AM), pp. 200–208.
ICALP-1994-FreivaldsK #bound #random: Lower Space Bounds for Randomized Computation (RF, MK), pp. 580–592.
STOC-1994-GrigorievKV #algebra #bound #testing: Lower bounds on testing membership to a polyhedron by algebraic decision trees (DG, MK, NV), pp. 635–644.
ICALP-1993-KarpinskiV #on the #random: On Randomized Versus Deterministic Computation (MK, RV), pp. 227–240.
STOC-1993-GathenKS: Counting curves and their projections (JvzG, MK, IS), pp. 805–812.
STOC-1993-GoldmannK #simulation: Simulating threshold circuits by majority circuits (MG, MK), pp. 551–560.
CSL-1990-FlogelKB #quantifier #subclass: Subclasses of Quantified Boolean Formulas (AF, MK, HKB), pp. 145–155.
CSL-1988-Karpinski #algebra #complexity #problem: Boolean Complexity of Algebraic Interpolation Problems (MK), pp. 138–147.
CSL-1987-KarpinskiBS #complexity #horn clause #on the #quantifier: On the Computational Complexity of Quantified Horn Clauses (MK, HKB, PHS), pp. 129–137.