Publications

Disclaimers

• [Some of] this material is based upon work supported by the National Science Foundation under Grant Nos. 0510203 and 0354600. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
• Use in accordance with appropriate Copyright Rules. Some of the policies are contained here.
• This has not been (seriously) updated since early 2007 or so. See my cv for publication list.

Preprints and Technical Reports

• M. J. Strauss and X. Zheng, Private Approximate Heavy Hitters, 2006 (submitted).
• A. C. Gilbert, M. J. Strauss, J. A. Tropp, and R. Vershynin, Algorithmic linear dimension reduction in the l_1 norm for sparse vectors, 2006 (submitted).
• A. C. Gilbert and M. J. Strauss, Group testing in statistical signal recovery, 2006 (submitted).
• A. R. Calderbank, A. C. Gilbert, and M. J. Strauss, List decoding of noisy Reed-Muller-like codes, 2006 (submitted).
• A. Gilbert, Y. Kotidis, S. Muthukrishnan, M. Strauss, QuickSAND: Quick Summary and Analysis of Network Data, DIMACS Technical Report 2001-43, November 2001.

Refereed Journal Publications

• A. C. Gilbert and M. J. Strauss. Group testing in statistical signal recovery. To appear in Technometrics, 2007.
• X. Shi, L. A. Adamic, and M. Strauss. Networks of Strong Ties. Physica A: Statistical Mechanics and its Applications, Volume 378, Issue 1, 1 May 2007, pp. 33-47.

2006

• J. Feigenbaum, Y. Ishai, T. Malkin, K. Nissim, M. Strauss, R. Wright. Secure Multiparty Computation of Approximations. Transactions on Algorithms, pp. 435-472, 2006.
• E. Cohen and M. Strauss. Maintaining Time-Decaying Stream Aggregates, Journal of Algorithms, 59(1) 19-36, 2006.
• J. Zou, A. Gilbert, M. Strauss, and I. Daubechies, Theoretical and Experimental Analysis of a Randomized Algorithm for Sparse Fourier Transform Analysis, Journal of Computational Physics, vol. 211, No. 2, 2006, pp. 572-595.
• A. C. Gilbert, M. J. Strauss, and J. A. Tropp, Algorithms for Simultaneous Sparse Approximation. Part I: Greedy Pursuit, Special issue on sparse approximations in signal and image processing of EURASIP J. Signal Processing, Vol. 86, April 2006, pp. 572-588.

2005

• J. Fong, A. C. Gilbert, S. Kannan, and M. Strauss, Better alternatives to OSPF routing, special issue of Algorithmica on network design, vol. 43, Nos. 1-2, 2005, pp. 113-131.
• A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss, Domain-driven data synopses for dynamic quantiles, IEEE Transactions on Knowledge and Data Engineering, vol. 17, no. 7, 2005, pp. 927-938.

2003

• A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss, One-pass wavelet decompositions of data streams, IEEE Transactions on Knowledge and Data Engineering, vol. 15, no. 3, 2003, pp. 541-554.

2002

• J. Feigenbaum, S. Kannan, M. Strauss, and M. Vishwanathan, Testing and spot-checking data streams. Algorithmica, 34(1): 67-80, 2002.
• J. Feigenbaum, S. Kannan, M. Strauss, and M. Vishwanathan. An Approximate L1-Difference Algorithm for Massive Data Streams. SIAM J. Comput., 32(1): 131-151, 2002.

  2001

• J. Fong and M. Strauss. An Approximate Lp-Difference Algorithm for Massive Data Streams. Discrete Mathematics and Theoretical Computer Science pp. 4(2): 301-322, 2001.

  2000 and earlier

