Steven Rudich

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Weakly learning DNF and characterizing statistical query learning using Fourier analysis Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94	2016-09-01	Paper
Natural proofs Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94	2016-09-01	Paper
On the (im)possibility of obfuscating programs Journal of the ACM	2014-02-17	Paper
Fast learning of \(k\)-term DNF formulas with queries. Journal of Computer and System Sciences	2008-12-21	Paper
Learning a Hidden Matching SIAM Journal on Computing	2005-02-21	Paper
scientific article; zbMATH DE number 2134900 (Why is no real title available?)	2005-02-18	Paper
scientific article; zbMATH DE number 1842483 (Why is no real title available?)	2002-12-08	Paper
Communication complexity towards lower bounds on circuit depth Computational Complexity	2002-06-17	Paper
Reducing the complexity of reductions Computational Complexity	2002-05-05	Paper
scientific article; zbMATH DE number 1559593 (Why is no real title available?)	2001-03-01	Paper
Reductions in circuit complexity: An isomorphism theorem and a gap theorem Journal of Computer and System Sciences	1999-09-29	Paper
Products and Help Bits in Decision Trees SIAM Journal on Computing	1999-02-22	Paper
Natural proofs Journal of Computer and System Sciences	1997-12-03	Paper
The Wakeup Problem SIAM Journal on Computing	1997-06-09	Paper
Representing Boolean functions as polynomials modulo composite numbers Computational Complexity	1995-04-06	Paper
The expressive power of voting polynomials Combinatorica	1994-08-11	Paper
On dice and coins: Models of computation for random generation Information and Computation	1993-08-30	Paper
scientific article; zbMATH DE number 176554 (Why is no real title available?)	1993-05-18	Paper
Implicat Representation of Graphs SIAM Journal on Discrete Mathematics	1993-04-01	Paper
scientific article; zbMATH DE number 4185033 (Why is no real title available?)	1990-01-01	Paper
On the complexity of ranking Journal of Computer and System Sciences	1990-01-01	Paper
scientific article; zbMATH DE number 4117876 (Why is no real title available?)	1989-01-01	Paper
scientific article; zbMATH DE number 4068311 (Why is no real title available?)	1988-01-01	Paper

Research outcomes over time

This page was built for person: Steven Rudich