Roman Smolensky

18 papers A* 8Journal 10
YearRankTypeTitle / Venue / Authors
1997 J jnl
A Lower Bound for Randomized Algebraic Decision Trees.
Comput. Complex.
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
1997 J jnl
Easy Lower Bound for a Strange Computational Model.
Comput. Complex.
Roman Smolensky
1997 J jnl
Lower Bounds for Polynomial Evaluation and Interpolation Problems.
Comput. Complex.
Victor Shoup, Roman Smolensky
1997 J jnl
Randomization and the Computational Power of Analytic and Algebraic Decision Trees.
Comput. Complex.
Dima Grigoriev, Marek Karpinski, Roman Smolensky
1997 J jnl
Representations of Sets of Boolean Functions by Commutative Rings.
Comput. Complex.
Roman Smolensky
1997 J jnl
The Electrical Resistance of a Graph Captures its Commute and Cover Times.
Comput. Complex.
Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, Prasoon Tiwari
1997 J jnl
Well-Known Bound for the VC-Dimension Made Easy.
Comput. Complex.
Roman Smolensky
1996 A* conf
A Lower Bound for Randomized Algebraic Decision Trees.
STOC
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
1995 J jnl
A Lower Bound for Randomized Algebraic Decision Trees
Electron. Colloquium Comput. Complex.
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
1993 J jnl
On Lower Bounds for Read-K-Times Branching Programs.
Comput. Complex.
Allan Borodin, Alexander A. Razborov, Roman Smolensky
1993 A* conf
On Representations by Low-Degree Polynomials
FOCS
Roman Smolensky
1992 J jnl
Polynomial Threshold Functions, AC^0 Functions, and Spectral Norms.
SIAM J. Comput.
Jehoshua Bruck, Roman Smolensky
1991 A* conf
Lower Bounds for Polynomial Evaluation and Interpolation Problems
FOCS
Victor Shoup, Roman Smolensky
1990 A* conf
On Interpolation by Analytic Functions with Special Properties and Some Weak Lower Bounds on the Size of Circuits with Symmetric Gates
FOCS
Roman Smolensky
1990 A* conf
Polynomial Threshold Functions, AC^0 Functions and Spectral Norms (Extended Abstract)
FOCS
Jehoshua Bruck, Roman Smolensky
1989 A* conf
The Electrical Resistance of a Graph Captures its Commute and Cover Times (Detailed Abstract)
STOC
Ashok K. Chandra, Prabhakar Raghavan, Walter L. Ruzzo, Roman Smolensky, Prasoon Tiwari
1987 A* conf
Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity
STOC
Roman Smolensky
1985 A* conf
The Bit Extraction Problem of t-Resilient Functions (Preliminary Version)
FOCS
Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, Roman Smolensky