Roman Smolensky

According to our database, Roman Smolensky authored at least 15 papers between 1985 and 1997.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

1997

Well-Known Bound for the VC-Dimension Made Easy.

Roman Smolensky

Comput. Complex., 1997

Easy Lower Bound for a Strange Computational Model.

Roman Smolensky

Comput. Complex., 1997

Representations of Sets of Boolean Functions by Commutative Rings.

Roman Smolensky

Comput. Complex., 1997

Lower Bounds for Polynomial Evaluation and Interpolation Problems.

Victor Shoup, 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

A Lower Bound for Randomized Algebraic Decision Trees.

Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

Comput. Complex., 1997

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

1993

On Lower Bounds for Read-K-Times Branching Programs.

Allan Borodin, Alexander A. Razborov, Roman Smolensky

Comput. Complex., 1993

On Representations by Low-Degree Polynomials

Roman Smolensky

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1992

Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms.

Jehoshua Bruck, Roman Smolensky

SIAM J. Comput., 1992

1990

On Interpolation by Analytic Functions with Special Properties and Some Weak Lower Bounds on the Size of Circuits with Symmetric Gates

Roman Smolensky

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Polynomial Threshold Functions, AC^0 Functions and Spectral Norms (Extended Abstract)

Jehoshua Bruck, Roman Smolensky

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

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

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1987

Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity

Roman Smolensky

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1985

The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)

Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, Roman Smolensky

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985