Roman Smolensky

Publication Activity (10 Years)

Years Active: 1985-1997
Publications (10 Years): 0

Publications

Roman Smolensky
Well-Known Bound for the VC-Dimension Made Easy. Comput. Complex. 6 (4) (1997)
Victor Shoup, Roman Smolensky
Lower Bounds for Polynomial Evaluation and Interpolation Problems. Comput. Complex. 6 (4) (1997)
Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, Prasoon Tiwari
The Electrical Resistance of a Graph Captures its Commute and Cover Times. Comput. Complex. 6 (4) (1997)
Roman Smolensky
Representations of Sets of Boolean Functions by Commutative Rings. Comput. Complex. 6 (3) (1997)
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
A Lower Bound for Randomized Algebraic Decision Trees. Comput. Complex. 6 (4) (1997)
Dima Grigoriev, Marek Karpinski, Roman Smolensky
Randomization and the Computational Power of Analytic and Algebraic Decision Trees. Comput. Complex. 6 (4) (1997)
Roman Smolensky
Easy Lower Bound for a Strange Computational Model. Comput. Complex. 6 (3) (1997)
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
A Lower Bound for Randomized Algebraic Decision Trees. STOC (1996)
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
A Lower Bound for Randomized Algebraic Decision Trees Electron. Colloquium Comput. Complex. 2 (63) (1995)
Allan Borodin, Alexander A. Razborov, Roman Smolensky
On Lower Bounds for Read-K-Times Branching Programs. Comput. Complex. 3 (1993)
Roman Smolensky
On Representations by Low-Degree Polynomials FOCS (1993)
Jehoshua Bruck, Roman Smolensky
Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms. SIAM J. Comput. 21 (1) (1992)
Victor Shoup, Roman Smolensky
Lower Bounds for Polynomial Evaluation and Interpolation Problems FOCS (1991)
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)
Jehoshua Bruck, Roman Smolensky
Polynomial Threshold Functions, AC^0 Functions and Spectral Norms (Extended Abstract) FOCS (1990)
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)
Roman Smolensky
Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity STOC (1987)
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)