Travelled to:2 × Canada
4 × USA
Collaborated with:L.Trevisan ∅ L.Gurvits S.Lovett R.Meshulam N.Linial A.Wigderson E.Fischer E.Lehman I.Newman S.Raskhodnikova R.Rubinfeld
Talks about:determinist (2) algorithm (2) polynomi (2) approxim (2) gower (2) test (2) mix (2) discrimin (1) conjectur (1) character (1)
Person: Alex Samorodnitsky
DBLP: Samorodnitsky:Alex
Contributed to:
200820072006200220001998Wrote 7 papers:
- STOC-2008-LovettMS
- Inverse conjecture for the gowers norm is false (SL, RM, AS), pp. 547–556.
- STOC-2007-Samorodnitsky #scalability #testing
- Low-degree tests at large distances (AS), pp. 506–515.
- STOC-2006-SamorodnitskyT
- Gowers uniformity, influence of variables, and PCPs (AS, LT), pp. 11–20.
- STOC-2002-FischerLNRRS #testing
- Monotonicity testing over general poset domains (EF, EL, IN, SR, RR, AS), pp. 474–483.
- STOC-2000-GurvitsS #algorithm #approximate #polynomial
- A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume (LG, AS), pp. 48–57.
- STOC-2000-SamorodnitskyT #complexity #query
- A PCP characterization of NP with optimal amortized query complexity (AS, LT), pp. 191–199.
- STOC-1998-LinialSW #algorithm #approximate #matrix #polynomial #scalability
- A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents (NL, AS, AW), pp. 644–652.