Measure on Small Complexity Classes, with Applications for BPP - Eric Allender; Martin Strauss 001 (FOCS, 1994)

Measure on P: Robustness of the Notion. - Eric Allender; Martin Strauss 001 (MFCS, 1995)

Normal Numbers and Sources for BPP. - Martin Strauss 001 (STACS, 1995)

Constant Depth Circuits and the Lutz Hypothesis. - Jin-yi Cai; D. Sivakumar; Martin Strauss 001 (FOCS, 1997)

A universal upper bound on the performance of the Lempel-Ziv algorithm on maliciously-constructed data. - James I. Lathrop; Martin Strauss 001 (SEQUENCES, 1997)

An Information-Theoretic Treatment of Random-Self-Reducibility (Extended Abstract). - Joan Feigenbaum; Martin Strauss 001 (STACS, 1997)

REFEREE: Trust Management for Web Applications. - Yang-Hua Chu; Joan Feigenbaum; Brian A. LaMacchia; Paul Resnick; Martin Strauss 001 (Comput. Networks, 1997)

Managing trust in an information-labeling system. - Matt Blaze; Joan Feigenbaum; Paul Resnick; Martin Strauss 001 (Eur. Trans. Telecommun., 1997)

Measure on P: Strength of the Notion. - Martin Strauss 001 (Inf. Comput., 1997)

Divertible Protocols and Atomic Proxy Cryptography. - Matt Blaze; Gerrit Bleumer; Martin Strauss 001 (EUROCRYPT, 1998)

Compliance Checking in the PolicyMaker Trust Management System. - Matt Blaze; Joan Feigenbaum; Martin Strauss 001 (Financial Cryptography, 1998)

A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract). - Harry Buhrman; Dieter van Melkebeek; Kenneth W. Regan; D. Sivakumar; Martin Strauss 001 (STACS, 1998)

A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem - Harry Buhrman; Dieter van Melkebeek; Kenneth W. Regan; Martin Strauss 001; D. Sivakumar (Electron. Colloquium Comput. Complex., 1998)

Using Smartcards to Secure a Personalized Gambling Device. - William Aiello; Aviel D. Rubin; Martin Strauss 001 (CCS, 1999)

An Approximate L1-Difference Algorithm for Massive Data Streams. - Joan Feigenbaum; Sampath Kannan; Martin Strauss 001; Mahesh Viswanathan 001 (FOCS, 1999)

Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. - Haim Kaplan; Martin Strauss 001; Mario Szegedy (SODA, 1999)

Testing and spot-checking of data streams (extended abstract). - Joan Feigenbaum; Sampath Kannan; Martin Strauss 001; Mahesh Viswanathan 001 (SODA, 2000)

An Approximate Lp-Difference Algorithm for Massive Data Streams. - Jessica H. Fong; Martin Strauss 001 (STACS, 2000)

Bias Invariance of Small Upper Spans. - Jack H. Lutz; Martin Strauss 001 (STACS, 2000)

Secure Multiparty Computation of Approximations. - Joan Feigenbaum; Yuval Ishai; Tal Malkin; Kobbi Nissim; Martin Strauss 001; Rebecca N. Wright (ICALP, 2001)

Optimal and Approximate Computation of Summary Statistics for Range Aggregates. - Anna C. Gilbert; Yannis Kotidis; S. Muthukrishnan 001; Martin Strauss 001 (PODS, 2001)

Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries. - Anna C. Gilbert; Yannis Kotidis; S. Muthukrishnan 001; Martin Strauss 001 (VLDB, 2001)

An Approximate Lp Difference Algorithm for Massive Data Streams. - Jessica H. Fong; Martin Strauss 001 (Discret. Math. Theor. Comput. Sci., 2001)

Histogramming Data Streams with Fast Per-Item Processing. - Sudipto Guha; Piotr Indyk; S. Muthukrishnan 001; Martin Strauss 001 (ICALP, 2002)

