Martin Strauss

According to our database, Martin Strauss authored at least 69 papers between 1994 and 2018.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2018

Histograms on Streams.

Martin J. Strauss

Proceedings of the Encyclopedia of Database Systems, Second Edition, 2018

2017

For-All Sparse Recovery in Near-Optimal Time.

Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss

ACM Trans. Algorithms, 2017

Fair Pipelines.

Amanda Bower, Sarah N. Kitchen, Laura Niss, Martin J. Strauss, Alexander Vargas, Suresh Venkatasubramanian

CoRR, 2017

2016

Approximate Histogram and Wavelet Summaries of Streaming Data.

S. Muthukrishnan, Martin Strauss

Proceedings of the Data Stream Management - Processing High-Speed Data Streams, 2016

2015

What's the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid.

Petros Boufounos, Volkan Cevher, Anna C. Gilbert, Yi Li, Martin J. Strauss

Algorithmica, 2015

2013

ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk.

Anna C. Gilbert, Hung Q. Ngo, Ely Porat, Atri Rudra, Martin J. Strauss

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Approximate Sparse Recovery: Optimizing Time and Measurements.

Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss

SIAM J. Comput., 2012

Reusable low-error compressive sampling schemes through privacy.

Anna C. Gilbert, Brett Hemenway, Martin J. Strauss, David P. Woodruff, Mary Wootters

Proceedings of the IEEE Statistical Signal Processing Workshop, 2012

Sublinear time, measurement-optimal, sparse recovery for all.

Ely Porat, Martin J. Strauss

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Recovering simple signals.

Anna C. Gilbert, Brett Hemenway, Atri Rudra, Martin J. Strauss, Mary Wootters

Proceedings of the 2012 Information Theory and Applications Workshop, 2012

2011

Public Key Locally Decodable Codes with Short Keys.

Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters

Electron. Colloquium Comput. Complex., 2011

2010

Space-optimal heavy hitters with strong error bounds.

Radu Berinde, Piotr Indyk, Graham Cormode, Martin J. Strauss

ACM Trans. Database Syst., 2010

2009

Histograms on Streams.

Martin J. Strauss

Proceedings of the Encyclopedia of Database Systems, 2009

Private multiparty sampling and approximation of vector combinations.

Yuval Ishai, Tal Malkin, Martin J. Strauss, Rebecca N. Wright

Theor. Comput. Sci., 2009

Near-optimal Bayesian localization via incoherence and sparsity.

Volkan Cevher, Petros Boufounos, Richard G. Baraniuk, Anna C. Gilbert, Martin J. Strauss

Proceedings of the 8th International Conference on Information Processing in Sensor Networks, 2009

2008

A Tutorial on Fast Fourier Sampling.

Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp

IEEE Signal Process. Mag., 2008

Fast Private Norm Estimation and Heavy Hitters.

Joe Kilian, André Madeira, Martin J. Strauss, Xuan Zheng

Proceedings of the Theory of Cryptography, Fifth Theory of Cryptography Conference, 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, Richard G. Baraniuk, Yehia Massoud

Proceedings of the International Symposium on Circuits and Systems (ISCAS 2008), 2008

Fundamental performance bounds for a compressive sampling system.

Anna C. Gilbert, Martin J. Strauss

Proceedings of the IEEE International Conference on Acoustics, 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

Proceedings of the 46th Annual Allerton Conference on Communication, 2008

Group testing and sparse signal recovery.

Anna C. Gilbert, Mark A. Iwen, Martin J. Strauss

Proceedings of the 42nd Asilomar Conference on Signals, Systems and Computers, 2008

2007

Analysis of Data Streams: Computational and Algorithmic Challenges.

Anna C. Gilbert, Martin J. Strauss

Technometrics, 2007

One sketch for all: fast algorithms for compressed sensing.

Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, Roman Vershynin

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Sparse Gradient Image Reconstruction Done Faster.

Ray Maleh, Anna C. Gilbert, Martin J. Strauss

Proceedings of the International Conference on Image Processing, 2007

Fast Line-Based Imaging of Small Sample Features.

Mark A. Iwen, Gurjit S. Mandair, Michael D. Morris, Martin Strauss

Proceedings of the IEEE International Conference on Acoustics, 2007

2006

Secure multiparty computation of approximations.

Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J. Strauss, Rebecca N. Wright

ACM Trans. Algorithms, 2006

Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit.

Joel A. Tropp, Anna C. Gilbert, Martin J. Strauss

Signal Process., 2006

Maintaining time-decaying stream aggregates.

Edith Cohen, Martin J. Strauss

J. Algorithms, 2006

Private Approximate Heavy Hitters

Martin J. Strauss, Xuan Zheng

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

List decoding of noisy Reed-Muller-like codes

A. Robert Calderbank, Anna C. Gilbert, Martin J. Strauss

CoRR, 2006

2005

Domain-Driven Data Synopses for Dynamic Quantiles.

Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss

IEEE Trans. Knowl. Data Eng., 2005

