dblp.uni-trier.dewww.uni-trier.de

Roman Smolensky

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeer - CSB - Google - MSN - Yahoo

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
11EEDima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky: A Lower Bound for Randomized Algebraic Decision Trees. STOC 1996: 612-619
1995
10EEDima 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

Coauthor Index

1Allan Borodin [8]
2Jehoshua Bruck [4] [7]
3Ashok K. Chandra [3] [14]
4Benny Chor [1]
5Joel Friedman [1]
6Oded Goldreich [1]
7Dima Grigoriev [10] [11] [12] [13]
8Johan Håstad [1]
9Friedhelm Meyer auf der Heide [10] [11] [13]
10Marek Karpinski [10] [11] [12] [13]
11Prabhakar Raghavan [3] [14]
12Alexander A. Razborov [8]
13Steven Rudich [1]
14Walter L. Ruzzo [3] [14]
15Victor Shoup [6] [15]
16Prasoon Tiwari [3] [14]

Colors in the list of coauthors

Copyright © Sun May 17 03:24:02 2009 by Michael Ley (ley@uni-trier.de)