Fast, small-space algorithms for approximate histogram maintenance. - Anna C. Gilbert; Sudipto Guha; Piotr Indyk; Yannis Kotidis; S. Muthukrishnan 001; Martin Strauss 001 (STOC, 2002)

Near-optimal sparse fourier representations via sampling. - Anna C. Gilbert; Sudipto Guha; Piotr Indyk; S. Muthukrishnan 001; Martin Strauss 001 (STOC, 2002)

How to Summarize the Universe: Dynamic Maintenance of Quantiles. - Anna C. Gilbert; Yannis Kotidis; S. Muthukrishnan 001; Martin Strauss 001 (VLDB, 2002)

Testing and Spot-Checking of Data Streams. - Joan Feigenbaum; Sampath Kannan; Martin Strauss 001; Mahesh Viswanathan 001 (Algorithmica, 2002)

An Approximate L1-Difference Algorithm for Massive Data Streams. - Joan Feigenbaum; Sampath Kannan; Martin Strauss 001; Mahesh Viswanathan 001 (SIAM J. Comput., 2002)

Maintenance of Multidimensional Histograms. - S. Muthukrishnan 001; Martin Strauss 001 (FSTTCS, 2003)

Improved sparse approximation over quasiincoherent dictionaries. - Joel A. Tropp; Anna C. Gilbert; S. Muthukrishnan 001; Martin Strauss 001 (ICIP (1), 2003)

Maintaining time-decaying stream aggregates. - Edith Cohen; Martin Strauss 001 (PODS, 2003)

Approximation of functions over redundant dictionaries using coherence. - Anna C. Gilbert; S. Muthukrishnan 001; Martin Strauss 001 (SODA, 2003)

Rangesum histograms. - S. Muthukrishnan 001; Martin Strauss 001 (SODA, 2003)

One-Pass Wavelet Decompositions of Data Streams. - Anna C. Gilbert; Yannis Kotidis; S. Muthukrishnan 001; Martin Strauss 001 (IEEE Trans. Knowl. Data Eng., 2003)

Workload-Optimal Histograms on Streams. - S. Muthukrishnan 001; Martin Strauss 001; Xuan Zheng (ESA, 2005)

Simultaneous sparse approximation via greedy pursuit. - Joel A. Tropp; Anna C. Gilbert; Martin J. Strauss (ICASSP (5), 2005)

Improved range-summable random variable construction algorithms. - A. Robert Calderbank; Anna C. Gilbert; Kirill Levchenko; S. Muthukrishnan 001; Martin Strauss 001 (SODA, 2005)

Better Alternatives to OSPF Routing. - Jessica H. Fong; Anna C. Gilbert; Sampath Kannan; Martin J. Strauss (Algorithmica, 2005)

Domain-Driven Data Synopses for Dynamic Quantiles. - Anna C. Gilbert; Yannis Kotidis; S. Muthukrishnan 001; Martin Strauss 001 (IEEE Trans. Knowl. Data Eng., 2005)

List decoding of noisy Reed-Muller-like codes - A. Robert Calderbank; Anna C. Gilbert; Martin J. Strauss (CoRR, 2006)

Algorithmic linear dimension reduction in the l_1 norm for sparse vectors - Anna C. Gilbert; Martin J. Strauss; Joel A. Tropp; Roman Vershynin (CoRR, 2006)

Private Approximate Heavy Hitters - Martin J. Strauss; Xuan Zheng (CoRR, 2006)

Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit. - Joel A. Tropp; Anna C. Gilbert; Martin J. Strauss (Signal Process., 2006)

Private Multiparty Sampling and Approximation of Vector Combinations. - Yuval Ishai; Tal Malkin; Martin J. Strauss; Rebecca N. Wright (ICALP, 2007)

Fast Line-Based Imaging of Small Sample Features. - Mark A. Iwen; Gurjit S. Mandair; Michael D. Morris; Martin Strauss 001 (ICASSP (1), 2007)

