The Bit Extraction Problem of t-Resilient Functions (Preliminary Version) - Benny Chor; Oded Goldreich 001; Johan Håstad; Joel Friedman; Steven Rudich; Roman Smolensky (FOCS, 1985)

Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity - Roman Smolensky (STOC, 1987)

The Electrical Resistance of a Graph Captures its Commute and Cover Times (Detailed Abstract) - Ashok K. Chandra; Prabhakar Raghavan; Walter L. Ruzzo; Roman Smolensky; Prasoon Tiwari (STOC, 1989)

Polynomial Threshold Functions, AC^0 Functions and Spectral Norms (Extended Abstract) - Jehoshua Bruck; Roman Smolensky (FOCS, 1990)

On Interpolation by Analytic Functions with Special Properties and Some Weak Lower Bounds on the Size of Circuits with Symmetric Gates - Roman Smolensky (FOCS, 1990)

Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms. - Jehoshua Bruck; Roman Smolensky (SIAM J. Comput., 1992)

On Representations by Low-Degree Polynomials - Roman Smolensky (FOCS, 1993)

On Lower Bounds for Read-K-Times Branching Programs. - Allan Borodin; Alexander A. Razborov; Roman Smolensky (Comput. Complex., 1993)

The Electrical Resistance of a Graph Captures its Commute and Cover Times. - Ashok K. Chandra; Prabhakar Raghavan; Walter L. Ruzzo; Roman Smolensky; Prasoon Tiwari (Comput. Complex., 1997)

A Lower Bound for Randomized Algebraic Decision Trees. - Dima Grigoriev; Marek Karpinski; Friedhelm Meyer auf der Heide; Roman Smolensky (Comput. Complex., 1997)

Randomization and the Computational Power of Analytic and Algebraic Decision Trees. - Dima Grigoriev; Marek Karpinski; Roman Smolensky (Comput. Complex., 1997)

Lower Bounds for Polynomial Evaluation and Interpolation Problems. - Victor Shoup; Roman Smolensky (Comput. Complex., 1997)

Representations of Sets of Boolean Functions by Commutative Rings. - Roman Smolensky (Comput. Complex., 1997)

Easy Lower Bound for a Strange Computational Model. - Roman Smolensky (Comput. Complex., 1997)

Well-Known Bound for the VC-Dimension Made Easy. - Roman Smolensky (Comput. Complex., 1997)