default search action
Martin Strauss 0001
Martin J. Strauss
Person information
- affiliation: University of Michigan, Ann Arbor, MI, USA
- affiliation (1997 - 2004): AT&T Labs-Research, Florham Park, NJ, USA
- affiliation (PhD 1996): Rutgers University, New Brunswick, NJ, USA
Other persons with the same name
- Martin Strauss 0002 — DFKI, Saarbrücken, Germany
- Martin Strauss 0003 — University of Erlangen-Nuremberg, Digital Sports Group, Germany
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2010 – 2019
- 2018
- [r2]Martin J. Strauss:
Histograms on Streams. Encyclopedia of Database Systems (2nd ed.) 2018 - 2017
- [j22]Anna C. Gilbert, Yi Li
, Ely Porat, Martin J. Strauss:
For-All Sparse Recovery in Near-Optimal Time. ACM Trans. Algorithms 13(3): 32:1-32:26 (2017) - [i14]Amanda Bower
Fair Pipelines. CoRR abs/1707.00391 (2017) - 2016
- [p1]S. Muthukrishnan, Martin Strauss:
Approximate Histogram and Wavelet Summaries of Streaming Data. Data Stream Management 2016: 263-281 - 2015
- [j21]Petros Boufounos, Volkan Cevher, Anna C. Gilbert, Yi Li
What's the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid. Algorithmica 73(2): 261-288 (2015) - 2014
- [c49]Anna C. Gilbert, Yi Li
For-All Sparse Recovery in Near-Optimal Time. ICALP (1) 2014: 538-550 - [i13]Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss:
For-all Sparse Recovery in Near-Optimal Time. CoRR abs/1402.1726 (2014) - 2013
- [c48]Anna C. Gilbert, Hung Q. Ngo, Ely Porat, Atri Rudra, Martin J. Strauss:
ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk. ICALP (1) 2013: 461-472 - [i12]Anna C. Gilbert, Hung Q. Ngo, Ely Porat, Atri Rudra, Martin J. Strauss:
L2/L2-foreach sparse recovery with low risk. CoRR abs/1304.6232 (2013) - 2012
- [j20]Anna C. Gilbert, Yi Li
Approximate Sparse Recovery: Optimizing Time and Measurements. SIAM J. Comput. 41(2): 436-453 (2012) - [c47]Petros Boufounos
What's the Frequency, Kenneth?: Sublinear Fourier Sampling Off the Grid. APPROX-RANDOM 2012: 61-72 - [c46]Anna C. Gilbert, Brett Hemenway, Atri Rudra, Martin J. Strauss, Mary Wootters:
Recovering simple signals. ITA 2012: 382-391 - [c45]Ely Porat, Martin J. Strauss:
Sublinear time, measurement-optimal, sparse recovery for all. SODA 2012: 1215-1227 - [c44]Anna C. Gilbert, Brett Hemenway, Martin J. Strauss, David P. Woodruff, Mary Wootters:
Reusable low-error compressive sampling schemes through privacy. SSP 2012: 536-539 - 2011
- [c43]Brett Hemenway, Rafail Ostrovsky, Martin J. Strauss, Mary Wootters:
Public Key Locally Decodable Codes with Short Keys. APPROX-RANDOM 2011: 605-615 - [i11]Brett Hemenway, Rafail Ostrovsky, Martin Strauss, Mary Wootters:
Public Key Locally Decodable Codes with Short Keys. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j19]Radu Berinde, Piotr Indyk, Graham Cormode
Space-optimal heavy hitters with strong error bounds. ACM Trans. Database Syst. 35(4): 26:1-26:28 (2010) - [c42]Anna C. Gilbert, Yi Li
Approximate sparse recovery: optimizing time and measurements. STOC 2010: 475-484 - [i10]Ely Porat, Martin J. Strauss:
Sublinear Time, Measurement-Optimal, Sparse Recovery For All. CoRR abs/1012.1886 (2010)
2000 – 2009
- 2009
- [j18]Yuval Ishai, Tal Malkin, Martin J. Strauss, Rebecca N. Wright:
Private multiparty sampling and approximation of vector combinations. Theor. Comput. Sci. 410(18): 1730-1745 (2009) - [c41]Volkan Cevher, Petros Boufounos, Richard G. Baraniuk, Anna C. Gilbert, Martin J. Strauss:
Near-optimal Bayesian localization via incoherence and sparsity. IPSN 2009: 205-216 - [c40]Radu Berinde, Graham Cormode
Space-optimal heavy hitters with strong error bounds. PODS 2009: 157-166 - [r1]Martin J. Strauss:
Histograms on Streams. Encyclopedia of Database Systems 2009: 1315-1318 - [i9]Anna C. Gilbert, Yi Li, Ely Porat, Martin J. Strauss:
Approximate Sparse Recovery: Optimizing Time and Measurements. CoRR abs/0912.0229 (2009) - 2008
- [j17]Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp
A Tutorial on Fast Fourier Sampling. IEEE Signal Process. Mag. 25(2): 57-66 (2008) - [c39]Anna C. Gilbert, Mark A. Iwen, Martin J. Strauss:
Group testing and sparse signal recovery. ACSCC 2008: 1059-1063 - [c38]Radu Berinde, Anna C. Gilbert, Piotr Indyk, Howard J. Karloff, Martin J. Strauss:
Combining geometry and combinatorics: A unified approach to sparse signal recovery. Allerton 2008: 798-805 - [c37]Anna C. Gilbert, Martin J. Strauss:
Fundamental performance bounds for a compressive sampling system. ICASSP 2008: 3841-3844 - [c36]Stephen Pfetsch, Tamer Ragheb, Jason N. Laska, Hamid Nejati, Anna C. Gilbert, Martin Strauss, Richard G. Baraniuk, Yehia Massoud:
On the feasibility of hardware implementation of sub-Nyquist random-sampling based analog-to-information conversion. ISCAS 2008: 1480-1483 - [c35]Joe Kilian, André Madeira, Martin J. Strauss, Xuan Zheng:
Fast Private Norm Estimation and Heavy Hitters. TCC 2008: 176-193 - [i8]Radu Berinde, Anna C. Gilbert, Piotr Indyk, Howard J. Karloff, Martin J. Strauss:
Combining geometry and combinatorics: A unified approach to sparse signal recovery. CoRR abs/0804.4666 (2008) - 2007
- [j16]Anna C. Gilbert, Martin J. Strauss:
Analysis of Data Streams: Computational and Algorithmic Challenges. Technometrics 49(3): 346-356 (2007) - [c34]Yuval Ishai, Tal Malkin, Martin J. Strauss, Rebecca N. Wright:
Private Multiparty Sampling and Approximation of Vector Combinations. ICALP 2007: 243-254 - [c33]Mark A. Iwen, Gurjit S. Mandair, Michael D. Morris, Martin Strauss:
Fast Line-Based Imaging of Small Sample Features. ICASSP (1) 2007: 421-424 - [c32]Ray Maleh, Anna C. Gilbert, Martin J. Strauss:
Sparse Gradient Image Reconstruction Done Faster. ICIP (2) 2007: 77-80 - [c31]Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, Roman Vershynin:
One sketch for all: fast algorithms for compressed sensing. STOC 2007: 237-246 - 2006
- [j15]Edith Cohen, Martin J. Strauss:
Maintaining time-decaying stream aggregates. J. Algorithms 59(1): 19-36 (2006) - [j14]Joel A. Tropp
Algorithms for simultaneous sparse approximation. Part I: Greedy pursuit. Signal Process. 86(3): 572-588 (2006) - [j13]Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J. Strauss, Rebecca N. Wright:
Secure multiparty computation of approximations. ACM Trans. Algorithms 2(3): 435-472 (2006) - [i7]A. Robert Calderbank, Anna C. Gilbert, Martin J. Strauss:
List decoding of noisy Reed-Muller-like codes. CoRR abs/cs/0607098 (2006) - [i6]Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, Roman Vershynin:
Algorithmic linear dimension reduction in the l_1 norm for sparse vectors. CoRR abs/cs/0608079 (2006) - [i5]Martin J. Strauss, Xuan Zheng:
Private Approximate Heavy Hitters. CoRR abs/cs/0609166 (2006) - 2005
- [j12]Jessica H. Fong, Anna C. Gilbert, Sampath Kannan, Martin J. Strauss:
Better Alternatives to OSPF Routing. Algorithmica 43(1-2): 113-131 (2005) - [j11]Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss:
Domain-Driven Data Synopses for Dynamic Quantiles. IEEE Trans. Knowl. Data Eng. 17(7): 927-938 (2005) - [c30]S. Muthukrishnan, Martin Strauss, Xuan Zheng:
Workload-Optimal Histograms on Streams. ESA 2005: 734-745 - [c29]Joel A. Tropp, Anna C. Gilbert, Martin J. Strauss:
Simultaneous sparse approximation via greedy pursuit. ICASSP (5) 2005: 721-724 - [c28]A. Robert Calderbank, Anna C. Gilbert, Kirill Levchenko, S. Muthukrishnan, Martin Strauss:
Improved range-summable random variable construction algorithms. SODA 2005: 840-849 - 2003
- [j10]Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss:
One-Pass Wavelet Decompositions of Data Streams. IEEE Trans. Knowl. Data Eng. 15(3): 541-554 (2003) - [c27]S. Muthukrishnan, Martin Strauss:
Maintenance of Multidimensional Histograms. FSTTCS 2003: 352-362 - [c26]Joel A. Tropp, Anna C. Gilbert, S. Muthukrishnan, Martin Strauss:
Improved sparse approximation over quasiincoherent dictionaries. ICIP (1) 2003: 37-40 - [c25]Edith Cohen, Martin Strauss:
Maintaining time-decaying stream aggregates. PODS 2003: 223-233 - [c24]S. Muthukrishnan, Martin Strauss:
Rangesum histograms. SODA 2003: 233-242 - [c23]Anna C. Gilbert, S. Muthukrishnan, Martin Strauss:
Approximation of functions over redundant dictionaries using coherence. SODA 2003: 243-252 - 2002
- [j9]Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan:
Testing and Spot-Checking of Data Streams. Algorithmica 34(1): 67-80 (2002) - [j8]Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan:
An Approximate L1-Difference Algorithm for Massive Data Streams. SIAM J. Comput. 32(1): 131-151 (2002) - [c22]Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss:
Histogramming Data Streams with Fast Per-Item Processing. ICALP 2002: 681-692 - [c21]Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss:
Near-optimal sparse fourier representations via sampling. STOC 2002: 152-161 - [c20]Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin Strauss:
Fast, small-space algorithms for approximate histogram maintenance. STOC 2002: 389-398 - [c19]Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss:
How to Summarize the Universe: Dynamic Maintenance of Quantiles. VLDB 2002: 454-465 - 2001
- [j7]Jessica H. Fong, Martin Strauss:
An Approximate Lp Difference Algorithm for Massive Data Streams. Discret. Math. Theor. Comput. Sci. 4(2): 301-322 (2001) - [c18]Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, Rebecca N. Wright:
Secure Multiparty Computation of Approximations. ICALP 2001: 927-938 - [c17]Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss:
Optimal and Approximate Computation of Summary Statistics for Range Aggregates. PODS 2001 - [c16]Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, Martin Strauss:
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries. VLDB 2001: 79-88 - [i4]Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, Rebecca N. Wright:
Secure Multiparty Computation of Approximations. IACR Cryptol. ePrint Arch. 2001: 24 (2001) - 2000
- [j6]Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss:
A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem. SIAM J. Comput. 30(2): 576-601 (2000) - [c15]Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan:
Testing and spot-checking of data streams (extended abstract). SODA 2000: 165-174 - [c14]Jack H. Lutz, Martin Strauss:
Bias Invariance of Small Upper Spans. STACS 2000: 74-86 - [c13]Jessica H. Fong, Martin Strauss:
An Approximate Lp-Difference Algorithm for Massive Data Streams. STACS 2000: 193-204
1990 – 1999
- 1999
- [c12]William Aiello, Aviel D. Rubin, Martin Strauss:
Using Smartcards to Secure a Personalized Gambling Device. CCS 1999: 128-137 - [c11]Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan:
An Approximate L1-Difference Algorithm for Massive Data Streams. FOCS 1999: 501-511 - [c10]Haim Kaplan, Martin Strauss, Mario Szegedy:
Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data. SODA 1999: 935-936 - 1998
- [c9]Matt Blaze, Gerrit Bleumer, Martin Strauss:
Divertible Protocols and Atomic Proxy Cryptography. EUROCRYPT 1998: 127-144 - [c8]Matt Blaze, Joan Feigenbaum, Martin Strauss:
Compliance Checking in the PolicyMaker Trust Management System. Financial Cryptography 1998: 254-274 - [c7]Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss:
A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract). STACS 1998: 161-171 - [i3]Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, Martin Strauss, D. Sivakumar:
A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [j5]Yang-Hua Chu, Joan Feigenbaum, Brian A. LaMacchia, Paul Resnick, Martin Strauss:
REFEREE: Trust Management for Web Applications. Comput. Networks 29(8-13): 953-964 (1997) - [j4]Matt Blaze, Joan Feigenbaum, Paul Resnick, Martin Strauss:
Managing trust in an information-labeling system. Eur. Trans. Telecommun. 8(5): 491-501 (1997) - [j3]Martin Strauss:
Measure on P: Strength of the Notion. Inf. Comput. 136(1): 1-23 (1997) - [j2]Martin Strauss:
Normal Numbers and Sources for BPP. Theor. Comput. Sci. 178(1-2): 155-169 (1997) - [j1]Yang-Hua Chu, Joan Feigenbaum, Brian A. LaMacchia, Paul Resnick, Martin Strauss:
Referee: trust management for Web applications. World Wide Web J. 2: 127-139 (1997) - [c6]Jin-yi Cai, D. Sivakumar, Martin Strauss:
Constant Depth Circuits and the Lutz Hypothesis. FOCS 1997: 595-604 - [c5]James I. Lathrop, Martin Strauss:
A universal upper bound on the performance of the Lempel-Ziv algorithm on maliciously-constructed data. SEQUENCES 1997: 123-135 - [c4]Joan Feigenbaum, Martin Strauss:
An Information-Theoretic Treatment of Random-Self-Reducibility (Extended Abstract). STACS 1997: 523-534 - 1995
- [c3]Eric Allender
Measure on P: Robustness of the Notion. MFCS 1995: 129-138 - [c2]Martin Strauss:
Normal Numbers and Sources for BPP. STACS 1995: 515-526 - [i2]Eric Allender, Martin Strauss:
Measure on P: Robustness of the Notion. Electron. Colloquium Comput. Complex. TR95 (1995) - 1994
- [c1]Eric Allender, Martin Strauss:
Measure on Small Complexity Classes, with Applications for BPP. FOCS 1994: 807-818 - [i1]Eric Allender, Martin Strauss:
Measure on Small Complexity Classes, with Applications for BPP. Electron. Colloquium Comput. Complex. TR94 (1994)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-30 20:32 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: