Travelled to:1 × Canada
1 × Spain
4 × USA
Collaborated with:M.Karpinski ∅ E.A.Hirsch D.V.Pasechnik N.Vorobjov S.R.Buss R.Impagliazzo T.Pitassi F.M.a.d.Heide R.Smolensky
Talks about:lower (6) bound (6) algebra (3) random (3) exponenti (2) decis (2) tree (2) polyhedron (1) membership (1) polynomi (1)
Person: Dima Grigoriev
DBLP: Grigoriev:Dima
Contributed to:
2002
19991998199719961994Wrote 7 papers:
- ICALP-2002-GrigorievHP #algebra #bound #exponential #proving
- Exponential Lower Bound for Static Semi-algebraic Proofs (DG, EAH, DVP), pp. 257–268.
- STOC-1999-BussGIP #calculus #linear #polynomial
- Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (SRB, DG, RI, TP), pp. 547–556.
- STOC-1998-Grigoriev #bound #complexity #random
- Randomized Complexity Lower Bounds (DG), pp. 219–223.
- 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.
- STOC-1996-GrigorievKHS #algebra #bound #random
- A Lower Bound for Randomized Algebraic Decision Trees (DG, MK, FMadH, RS), pp. 612–619.
- STOC-1994-GrigorievKV #algebra #bound #testing
- Lower bounds on testing membership to a polyhedron by algebraic decision trees (DG, MK, NV), pp. 635–644.