Travelled to:1 × Canada
1 × Finland
2 × USA
Collaborated with:∅ S.Arora I.Tourlakis E.A.Hirsch D.Itsykson J.Johannsen T.Pitassi A.Urquhart E.Ben-Sasson A.A.Razborov A.Wigderson
Talks about:exponenti (2) resolut (2) lower (2) bound (2) nonapproxim (1) schrijver (1) hierarchi (1) algorithm (1) proposit (1) calculus (1)
Person: Michael Alekhnovich
DBLP: Alekhnovich:Michael
Contributed to:
2005
200420022000Wrote 5 papers:
- STOC-2005-Alekhnovich #bound #random
- Lower bounds for k-DNF resolution on random 3-CNFs (MA), pp. 251–256.
- STOC-2005-AlekhnovichAT #towards
- Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy (MA, SA, IT), pp. 294–303.
- ICALP-2004-AlekhnovichHI #algorithm #bound #exponential #satisfiability
- Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas (MA, EAH, DI), pp. 84–96.
- STOC-2002-AlekhnovichJPU #exponential
- An exponential separation between regular and general resolution (MA, JJ, TP, AU), pp. 448–456.
- STOC-2000-AlekhnovichBRW #calculus #complexity
- Space complexity in propositional calculus (MA, EBS, AAR, AW), pp. 358–367.