Sparse Gradient Image Reconstruction Done Faster. - Ray Maleh; Anna C. Gilbert; Martin J. Strauss (ICIP (2), 2007)

One sketch for all: fast algorithms for compressed sensing. - Anna C. Gilbert; Martin J. Strauss; Joel A. Tropp; Roman Vershynin (STOC, 2007)

Analysis of Data Streams: Computational and Algorithmic Challenges. - Anna C. Gilbert; Martin J. Strauss (Technometrics, 2007)

Group testing and sparse signal recovery. - Anna C. Gilbert; Mark A. Iwen; Martin J. Strauss (ACSCC, 2008)

Combining geometry and combinatorics: A unified approach to sparse signal recovery. - Radu Berinde; Anna C. Gilbert; Piotr Indyk; Howard J. Karloff; Martin J. Strauss (Allerton, 2008)

Fundamental performance bounds for a compressive sampling system. - Anna C. Gilbert; Martin J. Strauss (ICASSP, 2008)

On the feasibility of hardware implementation of sub-Nyquist random-sampling based analog-to-information conversion. - Stephen Pfetsch; Tamer Ragheb; Jason N. Laska; Hamid Nejati; Anna C. Gilbert; Martin Strauss 001; Richard G. Baraniuk; Yehia Massoud (ISCAS, 2008)

Fast Private Norm Estimation and Heavy Hitters. - Joe Kilian; André Madeira; Martin J. Strauss; Xuan Zheng (TCC, 2008)

A Tutorial on Fast Fourier Sampling. - Anna C. Gilbert; Martin J. Strauss; Joel A. Tropp (IEEE Signal Process. Mag., 2008)

Near-optimal Bayesian localization via incoherence and sparsity. - Volkan Cevher; Petros Boufounos; Richard G. Baraniuk; Anna C. Gilbert; Martin J. Strauss (IPSN, 2009)

Space-optimal heavy hitters with strong error bounds. - Radu Berinde; Graham Cormode; Piotr Indyk; Martin J. Strauss (PODS, 2009)

Histograms on Streams. - Martin J. Strauss (Encyclopedia of Database Systems, 2009)

Approximate sparse recovery: optimizing time and measurements. - Anna C. Gilbert; Yi Li 002; Ely Porat; Martin J. Strauss (STOC, 2010)

Public Key Locally Decodable Codes with Short Keys. - Brett Hemenway; Rafail Ostrovsky; Martin J. Strauss; Mary Wootters (APPROX-RANDOM, 2011)

What's the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid. - Petros Boufounos; Volkan Cevher; Anna C. Gilbert; Yi Li 002; Martin J. Strauss (APPROX-RANDOM, 2012)

Recovering simple signals. - Anna C. Gilbert; Brett Hemenway; Atri Rudra; Martin J. Strauss; Mary Wootters (ITA, 2012)

Sublinear time, measurement-optimal, sparse recovery for all. - Ely Porat; Martin J. Strauss (SODA, 2012)

Reusable low-error compressive sampling schemes through privacy. - Anna C. Gilbert; Brett Hemenway; Martin J. Strauss; David P. Woodruff; Mary Wootters (SSP, 2012)

ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk. - Anna C. Gilbert; Hung Q. Ngo 001; Ely Porat; Atri Rudra; Martin J. Strauss (ICALP (1), 2013)

For-All Sparse Recovery in Near-Optimal Time. - Anna C. Gilbert; Yi Li 002; Ely Porat; Martin J. Strauss (ICALP (1), 2014)

Approximate Histogram and Wavelet Summaries of Streaming Data. - S. Muthukrishnan 001; Martin Strauss 001 (Data Stream Management, 2016)

Fair Pipelines. - Amanda Bower; Sarah N. Kitchen; Laura Niss; Martin J. Strauss; Alexander Vargas; Suresh Venkatasubramanian (CoRR, 2017)

Histograms on Streams. - Martin J. Strauss (Encyclopedia of Database Systems (2nd ed.), 2018)