Better Alternatives to OSPF Routing.

Jessica H. Fong, Anna C. Gilbert, Sampath Kannan, Martin J. Strauss

Algorithmica, 2005

Improved range-summable random variable construction algorithms.

A. Robert Calderbank, Anna C. Gilbert, Kirill Levchenko, S. Muthukrishnan, Martin Strauss

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Simultaneous sparse approximation via greedy pursuit.

Joel A. Tropp, Anna C. Gilbert, Martin J. Strauss

Proceedings of the 2005 IEEE International Conference on Acoustics, 2005

Workload-Optimal Histograms on Streams.

S. Muthukrishnan, Martin Strauss, Xuan Zheng

Proceedings of the Algorithms, 2005

2003

One-Pass Wavelet Decompositions of Data Streams.

Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss

IEEE Trans. Knowl. Data Eng., 2003

Rangesum histograms.

S. Muthukrishnan, Martin Strauss

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Approximation of functions over redundant dictionaries using coherence.

Anna C. Gilbert, S. Muthukrishnan, Martin Strauss

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Improved sparse approximation over quasiincoherent dictionaries.

Joel A. Tropp, Anna C. Gilbert, S. Muthukrishnan, Martin Strauss

Proceedings of the 2003 International Conference on Image Processing, 2003

Maintenance of Multidimensional Histograms.

S. Muthukrishnan, Martin Strauss

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

2002

An Approximate L1-Difference Algorithm for Massive Data Streams.

Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan

SIAM J. Comput., 2002

Testing and Spot-Checking of Data Streams.

Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan

Algorithmica, 2002

How to Summarize the Universe: Dynamic Maintenance of Quantiles.

Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss

Proceedings of 28th International Conference on Very Large Data Bases, 2002

Near-optimal sparse fourier representations via sampling.

Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Fast, small-space algorithms for approximate histogram maintenance.

Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin Strauss

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Histogramming Data Streams with Fast Per-Item Processing.

Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2001

An Approximate Lp Difference Algorithm for Massive Data Streams.

Jessica H. Fong, Martin Strauss

Discret. Math. Theor. Comput. Sci., 2001

Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries.

Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss

Proceedings of the VLDB 2001, 2001

Optimal and Approximate Computation of Summary Statistics for Range Aggregates.

Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss

Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

2000

A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem.

Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss

SIAM J. Comput., 2000

Bias Invariance of Small Upper Spans.

Jack H. Lutz, Martin Strauss

Proceedings of the STACS 2000, 2000

An Approximate L^p-Difference Algorithm for Massive Data Streams.

Jessica H. Fong, Martin Strauss

Proceedings of the STACS 2000, 2000

Testing and spot-checking of data streams (extended abstract).

Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999

Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data.

Haim Kaplan, Martin Strauss, Mario Szegedy

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

An Approximate L¹-Difference Algorithm for Massive Data Streams.

Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Using Smartcards to Secure a Personalized Gambling Device.

William Aiello, Aviel D. Rubin, Martin Strauss

Proceedings of the CCS '99, 1999

1998

A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract).

Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss

Proceedings of the STACS 98, 1998

Compliance Checking in the PolicyMaker Trust Management System.

Matt Blaze, Joan Feigenbaum, Martin Strauss

Proceedings of the Financial Cryptography, 1998

Divertible Protocols and Atomic Proxy Cryptography.

Matt Blaze, Gerrit Bleumer, Martin Strauss

Proceedings of the Advances in Cryptology - EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31, 1998

1997

Normal Numbers and Sources for BPP.

Martin Strauss

Theor. Comput. Sci., 1997

Measure on P: Strength of the Notion.

Martin Strauss

Inf. Comput., 1997

Managing trust in an information-labeling system.

Matt Blaze, Joan Feigenbaum, Paul Resnick, Martin Strauss

Eur. Trans. Telecommun., 1997

REFEREE: Trust Management for Web Applications.

Yang-Hua Chu, Joan Feigenbaum, Brian A. LaMacchia, Paul Resnick, Martin Strauss

Comput. Networks, 1997

An Information-Theoretic Treatment of Random-Self-Reducibility (Extended Abstract).

Joan Feigenbaum, Martin Strauss

Proceedings of the STACS 97, 14th Annual Symposium on Theoretical Aspects of Computer Science, Lübeck, Germany, February 27, 1997

A universal upper bound on the performance of the Lempel-Ziv algorithm on maliciously-constructed data.

James I. Lathrop, Martin Strauss

Proceedings of the Compression and Complexity of SEQUENCES 1997, 1997

Constant Depth Circuits and the Lutz Hypothesis.

Jin-yi Cai, D. Sivakumar, Martin Strauss

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1995

Measure on P: Robustness of the Notion

Eric Allender, Martin Strauss

Electron. Colloquium Comput. Complex., 1995

1994

Measure on Small Complexity Classes, with Applications for BPP

Eric Allender, Martin Strauss

Electron. Colloquium Comput. Complex., 1994