1997 |
18 | | Roman Smolensky:
Representations of Sets of Boolean Functions by Commutative Rings.
Computational Complexity 6(3): 199-208 (1997) |
17 | | Roman Smolensky:
Easy Lower Bound for a Strange Computational Model.
Computational Complexity 6(3): 213-216 (1997) |
16 | | Roman Smolensky:
Well-Known Bound for the VC-Dimension Made Easy.
Computational Complexity 6(4): 299-300 (1997) |
15 | | Victor Shoup,
Roman Smolensky:
Lower Bounds for Polynomial Evaluation and Interpolation Problems.
Computational Complexity 6(4): 301-311 (1997) |
14 | | Ashok K. Chandra,
Prabhakar Raghavan,
Walter L. Ruzzo,
Roman Smolensky,
Prasoon Tiwari:
The Electrical Resistance of a Graph Captures its Commute and Cover Times.
Computational Complexity 6(4): 312-340 (1997) |
13 | | Dima 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) |
12 | | Dima Grigoriev,
Marek Karpinski,
Roman Smolensky:
Randomization and the Computational Power of Analytic and Algebraic Decision Trees.
Computational Complexity 6(4): 376-388 (1997) |
1996 |
11 | EE | Dima Grigoriev,
Marek Karpinski,
Friedhelm Meyer auf der Heide,
Roman Smolensky:
A Lower Bound for Randomized Algebraic Decision Trees.
STOC 1996: 612-619 |
1995 |
10 | EE | Dima 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) |
1993 |
9 | | Roman Smolensky:
On Representations by Low-Degree Polynomials
FOCS 1993: 130-138 |
8 | | Allan Borodin,
Alexander A. Razborov,
Roman Smolensky:
On Lower Bounds for Read-K-Times Branching Programs.
Computational Complexity 3: 1-18 (1993) |
1992 |
7 | | Jehoshua Bruck,
Roman Smolensky:
Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms.
SIAM J. Comput. 21(1): 33-42 (1992) |
1991 |
6 | | Victor Shoup,
Roman Smolensky:
Lower Bounds for Polynomial Evaluation and Interpolation Problems
FOCS 1991: 378-383 |
1990 |
5 | | Roman Smolensky:
On Interpolation by Analytic Functions with Special Properties and Some Weak Lower Bounds on the Size of Circuits with Symmetric Gates
FOCS 1990: 628-631 |
4 | | Jehoshua Bruck,
Roman Smolensky:
Polynomial Threshold Functions, AC^0 Functions and Spectral Norms (Extended Abstract)
FOCS 1990: 632-641 |
1989 |
3 | | Ashok K. Chandra,
Prabhakar Raghavan,
Walter L. Ruzzo,
Roman Smolensky,
Prasoon Tiwari:
The Electrical Resistance of a Graph Captures its Commute and Cover Times (Detailed Abstract)
STOC 1989: 574-586 |
1987 |
2 | | Roman Smolensky:
Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity
STOC 1987: 77-82 |
1985 |
1 | | Benny Chor,
Oded Goldreich,
Johan Håstad,
Joel Friedman,
Steven Rudich,
Roman Smolensky:
The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)
FOCS 1985: 396-407 |