• H. Buhrman, D. van Melkebeek, K. Regan, D. Sivakumar and M. Strauss, A generalization of resource-bounded measure, with an application to the BPP vs. EXP problem. SIAM J. Comput. 30(2): 576-601, 2000.
• M. Blaze, J. Feigenbaum, P. Resnick, and M. Strauss. Managing trust in an information-labeling system. European Transactions on Telecommunications, 1997.
• Y.-H. Chu, J. Feigenbaum, B. LaMacchia, P. Resnick, M. Strauss, REFEREE: trust management for web applications, World Wide Web Journal, 2 1997, pages 127-139. (Reprinted from Proc. 6'th International World Wide Web Conference, World Wide Web Consortium, Cambridge 1997, pages 227-238.)
• M. Strauss, Measure on P: strength of the Notion, Information and Computation, 136(1), 1997, pages 1-23.
• M. Strauss, Normal numbers and sources for BPP. Theoretical Computer Science, Vol. 178, Number 1-2, 1997, pages 155-169.
• J. Chelikowsky, J. Phillips, M. Kamal and M. Strauss, Surface and thermodynamic interatomic force fields for silicon clusters and bulk phases, Physical Review Letters, v. 62 3 1989, pages 292-295.

Refereed Conference Publications

• Ray Maleh, Anna C. Gilbert, and Martin J. Strauss. Sparse gradient image reconstruction done faster. To appear at the International Conference on Image Processing (ICIP), 2007.
• Yuval Ishai, Tal Malkin, Martin J. Strauss and Rebecca N. Wright. Private Multiparty Sampling and Approximation of Vector Combinations. To appear in ICALP, 2007.
• A. C. Gilbert, M. J. Strauss, J. A. Tropp, and R. Vershynin, One sketch for all: Fast algorithms for compressed sensing. STOC 2007, Pages 237 - 246. long early version conference version.
• M. A. Iwen, G. Mandair, M. D. Morris, and M. Strauss. Fast Line-based Imaging of Small Sample Features. To appear as a poster in International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2007.

2006

• A. C. Gilbert, M. J. Strauss, J. A. Tropp, and R. Vershynin. Algorithmic linear dimension reduction in the ell1 norm for sparse vectors. Invited paper, special session on ``Compressed Sensing'' in Proceedings of the 44th Annual Allerton Conference on Communication, Control and Computing, Allerton, September 2006.

  2005

• S. Muthukrishnan, M. Strauss, and X. Zheng. Workload-Optimal Histograms on Streams. European Symposium on Algorithms (ESA) conference, 734-745, 2005.
• A. C. Gilbert, S. Muthukrishnan, and M. J. Strauss, Improved time bounds for near-optimal sparse Fourier representation via sampling, in Proceedings of SPIE Wavelets XI, San Diego, CA, 2005. Note copyright.
• J. Tropp, A. C. Gilbert, and M. J. Strauss, Simultaneous sparse approximation via greedy pursuit, invited paper, special session on ``Sparse representations in signal processing'', in Proceedings of the 2005 IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Philadelphia, PA, March 2005.
• A. R. Calderbank, A. C. Gilbert, K. Levchenko, S. Muthukrishnan, and M. Strauss, Improved range-summable random variable construction algorithms, in Proceedings of the 2005 SIAM Symposium on Discrete Algorithms (SODA), Vancouver, BC, 840-849, January 2005. Erratum.

2003

• E. Cohen and M. Strauss, Maintaining Time-Decaying Stream Aggregates, Principles of Database Systems (PODS), 223-233, 2003.
• J. A. Tropp, A. C. Gilbert, S. Muthukrishnan, and M. J. Strauss, Improved sparse approximation over quasi-incoherent dictionaries, IEEE International conference on image processing (ICIP), pp. 37-40, 2003.
• A. C. Gilbert, S. Muthukrishnan, and M. J. Strauss, Approximation of Functions over Redundant Dictionaries Using Coherence, in Proceedings of 2003 SIAM Symposium on Discrete Algorithms (SODA), pp. 243-252, 2003.
• S. Muthukrishnan and M. Strauss. Rangesum Histograms. in Proceedings of 2003 SIAM Symposium on Discrete Algorithms (SODA), pp. 233-242, 2003.
• S. Muthukrishnan and Martin Strauss. Maintenance of Multidimensional Histograms. Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 352-362, 2003.

  2002

• A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, M. J. Strauss, How to summarize the universe: Dynamic maintenance of quantiles, in Proc. of the 2002 Conference on Very Large Databases (VLDB), pp. 454-465, 2002.
• S. Guha, P. Indyk, S. Muthukrishnan, and M. Strauss. Histogramming Data Streams with Fast Per-Item Processing. International Colloquium on Automata, Languages and Programming (ICALP) conference, pp. 681-692, 2002.
• A. C. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, M. J. Strauss, Fast, Small-Space Algorithms for Approximate Histogram Maintenance, in Proc. of the 2002 ACM Symposium on Theory of Computing (STOC), pp. 389-398, 2002.
• A. C. Gilbert, S. Guha, P. Indyk, S. Muthukrishnan, M. J. Strauss, Near-Optimal Sparse Fourier Representations via Sampling, Proc. of the 2002 ACM Symposium on Theory of Computing (STOC), pp. 152-161, 2002.

2001

• A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, M. Strauss, Surfing wavelets on streams: one-pass summaries for approximate aggregate queries, in Proc. of the 2001 Conference on Very Large Databases (VLDB), pp. 79-88, 2001.
• J. Feigenbaum, Y. Ishai, T. Malkin, K. Nissim, M. Strauss, R. Wright. Secure Multiparty Computation of Approximations. International Colloquium on Automata, Languages and Programming (ICALP), 927-938, 2001.
• A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, M. Strauss, Optimal and Approximate Computation of Summary Statistics for Range Aggregates, in Proc. of the 2001 ACM Principles of Database Systems (PODS), pp. 227-236, Santa Barbara, 2001.

2000

• J. Fong and M. Strauss. An Approximate Lp-Difference Algorithm for Massive Data Streams. Symposium on Theoretical Aspects of Computer Science (STACS) conference, 193-204, 2000.
• J. Lutz and M. Strauss, Bias invariance of small upper spans. Symposium on Theoretical Aspects of Computer Science (STACS), 74-86, 2000.
• J. Feigenbaum, S. Kannan, M. Strauss, and M. Vishwanathan, Testing and spot-checking data streams. Proceedings of 2000 SIAM Symposium on Discrete Algorithms (SODA), 165-174, 2000.

  1999

• J. Feigenbaum, S. Kannan, M. Strauss, and M. Vishwanathan. An Approximate L1-Difference Algorithm for Massive Data Streams. Foundations of Computer Science (FOCS) conference, 501-511, 1999.
• W. Aiello, A. Rubin, and M. Strauss. Using smartcards to secure a personalized gambling device. Computer and Communication Security (CCS) conference, 128-137, 1999.
• Haim Kaplan, Martin Strauss, Mario Szegedy: Just the Fax—Differentiating Voice and Fax Phone Lines Using Call Billing Data. Symposium on Discrete Algorithms (SODA), 935-936, 1999.

  1998

• M. Blaze, G. Bleumer and M. Strauss. Protocol divertibility and atomic proxy cryptography. Eurocrypt conference, 127-144, 1998.
• M. Blaze, J. Feigenbaum and M. Strauss. Compliance checking in the PolicyMaker trust management system. Financial Cryptography (FC) conference (FC), 254-274, 1998.
• H. Buhrman, D. van Melkebeek, K. Regan, D. Sivakumar and M. Strauss, A generalization of resource-bounded measure, with an application to the BPP vs. EXP problem. Symposium on Theoretical Aspects of Computer Science (STACS), 161-171, 1998.

  1997 and earlier

• J. Feigenbaum and M. Strauss, An information-theoretic treatment of random-self-reducibility, Symposium on Theoretical Aspects of Computer Science (STACS), 523-534, 1997.
• J.-Y. Cai, D. Sivakumar, and M. Strauss. Constant-depth circuits and the Lutz hypothesis. Foundations of Computer Science (FOCS) Conference, 595-604, 1997.
• M. Strauss, Normal numbers and sources for BPP. Symposium on Theoretical Aspects of Computer Science (STACS), 515-526, 1995.
• E. Allender and M. Strauss. Measure on P: Robustness of the notion. Mathematical Foundations of Computer Science (MFCS) Conference, 129-138, 1995.
• E. Allender and M. Strauss, Measure on small complexity classes with applications for BPP, Proc. 35'th Foundations of Computer Science (FOCS) Conference (1994), pages 807-818.

Refereed Workshop Publications

• J. Laska, S. Kirolos, Y. Massoud, R. Baraniuk, A. Gilbert, M. Iwen, and M. Strauss. Random Sampling for Analog-to-Information Conversion of Wideband Signals. To appear in the Fifth IEEE Dallas Circuits and Systems Workshop, Oct., 2006.
• J. Fong, A. Gilbert, S. Kannan, and M. Strauss, Better alternatives to OSPF routing, in Proc. of Workshop on Approximation and Randomized Algorithms in Communication Networks (ARACNE), 2001.
• J. Lathrop and M. Strauss, A Universal Upper Bound on the Performance of the Lempel-Ziv Algorithm on Maliciously-Constructed Data. SEQUENCES'97.

PhD Thesis

• M. Strauss, Measure in Feasible Complexity Classes, Ph.D. Thesis, Rutgers University Mathematics Department, 1995.

[ Home | Research | Teaching | Vita | Funding ]