default search action

combined dblp search
author search
venue search
publication search

ask others

David P. Woodruff

> Home > Persons

Person information

affiliation: Carnegie Mellon University, PA, USA
affiliation (former): IBM Almaden Research Center, San Jose, CA, USA
affiliation (PhD 2007): Massachusetts Institute of Technology (MIT), Cambridge, MA, USA

Refine list

refinements active!

zoomed in on ?? of ?? records

view refined list in

export refined list as

showing all ?? records

Books and Theses

see FAQ

What is the meaning of the colors in the publication lists?

2007
[b1]
- view
  - electronic edition via handle.net
  - details & citations
- export record
  dblp key:
  - phd/ndltd/Woodruff07
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/phd/ndltd/Woodruff07
David P. Woodruff:
Efficient and private distance approximation in the communication and streaming models. Massachusetts Institute of Technology, Cambridge, MA, USA, 2007

Journal Articles

see FAQ

What is the meaning of the colors in the publication lists?

2025
[j44]
- view
  authority control:
- export record
  dblp key:
  - journals/pacmmod/WoodruffXZ25
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/pacmmod/WoodruffXZ25
David P. Woodruff, Shenghao Xie, Samson Zhou:
Perfect Sampling in Turnstile Streams Beyond Small Moments. Proc. ACM Manag. Data 3(2): 106:1-106:27 (2025)
[j43]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/WoodruffY25
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/WoodruffY25
David P. Woodruff, Taisuke Yasuda:
Online Lewis Weight Sampling. ACM Trans. Algorithms 21(4): 39:1-39:50 (2025)
2024
[j42]
- view
  authority control:
- export record
  dblp key:
  - journals/pacmmod/JayaramWZ24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/pacmmod/JayaramWZ24
Rajesh Jayaram, David P. Woodruff, Samson Zhou:
Streaming Algorithms with Few State Changes. Proc. ACM Manag. Data 2(2): 82 (2024)
[j41]
- view
  authority control:
- export record
  dblp key:
  - journals/pacmmod/0002LLTWZ24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/pacmmod/0002LLTWZ24
Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, Jason Zhang:
Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut. Proc. ACM Manag. Data 2(2): 85 (2024)
2023
[j40]
- view
  authority control:
- export record
  dblp key:
  - journals/cacm/Woodruff23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/cacm/Woodruff23
David P. Woodruff:
Technical Perspective: Tapping the Link between Algorithmic Model Counting and Streaming. Commun. ACM 66(9): 94 (2023)
[j39]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/JayaramW23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/JayaramW23
Rajesh Jayaram, David P. Woodruff:
Towards Optimal Moment Estimation in Streaming and Distributed Models. ACM Trans. Algorithms 19(3): 27:1-27:35 (2023)
[j38]
- view
  authority control:
- export record
  dblp key:
  - journals/tit/HuLWZZ23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/tit/HuLWZZ23
Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang:
Recovery From Non-Decomposable Distance Oracles. IEEE Trans. Inf. Theory 69(10): 6443-6469 (2023)
[j37]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/toc/DuMW023
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/toc/DuMW023
Elbert Du, Michael Mitzenmacher, David P. Woodruff, Guang Yang:
Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. Theory Comput. 19: 1-44 (2023)
2022
[j36]
- view
  authority control:
- export record
  dblp key:
  - journals/jacm/Ben-EliezerJWY22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jacm/Ben-EliezerJWY22
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev:
A Framework for Adversarially Robust Streaming Algorithms. J. ACM 69(2): 17:1-17:33 (2022)
[j35]
- view
  authority control:
- export record
  dblp key:
  - journals/sigmod/Woodruff22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/sigmod/Woodruff22
David P. Woodruff:
Technical Perspective: Model Counting Meets Distinct Elements in a Data Stream. SIGMOD Rec. 51(1): 86 (2022)
[j34]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/WangW22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/WangW22
Ruosong Wang, David P. Woodruff:
Tight Bounds for ℓ₁ Oblivious Subspace Embeddings. ACM Trans. Algorithms 18(1): 8:1-8:32 (2022)
2021
[j33]
- view
  - electronic edition @ eatcs.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/eatcs/WoodruffB21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/eatcs/WoodruffB21
David P. Woodruff, Mikolaj Bojanczyk:
ICALP 2022 - 49th EATCS International Colloquium on Automata, Languages and Programming. Bull. EATCS 135 (2021)
[j32]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/JayaramW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/JayaramW21
Rajesh Jayaram, David P. Woodruff:
Perfect L_p Sampling in a Data Stream. SIAM J. Comput. 50(2): 382-439 (2021)
[j31]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/LiWW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/LiWW21
Yi Li, Ruosong Wang, David P. Woodruff:
Tight Bounds for the Subspace Sketch Problem with Applications. SIAM J. Comput. 50(4): 1287-1335 (2021)
[j30]
- view
  authority control:
- export record
  dblp key:
  - journals/sigmod/Ben-EliezerJWY21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/sigmod/Ben-EliezerJWY21
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev:
A Framework for Adversarially Robust Streaming Algorithms. SIGMOD Rec. 50(1): 6-13 (2021)
[j29]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/SunWYZ21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/SunWYZ21
Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang:
Querying a Matrix through Matrix-Vector Products. ACM Trans. Algorithms 17(4): 31:1-31:19 (2021)
[j28]
- view
  authority control:
- export record
  dblp key:
  - journals/tit/YangLDW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/tit/YangLDW21
Fan Yang, Sifan Liu, Edgar Dobriban, David P. Woodruff:
How to Reduce Dimension With PCA and Random Projections? IEEE Trans. Inf. Theory 67(12): 8154-8189 (2021)
2020
[j27]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/LeePW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/LeePW20
Yin Tat Lee, Marcin Pilipczuk, David P. Woodruff:
Introduction to the Special Issue on SODA'18. ACM Trans. Algorithms 16(1): 1:1-1:2 (2020)
2019
[j26]
- view
  - electronic edition @ jmlr.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/jmlr/BalcanLSW019
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jmlr/BalcanLSW019
Maria-Florina Balcan, Yingyu Liang, Zhao Song, David P. Woodruff, Hongyang Zhang:
Non-Convex Matrix Completion and Related Problems via Strong Duality. J. Mach. Learn. Res. 20: 102:1-102:56 (2019)
[j25]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/LiNW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/LiNW19
Yi Li, Huy L. Nguyen, David P. Woodruff:
On Approximating Matrix Norms in Data Streams. SIAM J. Comput. 48(6): 1643-1697 (2019)
[j24]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/BhattacharyyaDW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/BhattacharyyaDW19
Arnab Bhattacharyya, Palash Dey, David P. Woodruff:
An Optimal Algorithm for ℓ₁-Heavy Hitters in Insertion Streams and Related Problems. ACM Trans. Algorithms 15(1): 2:1-2:27 (2019)
2017
[j23]
- view
  authority control:
- export record
  dblp key:
  - journals/dc/WoodruffZ17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/dc/WoodruffZ17
David P. Woodruff, Qin Zhang:
When distributed computation is communication expensive. Distributed Comput. 30(5): 309-323 (2017)
[j22]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/BoutsidisW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/BoutsidisW17
Christos Boutsidis, David P. Woodruff:
Optimal CUR Matrix Decompositions. SIAM J. Comput. 46(2): 543-589 (2017)
[j21]
- view
  authority control:
- export record
  dblp key:
  - journals/siammax/AvronCW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siammax/AvronCW17
Haim Avron, Kenneth L. Clarkson, David P. Woodruff:
Faster Kernel Ridge Regression Using Sketching and Preconditioning. SIAM J. Matrix Anal. Appl. 38(4): 1116-1138 (2017)
2016
[j20]
- view
  authority control:
- export record
  dblp key:
  - journals/algorithmica/McGregorPTW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/algorithmica/McGregorPTW16
Andrew McGregor, A. Pavan, Srikanta Tirthapura, David P. Woodruff:
Space-Efficient Estimation of Statistics Over Sub-Sampled Streams. Algorithmica 74(2): 787-811 (2016)
[j19]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/algorithmica/BravermanW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/algorithmica/BravermanW16
Mark Braverman, David P. Woodruff:
Guest Editorial for Information Complexity and Applications. Algorithmica 76(3): 595-596 (2016)
[j18]
- view
  authority control:
- export record
  dblp key:
  - journals/algorithmica/BrodyCKWY16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/algorithmica/BrodyCKWY16
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev:
Certifying Equality With Limited Interaction. Algorithmica 76(3): 796-845 (2016)
[j17]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/ClarksonDMMMW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/ClarksonDMMMW16
Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff:
The Fast Cauchy Transform and Faster Robust Linear Regression. SIAM J. Comput. 45(3): 763-810 (2016)
[j16]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/GhashamiLPW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/GhashamiLPW16
Mina Ghashami, Edo Liberty, Jeff M. Phillips, David P. Woodruff:
Frequent Directions: Simple and Deterministic Matrix Sketching. SIAM J. Comput. 45(5): 1762-1792 (2016)
[j15]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/RabaniRSW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/RabaniRSW16
Yuval Rabani, Andréa W. Richa, Jared Saia, David P. Woodruff:
Editorial to the Special Issue on SODA'12. ACM Trans. Algorithms 12(1): 1:1 (2016)
[j14]
- view
  authority control:
- export record
  dblp key:
  - journals/tkde/ChungTW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/tkde/ChungTW16
Yung-Yu Chung, Srikanta Tirthapura, David P. Woodruff:
A Simple Message-Optimal Algorithm for Random Sampling from a Distributed Stream. IEEE Trans. Knowl. Data Eng. 28(6): 1356-1368 (2016)
2015
[j13]
- view
  authority control:
- export record
  dblp key:
  - journals/algorithmica/TirthapuraW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/algorithmica/TirthapuraW15
Srikanta Tirthapura, David P. Woodruff:
A General Method for Estimating Correlated Aggregates Over a Data Stream. Algorithmica 73(2): 235-260 (2015)
2014
[j12]
- view
  authority control:
- export record
  dblp key:
  - journals/combinatorica/BermanBGRWY14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/combinatorica/BermanBGRWY14
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev:
Steiner transitive-closure spanners of low-dimensional posets. Comb. 34(3): 255-277 (2014)
[j11]
- view
  - electronic edition @ eatcs.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/eatcs/Woodruff14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/eatcs/Woodruff14
David P. Woodruff:
Data Streams and Applications in Computer Science. Bull. EATCS 114 (2014)
[j10]
- view
  authority control:
- export record
  dblp key:
  - journals/fttcs/Woodruff14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/fttcs/Woodruff14
David P. Woodruff:
Sketching as a Tool for Numerical Linear Algebra. Found. Trends Theor. Comput. Sci. 10(1-2): 1-157 (2014)
2013
[j9]
- view
  authority control:
- export record
  dblp key:
  - journals/pvldb/KimelfeldVW13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/pvldb/KimelfeldVW13
Benny Kimelfeld, Jan Vondrák, David P. Woodruff:
Multi-Tuple Deletion Propagation: Approximations and Complexity. Proc. VLDB Endow. 6(13): 1558-1569 (2013)
[j8]
- view
  authority control:
- export record
  dblp key:
  - journals/talg/JayramW13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/talg/JayramW13
T. S. Jayram, David P. Woodruff:
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error. ACM Trans. Algorithms 9(3): 26:1-26:17 (2013)
2012
[j7]
- view
  authority control:
- export record
  dblp key:
  - journals/jacm/ClarksonHW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jacm/ClarksonHW12
Kenneth L. Clarkson, Elad Hazan, David P. Woodruff:
Sublinear optimization for machine learning. J. ACM 59(5): 23:1-23:49 (2012)
[j6]
- view
  authority control:
- export record
  dblp key:
  - journals/jcst/Woodruff12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jcst/Woodruff12
David P. Woodruff:
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. J. Comput. Sci. Technol. 27(4): 678-686 (2012)
[j5]
- view
  authority control:
- export record
  dblp key:
  - journals/jmlr/DrineasMMW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jmlr/DrineasMMW12
Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff:
Fast approximation of matrix coherence and statistical leverage. J. Mach. Learn. Res. 13: 3475-3506 (2012)
[j4]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/BhattacharyyaGJRW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/BhattacharyyaGJRW12
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-Closure Spanners. SIAM J. Comput. 41(6): 1380-1425 (2012)
[j3]
- view
  authority control:
- export record
  dblp key:
  - journals/siamdm/BhattacharyyaGJJRW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamdm/BhattacharyyaGJJRW12
Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. SIAM J. Discret. Math. 26(2): 618-646 (2012)
2010
[j2]
- view
  authority control:
- export record
  dblp key:
  - journals/jacm/EvfimievskiFW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/jacm/EvfimievskiFW10
Alexandre V. Evfimievski, Ronald Fagin, David P. Woodruff:
Epistemic privacy. J. ACM 58(1): 2:1-2:45 (2010)
2007
[j1]
- view
  authority control:
- export record
  dblp key:
  - journals/siamcomp/WoodruffY07
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/siamcomp/WoodruffY07
David P. Woodruff, Sergey Yekhanin:
A Geometric Approach to Information-Theoretic Private Information Retrieval. SIAM J. Comput. 37(4): 1046-1056 (2007)

Conference and Workshop Papers

see FAQ

What is the meaning of the colors in the publication lists?

2025
[c292]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/CekirgeGW25
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/CekirgeGW25
N. Efe Çekirge, William Gay, David P. Woodruff:
Multipass Linear Sketches for Geometric LP-Type Problems. APPROX/RANDOM 2025: 8:1-8:25
[c291]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/compgeom/DriemelM0SW25
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/compgeom/DriemelM0SW25
Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, David P. Woodruff:
Range Counting Oracles for Geometric Problems. SoCG 2025: 42:1-42:16
[c290]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/BhaskaraMPVW25
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/BhaskaraMPVW25
Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu, Ali Vakilian, David P. Woodruff:
Guessing Efficiently for Constrained Subspace Approximation. ICALP 2025: 29:1-29:20
[c289]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/FengSW25
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/FengSW25
Shiyuan Feng, William Swartworth, David P. Woodruff:
Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model. ICALP 2025: 75:1-75:19
[c288]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/ChakrabartiJW025
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/ChakrabartiJW025
Amit Chakrabarti, Jeffrey Jiang, David P. Woodruff, Taisuke Yasuda:
Streaming Algorithms For ℓp Flows and ℓp Regression. ICLR 2025
[c287]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/KannanBKW25
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/KannanBKW25
Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham, David P. Woodruff:
LevAttention: Time, Space and Streaming Efficient Algorithm for Heavy Attentions. ICLR 2025
[c286]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/SilwalW025
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/SilwalW025
Sandeep Silwal, David P. Woodruff, Qiuyi Zhang:
Beyond Worst-Case Dimensionality Reduction for Sparse Vectors. ICLR 2025
[c285]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/innovations/0001G0LNSW25
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/0001G0LNSW25
Matthew Ding, Alexandro Garces, Jason Li, Honghao Lin, Jelani Nelson, Vihan Shah, David P. Woodruff:
Space Complexity of Minimum Cut Problems in Single-Pass Streams. ITCS 2025: 43:1-43:23
[c284]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/SwartworthW25
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/SwartworthW25
William Swartworth, David P. Woodruff:
Tight Sampling Bounds for Eigenvalue Approximation. SODA 2025: 489-516
[c283]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/GribelyukLWYZ25
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/GribelyukLWYZ25
Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness. STOC 2025: 395-406
2024
[c282]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/KachamW24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/KachamW24
Praneeth Kacham, David P. Woodruff:
Faster Algorithms for Schatten-p Low Rank Approximation. APPROX/RANDOM 2024: 55:1-55:19
[c281]
- view
  authority control:
- export record
  dblp key:
  - conf/emnlp/MuhamedLWDS24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/emnlp/MuhamedLWDS24
Aashiq Muhamed, Oscar Li, David P. Woodruff, Mona T. Diab, Virginia Smith:
GRASS: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients. EMNLP 2024: 14978-15003
[c280]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/GribelyukLWYZ24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/GribelyukLWYZ24
Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches. FOCS 2024: 2318-2343
[c279]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/0002LW24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/0002LW24
Yi Li, Honghao Lin, David P. Woodruff:
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms. ICLR 2024
[c278]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/HanJKMWZ24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/HanJKMWZ24
Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, Amir Zandieh:
HyperAttention: Long-context Attention in Near-Linear Time. ICLR 2024
[c277]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/Lu0CZWH24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/Lu0CZWH24
Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David P. Woodruff, Elad Hazan:
Adaptive Regret for Bandits Made Possible: Two Queries Suffice. ICLR 2024
[c276]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/AxiotisCHJMSWW24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/AxiotisCHJMSWW24
Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, Michael Wunder:
Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond. ICML 2024
[c275]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/EsfandiariKMWZ24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/EsfandiariKMWZ24
Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong:
High-Dimensional Geometric Streaming for Nearly Low Rank Data. ICML 2024
[c274]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/FengJW24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/FengJW24
Ying Feng, Aayush Jain, David P. Woodruff:
Fast White-Box Adversarial Streaming Without a Random Oracle. ICML 2024
[c273]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/PrabhuW24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/PrabhuW24
Milind Prabhu, David P. Woodruff:
Learning Multiple Secrets in Mastermind. ICML 2024
[c272]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/SwartworthW24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/SwartworthW24
William J. Swartworth, David P. Woodruff:
Fast Sampling-Based Sketches for Tensors. ICML 2024
[c271]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/Woodruff024
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/Woodruff024
David P. Woodruff, Taisuke Yasuda:
Reweighted Solutions for Weighted Low Rank Approximation. ICML 2024
[c270]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/Woodruff024a
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/Woodruff024a
David P. Woodruff, Taisuke Yasuda:
Coresets for Multiple ℓp Regression. ICML 2024
[c269]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/innovations/BhattacharjeeDM24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/BhattacharjeeDM24
Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff:
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. ITCS 2024: 13:1-13:24
[c268]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/innovations/ChenIW24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/ChenIW24
Justin Y. Chen, Piotr Indyk, David P. Woodruff:
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions. ITCS 2024: 32:1-32:22
[c267]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/innovations/MahankaliWZ24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/MahankaliWZ24
Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang:
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions. ITCS 2024: 79:1-79:23
[c266]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/0002VWZ24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/0002VWZ24
Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou:
On Socially Fair Low-Rank Approximation and Column Subset Selection. NeurIPS 2024
[c265]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/JiaPTWZZ24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/JiaPTWZZ24
Zhihao Jia, Qi Pang, Trung Tran, David P. Woodruff, Zhihao Zhang, Wenting Zheng:
Communication Bounds for the Distributed Experts Problem. NeurIPS 2024
[c264]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/KachamW24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/KachamW24
Praneeth Kacham, David P. Woodruff:
Approximating the Top Eigenvector in Random Order Streams. NeurIPS 2024
[c263]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/ShirzadLVVWS24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/ShirzadLVVWS24
Hamed Shirzad, Honghao Lin, Balaji Venkatachalam, Ameya Velingker, David P. Woodruff, Danica J. Sutherland:
Even Sparser Graph Transformers. NeurIPS 2024
[c262]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/Woodruff024
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/Woodruff024
David P. Woodruff, Taisuke Yasuda:
John Ellipsoids via Lazy Updates. NeurIPS 2024
[c261]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/WoodruffZ24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/WoodruffZ24
David P. Woodruff, Samson Zhou:
Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters. NeurIPS 2024
[c260]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/Woodruff24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/Woodruff24
David P. Woodruff:
Approximation Algorithms on Matrices - With Some Database Applications! PODS Companion 2024: 5-6
[c259]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/GhadiriLPSWY24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/GhadiriLPSWY24
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, Guanghao Ye:
Improving the Bit Complexity of Communication for Distributed Convex Optimization. STOC 2024: 1130-1140
[c258]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/BravermanGLWWZ24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/BravermanGLWWZ24
Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang:
A New Information Complexity Measure for Multi-pass Streaming with Applications. STOC 2024: 1781-1792
[c257]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/EsfandiariKMWZ24
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/EsfandiariKMWZ24
Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong:
Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond. STOC 2024: 1911-1922
2023
[c256]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/aistats/MaiMM0SW23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/aistats/MaiMM0SW23
Tung Mai, Alexander Munteanu, Cameron Musco, Anup Rao, Chris Schwiegelshohn, David P. Woodruff:
Optimal Sketching Bounds for Sparse Linear Regression. AISTATS 2023: 11288-11316
[c255]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/colt/LiLW23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/colt/LiLW23
Yi Li, Honghao Lin, David P. Woodruff:
ℓ_p-Regression in the Arbitrary Partition Model of Communication. COLT 2023: 4902-4928
[c254]
- view
  authority control:
- export record
  dblp key:
  - conf/eurocrypt/DinurSWZ23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/eurocrypt/DinurSWZ23
Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou:
On Differential Privacy and Adaptive Data Analysis with Bounded Space. EUROCRYPT (3) 2023: 35-65
[c253]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/Cohen-AddadWZ23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/Cohen-AddadWZ23
Vincent Cohen-Addad, David P. Woodruff, Samson Zhou:
Streaming Euclidean k-median and k-means with o(log n) Space. FOCS 2023: 883-908
[c252]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/KachamPTW23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/KachamPTW23
Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff:
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming. FOCS 2023: 1515-1550
[c251]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/0002LLVW23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/0002LLVW23
Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff:
Learning the Positions in CountSketch. ICLR 2023
[c250]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/CherapanamjeriS23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/CherapanamjeriS23
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou:
Robust Algorithms on Adaptive Inputs from Bounded Adversaries. ICLR 2023
[c249]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/MunteanuOW23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/MunteanuOW23
Alexander Munteanu, Simon Omlor, David P. Woodruff:
Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression. ICLR 2023
[c248]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/FengW23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/FengW23
Ying Feng, David P. Woodruff:
Improved Algorithms for White-Box Adversarial Streams. ICML 2023: 9962-9975
[c247]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/VelingkerVWZ23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/VelingkerVWZ23
Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou:
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. ICML 2023: 34952-34977
[c246]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/WoodruffY23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/WoodruffY23
David P. Woodruff, Taisuke Yasuda:
Sharper Bounds for ℓ_p Sensitivity Sampling. ICML 2023: 37238-37272
[c245]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/innovations/HuLW0Z23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/HuLW0Z23
Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang:
Recovery from Non-Decomposable Distance Oracles. ITCS 2023: 73:1-73:22
[c244]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/DexterDW023
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/DexterDW023
Gregory Dexter, Petros Drineas, David P. Woodruff, Taisuke Yasuda:
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming. NeurIPS 2023
[c243]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/KachamW23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/KachamW23
Praneeth Kacham, David P. Woodruff:
Lower Bounds on Adaptive Sensing for Matrix Recovery. NeurIPS 2023
[c242]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/PadmanabhanWZ23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/PadmanabhanWZ23
Swati Padmanabhan, David P. Woodruff, Richard Zhang:
Computing Approximate 𝓁_p Sensitivities. NeurIPS 2023
[c241]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/SarlosSWZ23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/SarlosSWZ23
Tamás Sarlós, Xingyou Song, David P. Woodruff, Richard Zhang:
Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products. NeurIPS 2023
[c240]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/WoodruffZZ23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/WoodruffZZ23
David P. Woodruff, Peilin Zhong, Samson Zhou:
Near-Optimal k-Clustering in the Sliding Window Model. NeurIPS 2023
[c239]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/WoodruffZZ23a
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/WoodruffZZ23a
David P. Woodruff, Fred Zhang, Samson Zhou:
On Robust Streaming for Learning with Experts: Algorithms and Lower Bounds. NeurIPS 2023
[c238]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/0002LW23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/0002LW23
Yi Li, Honghao Lin, David P. Woodruff:
The ℓ_p-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines. SODA 2023: 850-877
[c237]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/MeyerMMWZ23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/MeyerMMWZ23
Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Near-Linear Sample Complexity for L_p Polynomial Regression. SODA 2023: 3959-4025
[c236]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/CherapanamjeriS23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/CherapanamjeriS23
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. SODA 2023: 4026-4049
[c235]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/Woodruff023
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/Woodruff023
David P. Woodruff, Taisuke Yasuda:
Online Lewis Weight Sampling. SODA 2023: 4622-4666
[c234]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/SwartworthW23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/SwartworthW23
William Swartworth, David P. Woodruff:
Optimal Eigenvalue Approximation via Sketching. STOC 2023: 145-155
[c233]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/Woodruff023
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/Woodruff023
David P. Woodruff, Taisuke Yasuda:
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online. STOC 2023: 1802-1813
2022
[c232]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/LiLWZ22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/LiLWZ22
Yi Li, Honghao Lin, David P. Woodruff, Yuheng Zhang:
Streaming Algorithms with Large Approximation Factors. APPROX/RANDOM 2022: 13:1-13:23
[c231]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/MahabadiWZ22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/MahabadiWZ22
Sepideh Mahabadi, David P. Woodruff, Samson Zhou:
Adaptive Sketches for Robust Regression with Importance Sampling. APPROX/RANDOM 2022: 31:1-31:21
[c230]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/NeedellSW22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/NeedellSW22
Deanna Needell, William Swartworth, David P. Woodruff:
Testing Positive Semidefiniteness Using Linear Measurements. FOCS 2022: 87-97
[c229]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/Woodruff022
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/Woodruff022
David P. Woodruff, Taisuke Yasuda:
High-Dimensional Geometric Streaming in Polynomial Space. FOCS 2022: 732-743
[c228]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/MuscoMW022
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/MuscoMW022
Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda:
Active Linear Regression for ℓp Norms and Beyond. FOCS 2022: 744-753
[c227]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/ChenEILNRSWWZ22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/ChenEILNRSWWZ22
Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang:
Triangle and Four Cycle Counting with Predictions in Graph Streams. ICLR 2022
[c226]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/ErgunFSWZ22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/ErgunFSWZ22
Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Learning-Augmented $k$-means Clustering. ICLR 2022
[c225]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/MeyerMMWZ22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/MeyerMMWZ22
Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Fast Regression for Structured Inputs. ICLR 2022
[c224]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/ChepurkoCHLW22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/ChepurkoCHLW22
Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin, David P. Woodruff:
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra. ICML 2022: 3879-3900
[c223]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/KachamW22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/KachamW22
Praneeth Kacham, David P. Woodruff:
Sketching Algorithms and Lower Bounds for Ridge Regression. ICML 2022: 10539-10556
[c222]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/LinLW22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/LinLW22
Honghao Lin, Tian Luo, David P. Woodruff:
Learning Augmented Binary Search Trees. ICML 2022: 13431-13440
[c221]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/MunteanuO0W22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/MunteanuO0W22
Alexander Munteanu, Simon Omlor, Zhao Song, David P. Woodruff:
Bounding the Width of Neural Networks via Coupled Initialization A Worst Case Analysis. ICML 2022: 16083-16122
[c220]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/WoodruffZ22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/WoodruffZ22
David P. Woodruff, Amir Zandieh:
Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time. ICML 2022: 23933-23964
[c219]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/innovations/BawejaJW22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/BawejaJW22
Anubhav Baweja, Justin Jia, David P. Woodruff:
An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes. ITCS 2022: 16:1-16:23
[c218]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/innovations/KapralovMTWZ22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/KapralovMTWZ22
Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou:
Noisy Boolean Hidden Matching with Applications. ITCS 2022: 91:1-91:19
[c217]
- view
  - electronic edition @ nips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/WoodruffZ022
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/WoodruffZ022
David P. Woodruff, Fred Zhang, Richard Zhang:
Optimal Query Complexities for Dynamic Trace Estimation. NeurIPS 2022
[c216]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/AjtaiBJSSWZ22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/AjtaiBJSSWZ22
Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou:
The White-Box Adversarial Data Stream Model. PODS 2022: 15-27
[c215]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/JayaramWZ22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/JayaramWZ22
Rajesh Jayaram, David P. Woodruff, Samson Zhou:
Truly Perfect Samplers for Data Streams and Sliding Windows. PODS 2022: 29-40
[c214]
- view
  authority control:
- export record
  dblp key:
  - conf/recomb/ChowdhuryBZWD22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/recomb/ChowdhuryBZWD22
Agniva Chowdhury, Aritra Bose, Samson Zhou, David P. Woodruff, Petros Drineas:
A Fast, Provably Accurate Approximation Algorithm for Sparse Principal Component Analysis Reveals Human Genetic Variation Across the World. RECOMB 2022: 86-106
[c213]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/IndykNW22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/IndykNW22
Piotr Indyk, Shyam Narayanan, David P. Woodruff:
Frequency Estimation with One-Sided Error. SODA 2022: 695-707
[c212]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/WoodruffY22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/WoodruffY22
David P. Woodruff, Taisuke Yasuda:
Improved Algorithms for Low Rank Approximation from Sparsity. SODA 2022: 2358-2403
[c211]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/ChepurkoCKW22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/ChepurkoCKW22
Nadiia Chepurko, Kenneth L. Clarkson, Praneeth Kacham, David P. Woodruff:
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. SODA 2022: 3043-3068
[c210]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/BakshiCW22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/BakshiCW22
Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff:
Low-rank approximation with 1/ε^1/3 matrix-vector products. STOC 2022: 1130-1143
[c209]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/SrinivasWXZ22
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/SrinivasWXZ22
Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou:
Memory bounds for the experts problem. STOC 2022: 1158-1171
2021
[c208]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/0002W21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/0002W21
Yi Li, David P. Woodruff:
The Product of Gaussian Matrices Is Close to Gaussian. APPROX-RANDOM 2021: 35:1-35:22
[c207]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/coco/KamathPW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/coco/KamathPW21
Akshay Kamath, Eric Price, David P. Woodruff:
A Simple Proof of a New Set Disjointness with Applications to Data Streams. CCC 2021: 37:1-37:24
[c206]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/colt/KachamW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/colt/KachamW21
Praneeth Kacham, David P. Woodruff:
Reduced-Rank Regression with Operator Norm Error. COLT 2021: 2679-2716
[c205]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/colt/LiW021
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/colt/LiW021
Yi Li, David P. Woodruff, Taisuke Yasuda:
Exponentially Improved Dimensionality Reduction for l1: Subspace Embeddings and Independence Testing. COLT 2021: 3111-3195
[c204]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/colt/RashtchianW0Z21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/colt/RashtchianW0Z21
Cyrus Rashtchian, David P. Woodruff, Peng Ye, Hanlin Zhu:
Average-Case Communication Complexity of Statistical Problems. COLT 2021: 3859-3886
[c203]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/WoodruffZ21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/WoodruffZ21
David P. Woodruff, Samson Zhou:
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. FOCS 2021: 1183-1196
[c202]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/Woodruff21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/Woodruff21
David P. Woodruff:
A Very Sketchy Talk (Invited Talk). ICALP 2021: 6:1-6:8
[c201]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/WoodruffZ21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/WoodruffZ21
David P. Woodruff, Samson Zhou:
Separations for Estimating Large Frequency Moments on Data Streams. ICALP 2021: 112:1-112:21
[c200]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/BakshiBKWZ21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/BakshiBKWZ21
Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou:
Learning a Latent Simplex in Input Sparsity Time. ICLR 2021
[c199]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/FengKW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/FengKW21
Zhili Feng, Praneeth Kacham, David P. Woodruff:
Dimensionality Reduction for the Sum-of-Distances Metric. ICML 2021: 3220-3229
[c198]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/JayaramSWY21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/JayaramSWY21
Rajesh Jayaram, Alireza Samadian, David P. Woodruff, Peng Ye:
In-Database Regression in Input Sparsity Time. ICML 2021: 4797-4806
[c197]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/JiangLLMW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/JiangLLMW21
Shuli Jiang, Dennis Li, Irene Mengze Li, Arvind V. Mahankali, David P. Woodruff:
Streaming and Distributed Algorithms for Robust Column Subset Selection. ICML 2021: 4971-4981
[c196]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/JiangLSWW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/JiangLSWW21
Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David P. Woodruff:
Single Pass Entrywise-Transformed Low Rank Approximation. ICML 2021: 4982-4991
[c195]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/MunteanuOW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/MunteanuOW21
Alexander Munteanu, Simon Omlor, David P. Woodruff:
Oblivious Sketching for Logistic Regression. ICML 2021: 7861-7871
[c194]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/0002WYZ21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/0002WYZ21
Zhao Song, David P. Woodruff, Zheng Yu, Lichen Zhang:
Fast Sketching of Polynomial Kernels of Polynomial Degree. ICML 2021: 9812-9823
[c193]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/innovations/MuscoMW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/MuscoMW21
Cameron Musco, Christopher Musco, David P. Woodruff:
Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation. ITCS 2021: 6:1-6:20
[c192]
- view
  - electronic edition @ neurips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/IndykWW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/IndykWW21
Piotr Indyk, Tal Wagner, David P. Woodruff:
Few-Shot Data-Driven Algorithms for Low Rank Approximation. NeurIPS 2021: 10678-10690
[c191]
- view
  - electronic edition @ neurips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/MahankaliW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/MahankaliW21
Arvind V. Mahankali, David P. Woodruff:
Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters. NeurIPS 2021: 14407-14420
[c190]
- view
  - electronic edition @ neurips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/JiangPWZ21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/JiangPWZ21
Shuli Jiang, Hai Pham, David P. Woodruff, Qiuyi (Richard) Zhang:
Optimal Sketching for Trace Estimation. NeurIPS 2021: 23741-23753
[c189]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/CormodeDW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/CormodeDW21
Graham Cormode, Charlie Dickens, David P. Woodruff:
Subspace Exploration: Bounds on Projected Frequency Estimation. PODS 2021: 273-284
[c188]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/MahankaliW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/MahankaliW21
Arvind V. Mahankali, David P. Woodruff:
Optimal ℓ₁ Column Subset Selection and a Fast PTAS for Low Rank Approximation. SODA 2021: 560-578
[c187]
- view
  authority control:
- export record
  dblp key:
  - conf/sosa/MeyerMMW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/sosa/MeyerMMW21
Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff:
Hutch++: Optimal Stochastic Trace Estimation. SOSA 2021: 142-155
[c186]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/uai/FengRW21
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/uai/FengRW21
Zhili Feng, Fred Roosta, David P. Woodruff:
Non-PSD matrix sketching with applications to regression and optimization. UAI 2021: 1841-1851
2020
[c185]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/aistats/KachamW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/aistats/KachamW20
Praneeth Kacham, David P. Woodruff:
Optimal Deterministic Coresets for Ridge Regression. AISTATS 2020: 4141-4150
[c184]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/aistats/LiaoPPW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/aistats/LiaoPPW20
Hang Liao, Barak A. Pearlmutter, Vamsi K. Potluru, David P. Woodruff:
Automatic Differentiation of Sketched Regression. AISTATS 2020: 4367-4376
[c183]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/RashtchianWZ20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/RashtchianWZ20
Cyrus Rashtchian, David P. Woodruff, Hanlin Zhu:
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems. APPROX-RANDOM 2020: 26:1-26:20
[c182]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/AndoniB0MW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/AndoniB0MW20
Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff:
Streaming Complexity of SVMs. APPROX-RANDOM 2020: 50:1-50:22
[c181]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/BakshiCW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/BakshiCW20
Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff:
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. APPROX-RANDOM 2020: 64:1-64:22
[c180]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/BravermanGW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/BravermanGW20
Mark Braverman, Sumegha Garg, David P. Woodruff:
The Coin Problem with Applications to Data Streams. FOCS 2020: 318-329
[c179]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/BakshiCW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/BakshiCW20
Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff:
Robust and Sample Optimal Algorithms for PSD Low Rank Approximation. FOCS 2020: 506-516
[c178]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/BravermanDMMUWZ20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/BravermanDMMUWZ20
Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou:
Near Optimal Linear Algebra in the Online and Sliding Window Models. FOCS 2020: 517-528
[c177]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/JayaramWZ20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/JayaramWZ20
Rajesh Jayaram, David P. Woodruff, Qiuyi Zhang:
Span Recovery for Deep Neural Networks with Applications to Input Obfuscation. ICLR 2020
[c176]
- view
  - electronic edition @ openreview.net (open access)
  - details & citations
- export record
  dblp key:
  - conf/iclr/JiangLLRW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/iclr/JiangLLRW20
Tanqiu Jiang, Yi Li, Honghao Lin, Yisong Ruan, David P. Woodruff:
Learning-Augmented Data Stream Algorithms. ICLR 2020
[c175]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/LiW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/LiW20
Yi Li, David P. Woodruff:
Input-Sparsity Low Rank Approximation in Schatten Norm. ICML 2020: 6001-6009
[c174]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/WoodruffZ20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/WoodruffZ20
David P. Woodruff, Amir Zandieh:
Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling. ICML 2020: 10324-10333
[c173]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/innovations/FernandezW020
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/FernandezW020
Manuel Fernandez, David P. Woodruff, Taisuke Yasuda:
Graph Spanners in the Message-Passing Model. ITCS 2020: 77:1-77:18
[c172]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/innovations/GoldwasserGMW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/GoldwasserGMW20
Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff:
Pseudo-Deterministic Streaming. ITCS 2020: 79:1-79:25
[c171]
- view
  - electronic edition @ neurips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/CohenPW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/CohenPW20
Edith Cohen, Rasmus Pagh, David P. Woodruff:
WOR and p's: Sketches for ℓ_p-Sampling Without Replacement. NeurIPS 2020
[c170]
- view
  - electronic edition @ neurips.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/nips/HoangHPW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/HoangHPW20
Quang Minh Hoang, Nghia Hoang, Hai Pham, David P. Woodruff:
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes. NeurIPS 2020
[c169]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/Ben-EliezerJWY20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/Ben-EliezerJWY20
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev:
A Framework for Adversarially Robust Streaming Algorithms. PODS 2020: 63-80
[c168]
- view
  authority control:
- export record
  dblp key:
  - conf/sigecom/MandalSW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/sigecom/MandalSW20
Debmalya Mandal, Nisarg Shah, David P. Woodruff:
Optimal Communication-Distortion Tradeoff in Voting. EC 2020: 795-813
[c167]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/AhleKKPVWZ20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/AhleKKPVWZ20
Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh:
Oblivious Sketching of High-Degree Polynomial Kernels. SODA 2020: 141-160
[c166]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/LiWW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/LiWW20
Yi Li, Ruosong Wang, David P. Woodruff:
Tight Bounds for the Subspace Sketch Problem with Applications. SODA 2020: 1655-1674
[c165]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/VempalaWW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/VempalaWW20
Santosh S. Vempala, Ruosong Wang, David P. Woodruff:
The Communication Complexity of Optimization. SODA 2020: 1733-1752
[c164]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/MahabadiRWZ20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/MahabadiRWZ20
Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou:
Non-adaptive adaptive sampling on turnstile streams. STOC 2020: 1251-1264
[c163]
- view
  authority control:
- export record
  dblp key:
  - conf/www/RashtchianSW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/www/RashtchianSW20
Cyrus Rashtchian, Aneesh Sharma, David P. Woodruff:
LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew. WWW 2020: 2998-3004
2019
[c162]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/aaai/ShiW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/aaai/ShiW19
Xiaofei Shi, David P. Woodruff:
Sublinear Time Numerical Linear Algebra for Structured Matrices. AAAI 2019: 4918-4925
[c161]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/aistats/HainlineJLW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/aistats/HainlineJLW19
John Hainline, Brendan Juba, Hai S. Le, David P. Woodruff:
Conditional Sparse $L_p$-norm Regression With Optimal Probability. AISTATS 2019: 1042-1050
[c160]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/FernandezW019
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/FernandezW019
Manuel Fernandez, David P. Woodruff, Taisuke Yasuda:
The Query Complexity of Mastermind with l_p Distances. APPROX-RANDOM 2019: 1:1-1:11
[c159]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/JayaramW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/JayaramW19
Rajesh Jayaram, David P. Woodruff:
Towards Optimal Moment Estimation in Streaming and Distributed Models. APPROX-RANDOM 2019: 29:1-29:21
[c158]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/colt/BakshiJW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/colt/BakshiJW19
Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff:
Learning Two Layer Rectified Neural Networks in Polynomial Time. COLT 2019: 195-268
[c157]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/colt/0002D0W19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/colt/0002D0W19
Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff:
Faster Algorithms for High-Dimensional Robust Covariance Estimation. COLT 2019: 727-757
[c156]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/colt/IndykVWW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/colt/IndykVWW19
Piotr Indyk, Ali Vakilian, Tal Wagner, David P. Woodruff:
Sample-Optimal Low-Rank Approximation of Distance Matrices. COLT 2019: 1723-1751
[c155]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/compgeom/BravermanCKWY19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/compgeom/BravermanCKWY19
Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang:
The One-Way Communication Complexity of Dynamic Time Warping Distance. SoCG 2019: 16:1-16:15
[c154]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/gi/MunteanuSSW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/gi/MunteanuSSW19
Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff:
On Coresets for Logistic Regression. GI-Jahrestagung 2019: 267-268
[c153]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/AwasthiBBWW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/AwasthiBBWW19
Pranjal Awasthi, Ainesh Bakshi, Maria-Florina Balcan, Colin White, David P. Woodruff:
Robust Communication-Optimal Distributed Clustering Algorithms. ICALP 2019: 18:1-18:16
[c152]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/SunWYZ19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/SunWYZ19
Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang:
Querying a Matrix Through Matrix-Vector Products. ICALP 2019: 94:1-94:16
[c151]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/WoodruffY19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/WoodruffY19
David P. Woodruff, Guang Yang:
Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. ICALP 2019: 97:1-97:14
[c150]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/ClarksonWW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/ClarksonWW19
Kenneth L. Clarkson, Ruosong Wang, David P. Woodruff:
Dimensionality Reduction for Tukey Regression. ICML 2019: 1262-1271
[c149]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/0001PRW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/0001PRW19
Ravi Kumar, Rina Panigrahy, Ali Rahimi, David P. Woodruff:
Faster Algorithms for Binary Matrix Factorization. ICML 2019: 3551-3559
[c148]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/0002WF19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/0002WF19
Taisuke Yasuda, David P. Woodruff, Manuel Fernandez:
Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering. ICML 2019: 7055-7063
[c147]
- view
- export record
  dblp key:
  - conf/nips/DiaoSWY19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/DiaoSWY19
Huaian Diao, Zhao Song, David P. Woodruff, Xin Yang:
Total Least Squares Regression in Input Sparsity Time. NeurIPS 2019: 2478-2489
[c146]
- view
- export record
  dblp key:
  - conf/nips/BanWZ19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/BanWZ19
Frank Ban, David P. Woodruff, Qiuyi (Richard) Zhang:
Regularized Weighted Low Rank Approximation. NeurIPS 2019: 4061-4071
[c145]
- view
- export record
  dblp key:
  - conf/nips/DiaoJSSW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/DiaoJSSW19
Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, David P. Woodruff:
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation. NeurIPS 2019: 4739-4750
[c144]
- view
- export record
  dblp key:
  - conf/nips/SongWZ19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/SongWZ19
Zhao Song, David P. Woodruff, Peilin Zhong:
Towards a Zero-One Law for Column Subset Selection. NeurIPS 2019: 6120-6131
[c143]
- view
- export record
  dblp key:
  - conf/nips/MandalP0W19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/MandalP0W19
Debmalya Mandal, Ariel D. Procaccia, Nisarg Shah, David P. Woodruff:
Efficient and Thrifty Voting by Any Means Necessary. NeurIPS 2019: 7178-7189
[c142]
- view
- export record
  dblp key:
  - conf/nips/MeisterSW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/MeisterSW19
Michela Meister, Tamás Sarlós, David P. Woodruff:
Tight Dimensionality Reduction for Sketching Low Degree Polynomial Kernels. NeurIPS 2019: 9470-9481
[c141]
- view
- export record
  dblp key:
  - conf/nips/SongWZ19a
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/SongWZ19a
Zhao Song, David P. Woodruff, Peilin Zhong:
Average Case Column Subset Selection for Entrywise 퓁₁-Norm Loss. NeurIPS 2019: 10111-10121
[c140]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/JayaramSTW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/JayaramSTW19
Rajesh Jayaram, Gokarna Sharma, Srikanta Tirthapura, David P. Woodruff:
Weighted Reservoir Sampling from Distributed Streams. PODS 2019: 218-235
[c139]
- view
  - electronic edition @ springer.com (open access)
  - details & citations
- export record
  dblp key:
  - conf/recomb/KockanZDKKWS19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/recomb/KockanZDKKWS19
Can Kockan, Kaiyuan Zhu, Natnatee Dokmai, Nikolai Karpov, M. Oguzhan Külekci, David P. Woodruff, Süleyman Cenk Sahinalp:
Sketching Algorithms for Genomic Data Analysis and Querying in a Secure Enclave. RECOMB 2019: 302-304
[c138]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/BalcanLW019
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/BalcanLW019
Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang:
Testing Matrix Rank, Optimally. SODA 2019: 727-746
[c137]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/BanBBKLW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/BanBBKLW19
Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff:
A PTAS for ℓp-Low Rank Approximation. SODA 2019: 747-766
[c136]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/WangW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/WangW19
Ruosong Wang, David P. Woodruff:
Tight Bounds for ℓp Oblivious Subspace Embeddings. SODA 2019: 1825-1843
[c135]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/SongWZ19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/SongWZ19
Zhao Song, David P. Woodruff, Peilin Zhong:
Relative Error Tensor Low Rank Approximation. SODA 2019: 2772-2789
2018
[c134]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/aistats/DiaoSSW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/aistats/DiaoSSW18
Huaian Diao, Zhao Song, Wen Sun, David P. Woodruff:
Sketching for Kronecker Product Regression and P-splines. AISTATS 2018: 1299-1308
[c133]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/BravermanGLWZ18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/BravermanGLWZ18
Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou:
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. APPROX-RANDOM 2018: 7:1-7:22
[c132]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/KrishnanMW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/KrishnanMW18
Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff:
On Sketching the q to p Norms. APPROX-RANDOM 2018: 15:1-15:20
[c131]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/0002NW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/0002NW18
Yi Li, Vasileios Nakos, David P. Woodruff:
On Low-Risk Heavy Hitters and Sparse Recovery Schemes. APPROX-RANDOM 2018: 19:1-19:13
[c130]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/JayaramW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/JayaramW18
Rajesh Jayaram, David P. Woodruff:
Perfect Lp Sampling in a Data Stream. FOCS 2018: 544-555
[c129]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/SohlerW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/SohlerW18
Christian Sohler, David P. Woodruff:
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension. FOCS 2018: 802-813
[c128]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/BravermanVWY18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/BravermanVWY18
Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang:
Revisiting Frequency Moment Estimation in Random Order Streams. ICALP 2018: 25:1-25:14
[c127]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/GangulyW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/GangulyW18
Sumit Ganguly, David P. Woodruff:
High Probability Frequency Moment Sketches. ICALP 2018: 58:1-58:15
[c126]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/NakosSW018
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/NakosSW018
Vasileios Nakos, Xiaofei Shi, David P. Woodruff, Hongyang Zhang:
Improved Algorithms for Adaptive Compressed Sensing. ICALP 2018: 90:1-90:14
[c125]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/BravermanCKLWY18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/BravermanCKLWY18
Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer, Yi Li, David P. Woodruff, Lin F. Yang:
Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order. ICML 2018: 648-657
[c124]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/CormodeDW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/CormodeDW18
Graham Cormode, Charlie Dickens, David P. Woodruff:
Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski p-Norms. ICML 2018: 1048-1056
[c123]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/innovations/BalcanLWZ18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/BalcanLWZ18
Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, Hongyang Zhang:
Matrix Completion and Related Problems via Strong Duality. ITCS 2018: 5:1-5:22
[c122]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/innovations/MuscoNSUW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/MuscoNSUW18
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff:
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. ITCS 2018: 8:1-8:21
[c121]
- view
  authority control:
- export record
  dblp key:
  - conf/kdd/DahiyaKW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/kdd/DahiyaKW18
Yogesh Dahiya, Dimitris Konomis, David P. Woodruff:
An Empirical Evaluation of Sketching for Numerical Linear Algebra. KDD 2018: 1292-1300
[c120]
- view
- export record
  dblp key:
  - conf/nips/BakshiW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/BakshiW18
Ainesh Bakshi, David P. Woodruff:
Sublinear Time Low-Rank Approximation of Distance Matrices. NeurIPS 2018: 3786-3796
[c119]
- view
- export record
  dblp key:
  - conf/nips/MunteanuSSW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/MunteanuSSW18
Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff:
On Coresets for Logistic Regression. NeurIPS 2018: 6562-6571
[c118]
- view
- export record
  dblp key:
  - conf/nips/LevinSW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/LevinSW18
Roie Levin, Anish Prasad Sevekari, David P. Woodruff:
Robust Subspace Approximation in a Stream. NeurIPS 2018: 10706-10716
[c117]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/JayaramW18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/JayaramW18
Rajesh Jayaram, David P. Woodruff:
Data Streams with Bounded Deletions. PODS 2018: 341-354
[c116]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/Woodruff018
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/Woodruff018
David P. Woodruff, Qin Zhang:
Distributed Statistical Estimation of Matrix Products with Applications. PODS 2018: 383-394
2017
[c115]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/AvronCW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/AvronCW17
Haim Avron, Kenneth L. Clarkson, David P. Woodruff:
Sharper Bounds for Regularized Data Fitting. APPROX-RANDOM 2017: 27:1-27:22
[c114]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/esa/Woodruff17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/esa/Woodruff17
David P. Woodruff:
Sketching for Geometric Problems (Invited Talk). ESA 2017: 1:1-1:5
[c113]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/KapralovNPWWY17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/KapralovNPWWY17
Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh:
Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams. FOCS 2017: 475-486
[c112]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/MuscoW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/MuscoW17
Cameron Musco, David P. Woodruff:
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. FOCS 2017: 672-683
[c111]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/PriceSW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/PriceSW17
Eric Price, Zhao Song, David P. Woodruff:
Fast Regression with an $ell_infty$ Guarantee. ICALP 2017: 59:1-59:14
[c110]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/0002W17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/0002W17
Yi Li, David P. Woodruff:
Embeddings of Schatten Norms with Applications to Data Streams. ICALP 2017: 60:1-60:14
[c109]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/ChierichettiG0L17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/ChierichettiG0L17
Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, David P. Woodruff:
Algorithms for $\ell_p$ Low-Rank Approximation. ICML 2017: 806-814
[c108]
- view
- export record
  dblp key:
  - conf/nips/LiHW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/LiHW17
Xingguo Li, Jarvis D. Haupt, David P. Woodruff:
Near Optimal Sketching of Low-Rank Tensor Regression. NIPS 2017: 3466-3476
[c107]
- view
- export record
  dblp key:
  - conf/nips/MuscoW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/MuscoW17
Cameron Musco, David P. Woodruff:
Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? NIPS 2017: 4435-4445
[c106]
- view
- export record
  dblp key:
  - conf/nips/BringmannKW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/BringmannKW17
Karl Bringmann, Pavel Kolev, David P. Woodruff:
Approximation Algorithms for l₀-Low Rank Approximation. NIPS 2017: 6648-6659
[c105]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/BravermanCINWW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/BravermanCINWW17
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff:
BPTree: An ℓ₂ Heavy Hitters Algorithm Using Constant Memory. PODS 2017: 361-376
[c104]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/VempalaW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/VempalaW17
Santosh S. Vempala, David P. Woodruff:
Adaptive Matrix Vector Product. SODA 2017: 2044-2060
[c103]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/ClarksonW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/ClarksonW17
Kenneth L. Clarkson, David P. Woodruff:
Low-Rank PSD Approximation in Input-Sparsity Time. SODA 2017: 2061-2072
[c102]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/SongWZ17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/SongWZ17
Zhao Song, David P. Woodruff, Peilin Zhong:
Low rank approximation with entrywise l₁-norm error. STOC 2017: 688-701
2016
[c101]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/LiW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/LiW16
Yi Li, David P. Woodruff:
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. APPROX-RANDOM 2016: 39:1-39:11
[c100]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/coco/AiHLW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/coco/AiHLW16
Yuqing Ai, Wei Hu, Yi Li, David P. Woodruff:
New Characterizations in Turnstile Streams with Applications. CCC 2016: 20:1-20:22
[c99]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/esa/CrouchMVW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/esa/CrouchMVW16
Michael S. Crouch, Andrew McGregor, Gregory Valiant, David P. Woodruff:
Stochastic Streams: Sample Complexity vs. Space Complexity. ESA 2016: 32:1-32:15
[c98]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icalp/CohenNW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/CohenNW16
Michael B. Cohen, Jelani Nelson, David P. Woodruff:
Optimal Approximate Matrix Product in Terms of Stable Rank. ICALP 2016: 11:1-11:14
[c97]
- view
  authority control:
- export record
  dblp key:
  - conf/icde/WoodruffZ16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icde/WoodruffZ16
David P. Woodruff, Peilin Zhong:
Distributed low rank approximation of implicit functions of a matrix. ICDE 2016: 847-858
[c96]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/icdt/Woodruff16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icdt/Woodruff16
David P. Woodruff:
New Algorithms for Heavy Hitters in Data Streams (Invited Talk). ICDT 2016: 4:1-4:12
[c95]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/KapralovPW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/KapralovPW16
Michael Kapralov, Vamsi K. Potluru, David P. Woodruff:
How to Fake Multiply by a Gaussian Matrix. ICML 2016: 2101-2110
[c94]
- view
  authority control:
- export record
  dblp key:
  - conf/innovations/AndoniCKQWZ16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/AndoniCKQWZ16
Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang:
On Sketching Quadratic Forms. ITCS 2016: 311-319
[c93]
- view
  authority control:
- export record
  dblp key:
  - conf/kdd/BalcanLSW016
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/kdd/BalcanLSW016
Maria-Florina Balcan, Yingyu Liang, Le Song, David P. Woodruff, Bo Xie:
Communication Efficient Distributed Kernel Principal Component Analysis. KDD 2016: 725-734
[c92]
- view
- export record
  dblp key:
  - conf/nips/SongWZ16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/SongWZ16
Zhao Song, David P. Woodruff, Huan Zhang:
Sublinear Time Orthogonal Tensor Decomposition. NIPS 2016: 793-801
[c91]
- view
- export record
  dblp key:
  - conf/nips/ChenSWZ16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/ChenSWZ16
Jiecao Chen, He Sun, David P. Woodruff, Qin Zhang:
Communication-Optimal Distributed Clustering. NIPS 2016: 3720-3728
[c90]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/BravermanCWY16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/BravermanCWY16
Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff, Lin F. Yang:
Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors. PODS 2016: 261-276
[c89]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/BhattacharyyaDW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/BhattacharyyaDW16
Arnab Bhattacharyya, Palash Dey, David P. Woodruff:
An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems. PODS 2016: 385-400
[c88]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/BackursIRW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/BackursIRW16
Arturs Backurs, Piotr Indyk, Ilya P. Razenshteyn, David P. Woodruff:
Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching. SODA 2016: 318-337
[c87]
- view
  authority control:
- export record
  dblp key:
  - conf/spaa/EsfandiariHW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/spaa/EsfandiariHW16
Hossein Esfandiari, MohammadTaghi Hajiaghayi, David P. Woodruff:
Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond. SPAA 2016: 397-399
[c86]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/BoutsidisWZ16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/BoutsidisWZ16
Christos Boutsidis, David P. Woodruff, Peilin Zhong:
Optimal principal component analysis in distributed and streaming models. STOC 2016: 236-249
[c85]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/RazenshteynSW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/RazenshteynSW16
Ilya P. Razenshteyn, Zhao Song, David P. Woodruff:
Weighted low rank approximations with provable guarantees. STOC 2016: 250-263
[c84]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/LiW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/LiW16
Yi Li, David P. Woodruff:
On approximating functions of the singular values in a stream. STOC 2016: 726-739
[c83]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/BravermanCIW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/BravermanCIW16
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff:
Beating CountSketch for heavy hitters in insertion streams. STOC 2016: 740-753
[c82]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/BravermanGMNW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/BravermanGMNW16
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff:
Communication lower bounds for statistical estimation problems via a distributed data processing inequality. STOC 2016: 1011-1020
2015
[c81]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/SunW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/SunW15
Xiaoming Sun, David P. Woodruff:
Tight Bounds for Graph Problems in Insertion Streams. APPROX-RANDOM 2015: 435-448
[c80]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/ClarksonW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/ClarksonW15
Kenneth L. Clarkson, David P. Woodruff:
Input Sparsity and Hardness for Robust Subspace Approximation. FOCS 2015: 310-329
[c79]
- view
  authority control:
- export record
  dblp key:
  - conf/icalp/MolinaroWY15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/MolinaroWY15
Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev:
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity. ICALP (1) 2015: 960-972
[c78]
- view
  authority control:
- export record
  dblp key:
  - conf/icalp/WeinsteinW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/WeinsteinW15
Omri Weinstein, David P. Woodruff:
The Simultaneous Communication of Disjointness with Applications to Data Streams. ICALP (1) 2015: 1082-1093
[c77]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/GuchtWWZ15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/GuchtWWZ15
Dirk Van Gucht, Ryan Williams, David P. Woodruff, Qin Zhang:
The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication. PODS 2015: 199-212
[c76]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/ClarksonW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/ClarksonW15
Kenneth L. Clarkson, David P. Woodruff:
Sketching for M-Estimators: A Unified Approach to Robust Regression. SODA 2015: 921-939
2014
[c75]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/approx/BrodyCKWY14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/BrodyCKWY14
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev:
Certifying Equality With Limited Interaction. APPROX-RANDOM 2014: 545-581
[c74]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/colt/KannanVW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/colt/KannanVW14
Ravi Kannan, Santosh S. Vempala, David P. Woodruff:
Principal Component Analysis and Higher Correlations for Distributed Data. COLT 2014: 1040-1057
[c73]
- view
  authority control:
- export record
  dblp key:
  - conf/kdd/LiWW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/kdd/LiWW14
Yi Li, Zhengyu Wang, David P. Woodruff:
Improved testing of low rank matrices. KDD 2014: 691-700
[c72]
- view
- export record
  dblp key:
  - conf/nips/Woodruff14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/Woodruff14
David P. Woodruff:
Low Rank Approximation Lower Bounds in Row-Update Streams. NIPS 2014: 1781-1789
[c71]
- view
- export record
  dblp key:
  - conf/nips/AvronNW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/AvronNW14
Haim Avron, Huy L. Nguyen, David P. Woodruff:
Subspace Embeddings for the Polynomial Kernel. NIPS 2014: 2258-2266
[c70]
- view
- export record
  dblp key:
  - conf/nips/LiangBKW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/LiangBKW14
Yingyu Liang, Maria-Florina Balcan, Vandana Kanchanapally, David P. Woodruff:
Improved Distributed Principal Component Analysis. NIPS 2014: 3113-3121
[c69]
- view
  authority control:
- export record
  dblp key:
  - conf/podc/BrodyCKWY14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/podc/BrodyCKWY14
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P. Woodruff, Grigory Yaroslavtsev:
Beyond set disjointness: the communication complexity of finding the intersection. PODC 2014: 106-113
[c68]
- view
  authority control:
- export record
  dblp key:
  - conf/podc/KapralovW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/podc/KapralovW14
Michael Kapralov, David P. Woodruff:
Spanners and sparsifiers in dynamic streams. PODC 2014: 272-281
[c67]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/PaghSW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/PaghSW14
Rasmus Pagh, Morten Stöckel, David P. Woodruff:
Is min-wise hashing optimal for summarizing set intersection? PODS 2014: 109-120
[c66]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/WoodruffZ14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/WoodruffZ14
David P. Woodruff, Qin Zhang:
An Optimal Lower Bound for Distinct Elements in the Message Passing Model. SODA 2014: 718-733
[c65]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/LiNW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/LiNW14
Yi Li, Huy L. Nguyen, David P. Woodruff:
On Sketching Matrix Norms and the Top Singular Vector. SODA 2014: 1562-1581
[c64]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/LiNW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/LiNW14
Yi Li, Huy L. Nguyen, David P. Woodruff:
Turnstile streaming algorithms might as well be linear sketches. STOC 2014: 174-183
[c63]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/BoutsidisW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/BoutsidisW14
Christos Boutsidis, David P. Woodruff:
Optimal CUR matrix decompositions. STOC 2014: 353-362
[c62]
- view
  authority control:
- export record
  dblp key:
  - conf/wdag/LiSWW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/wdag/LiSWW14
Yi Li, Xiaoming Sun, Chengu Wang, David P. Woodruff:
On the Communication Complexity of Linear Algebraic Problems in the Message Passing Model. DISC 2014: 499-513
2013
[c61]
- view
  authority control:
- export record
  dblp key:
  - conf/approx/LiW13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/LiW13
Yi Li, David P. Woodruff:
A Tight Lower Bound for High Frequency Moment Estimation with Small Error. APPROX-RANDOM 2013: 623-638
[c60]
- view
  - electronic edition @ mlr.press (open access)
  - details & citations
- export record
  dblp key:
  - conf/colt/WoodruffZ13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/colt/WoodruffZ13
David P. Woodruff, Qin Zhang:
Subspace Embeddings and $\ell_p$-Regression Using Exponential Random Variables. COLT 2013: 546-567
[c59]
- view
- export record
  dblp key:
  - conf/nips/AvronSW13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/nips/AvronSW13
Haim Avron, Vikas Sindhwani, David P. Woodruff:
Sketching Structured Matrices for Faster Nonlinear Regression. NIPS 2013: 2994-3002
[c58]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/ClarksonDMMMW13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/ClarksonDMMMW13
Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff:
The Fast Cauchy Transform and Faster Robust Linear Regression. SODA 2013: 466-477
[c57]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/PriceW13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/PriceW13
Eric Price, David P. Woodruff:
Lower Bounds for Adaptive Sparse Recovery. SODA 2013: 652-663
[c56]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/MolinaroWY13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/MolinaroWY13
Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev:
Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching. SODA 2013: 1738-1756
[c55]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/ClarksonW13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/ClarksonW13
Kenneth L. Clarkson, David P. Woodruff:
Low rank approximation and regression in input sparsity time. STOC 2013: 81-90
[c54]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/HardtW13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/HardtW13
Moritz Hardt, David P. Woodruff:
How robust are linear sketches to adaptive inputs? STOC 2013: 121-130
[c53]
- view
  authority control:
- export record
  dblp key:
  - conf/wdag/WoodruffZ13
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/wdag/WoodruffZ13
David P. Woodruff, Qin Zhang:
When Distributed Computation Is Communication Expensive. DISC 2013: 16-30
2012
[c52]
- view
  authority control:
- export record
  dblp key:
  - conf/approx/NelsonNW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/NelsonNW12
Jelani Nelson, Huy L. Nguyên, David P. Woodruff:
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation. APPROX-RANDOM 2012: 627-638
[c51]
- view
  authority control:
- export record
  dblp key:
  - conf/icde/TirthapuraW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icde/TirthapuraW12
Srikanta Tirthapura, David P. Woodruff:
A General Method for Estimating Correlated Aggregates over a Data Stream. ICDE 2012: 162-173
[c50]
- view
  - electronic edition @ icml.cc (open access)
  - details & citations
- export record
  dblp key:
  - conf/icml/MahoneyDMW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icml/MahoneyDMW12
Michael W. Mahoney, Petros Drineas, Malik Magdon-Ismail, David P. Woodruff:
Fast approximation of matrix coherence and statistical leverage. ICML 2012
[c49]
- view
  authority control:
- export record
  dblp key:
  - conf/isit/PriceW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/isit/PriceW12
Eric Price, David P. Woodruff:
Applications of the Shannon-Hartley theorem to data streams and sparse recovery. ISIT 2012: 2446-2450
[c48]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/McGregorPTW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/McGregorPTW12
Andrew McGregor, A. Pavan, Srikanta Tirthapura, David P. Woodruff:
Space-efficient estimation of statistics over sub-sampled streams. PODS 2012: 273-282
[c47]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/TirthapuraW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/TirthapuraW12
Srikanta Tirthapura, David P. Woodruff:
Rectangle-efficient aggregation in spatial data streams. PODS 2012: 283-294
[c46]
- view
  authority control:
- export record
  dblp key:
  - conf/ssp/GilbertHSWW12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/ssp/GilbertHSWW12
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
[c45]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/WoodruffZ12
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/WoodruffZ12
David P. Woodruff, Qin Zhang:
Tight bounds for distributed functional monitoring. STOC 2012: 941-960
2011
[c44]
- view
  authority control:
- export record
  dblp key:
  - conf/approx/BrodyW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/BrodyW11
Joshua Brody, David P. Woodruff:
Streaming Algorithms with One-Sided Estimation. APPROX-RANDOM 2011: 436-447
[c43]
- view
  authority control:
- export record
  dblp key:
  - conf/esa/KleinPSW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/esa/KleinPSW11
Rolf Klein, Rainer Penninger, Christian Sohler, David P. Woodruff:
Tolerant Algorithms. ESA 2011: 736-747
[c42]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/IndykPW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/IndykPW11
Piotr Indyk, Eric Price, David P. Woodruff:
On the Power of Adaptivity in Sparse Recovery. FOCS 2011: 285-294
[c41]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/PriceW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/PriceW11
Eric Price, David P. Woodruff:
(1 + eps)-Approximate Sparse Recovery. FOCS 2011: 295-304
[c40]
- view
  authority control:
- export record
  dblp key:
  - conf/icalp/BermanBGRWY11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/BermanBGRWY11
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev:
Steiner Transitive-Closure Spanners of Low-Dimensional Posets. ICALP (1) 2011: 760-772
[c39]
- view
  - electronic edition @ tsinghua.edu.cn
  - details & citations
- export record
  dblp key:
  - conf/innovations/BhattacharyyaIWX11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/innovations/BhattacharyyaIWX11
Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff, Ning Xie:
The Complexity of Linear Dependence Problems in Vector Spaces. ICS 2011: 496-508
[c38]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/JayramW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/JayramW11
T. S. Jayram, David P. Woodruff:
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error. SODA 2011: 1-10
[c37]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/Woodruff11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/Woodruff11
David P. Woodruff:
Near-optimal private approximation protocols via a black box transformation. STOC 2011: 735-744
[c36]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/KaneNPW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/KaneNPW11
Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff:
Fast moment estimation in data streams in optimal space. STOC 2011: 745-754
[c35]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/SohlerW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/SohlerW11
Christian Sohler, David P. Woodruff:
Subspace embeddings for the L₁-norm with applications. STOC 2011: 755-764
[c34]
- view
  authority control:
- export record
  dblp key:
  - conf/wdag/TirthapuraW11
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/wdag/TirthapuraW11
Srikanta Tirthapura, David P. Woodruff:
Optimal Random Sampling from Distributed Streams Revisited. DISC 2011: 283-297
2010
[c33]
- view
  authority control:
- export record
  dblp key:
  - conf/approx/BhattacharyyaGJJRW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/BhattacharyyaGJJRW10
Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. APPROX-RANDOM 2010: 448-461
[c32]
- view
  authority control:
- export record
  dblp key:
  - conf/approx/Woodruff10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/Woodruff10
David P. Woodruff:
A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes over Any Field. APPROX-RANDOM 2010: 766-779
[c31]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/ClarksonHW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/ClarksonHW10
Kenneth L. Clarkson, Elad Hazan, David P. Woodruff:
Sublinear Optimization for Machine Learning. FOCS 2010: 449-457
[c30]
- view
  authority control:
- export record
  dblp key:
  - conf/icalp/Woodruff10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/Woodruff10
David P. Woodruff:
Additive Spanners in Nearly Quadratic Time. ICALP (1) 2010: 463-474
[c29]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/KaneNW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/KaneNW10
Daniel M. Kane, Jelani Nelson, David P. Woodruff:
An optimal algorithm for the distinct elements problem. PODS 2010: 41-52
[c28]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/NelsonW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/NelsonW10
Jelani Nelson, David P. Woodruff:
Fast Manhattan sketches in data streams. PODS 2010: 99-110
[c27]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/FeldmanMSW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/FeldmanMSW10
Dan Feldman, Morteza Monemizadeh, Christian Sohler, David P. Woodruff:
Coresets and Sketches for High Dimensional Subspace Approximation Problems. SODA 2010: 630-649
[c26]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/MonemizadehW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/MonemizadehW10
Morteza Monemizadeh, David P. Woodruff:
1-Pass Relative-Error L_p-Sampling with Applications. SODA 2010: 1143-1160
[c25]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/KaneNW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/KaneNW10
Daniel M. Kane, Jelani Nelson, David P. Woodruff:
On the Exact Space Complexity of Sketching and Streaming Small Norms. SODA 2010: 1161-1178
[c24]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/soda/BaIPW10
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/BaIPW10
Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff:
Lower Bounds for Sparse Recovery. SODA 2010: 1190-1197
2009
[c23]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/AndoniBIW09
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/AndoniBIW09
Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff:
Efficient Sketches for Earth-Mover Distance, with Applications. FOCS 2009: 324-330
[c22]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/JayramW09
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/JayramW09
T. S. Jayram, David P. Woodruff:
The Data Stream Space Complexity of Cascaded Norms. FOCS 2009: 765-774
[c21]
- view
  authority control:
- export record
  dblp key:
  - conf/icdt/Woodruff09
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icdt/Woodruff09
David P. Woodruff:
The average-case complexity of counting distinct elements. ICDT 2009: 284-295
[c20]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/BhattacharyyaGJRW09
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/BhattacharyyaGJRW09
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-closure spanners. SODA 2009: 932-941
[c19]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/ClarksonW09
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/ClarksonW09
Kenneth L. Clarkson, David P. Woodruff:
Numerical linear algebra in the streaming model. STOC 2009: 205-214
2008
[c18]
- view
  authority control:
- export record
  dblp key:
  - conf/approx/Woodruff08
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/Woodruff08
David P. Woodruff:
Corruption and Recovery-Efficient Locally Decodable Codes. APPROX-RANDOM 2008: 584-595
[c17]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/EvfimievskiFW08
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/EvfimievskiFW08
Alexandre V. Evfimievski, Ronald Fagin, David P. Woodruff:
Epistemic privacy. PODS 2008: 171-180
2007
[c16]
- view
  authority control:
- export record
  dblp key:
  - conf/eurocrypt/Woodruff07
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/eurocrypt/Woodruff07
David P. Woodruff:
Revisiting the Efficiency of Malicious Two-Party Computation. EUROCRYPT 2007: 79-96
[c15]
- view
  - electronic edition @ acm.org
  - details & citations
- export record
  dblp key:
  - conf/soda/SunW07
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/SunW07
Xiaoming Sun, David P. Woodruff:
The communication and streaming complexity of computing the longest common and increasing subsequences. SODA 2007: 336-345
2006
[c14]
- view
  authority control:
- export record
  dblp key:
  - conf/approx/Woodruff06
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/approx/Woodruff06
David P. Woodruff:
Better Approximations for the Minimum Common Integer Partition Problem. APPROX-RANDOM 2006: 248-259
[c13]
- view
  authority control:
- export record
  dblp key:
  - conf/crypto/RamzanW06
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/crypto/RamzanW06
Zulfikar Ramzan, David P. Woodruff:
Fast Algorithms for the Free Riders Problem in Broadcast Encryption. CRYPTO 2006: 308-325
[c12]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/GentryRW06
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/GentryRW06
Craig Gentry, Zulfikar Ramzan, David P. Woodruff:
Explicit Exclusive Set Systems with Applications to Broadcast Encryption. FOCS 2006: 27-38
[c11]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/Woodruff06
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/Woodruff06
David P. Woodruff:
Lower Bounds for Additive Spanners, Emulators, and More. FOCS 2006: 389-398
[c10]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - conf/tcc/IndykW06
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/tcc/IndykW06
Piotr Indyk, David P. Woodruff:
Polylogarithmic Private Approximations and Efficient Matching. TCC 2006: 245-264
2005
[c9]
- view
  authority control:
- export record
  dblp key:
  - conf/coco/WoodruffY05
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/coco/WoodruffY05
David P. Woodruff, Sergey Yekhanin:
A Geometric Approach to Information-Theoretic Private Information Retrieval. CCC 2005: 275-284
[c8]
- view
  authority control:
- export record
  dblp key:
  - conf/eurocrypt/DijkGPRSSW05
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/eurocrypt/DijkGPRSSW05
Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, David P. Woodruff:
Practical Cryptography in High Dimensional Tori. EUROCRYPT 2005: 234-250
[c7]
- view
  authority control:
- export record
  dblp key:
  - conf/stoc/IndykW05
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/stoc/IndykW05
Piotr Indyk, David P. Woodruff:
Optimal approximations of the frequency moments of data streams. STOC 2005: 202-208
2004
[c6]
- view
  authority control:
- export record
  dblp key:
  - conf/ccs/WoodruffS04
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/ccs/WoodruffS04
David P. Woodruff, Jessica Staddon:
Private inference control. CCS 2004: 188-197
[c5]
- view
  authority control:
- export record
  dblp key:
  - conf/crypto/DijkW04
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/crypto/DijkW04
Marten van Dijk, David P. Woodruff:
Asymptotically Optimal Communication for Torus-Based Cryptography. CRYPTO 2004: 157-178
[c4]
- view
  authority control:
- export record
  dblp key:
  - conf/pods/ZhouW04
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/pods/ZhouW04
Hanson Zhou, David P. Woodruff:
Clustering via Matrix Powering. PODS 2004: 136-142
[c3]
- view
  - electronic edition @ acm.org
  - details & citations
- export record
  dblp key:
  - conf/soda/Woodruff04
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/Woodruff04
David P. Woodruff:
Optimal space lower bounds for all frequency moments. SODA 2004: 167-175
2003
[c2]
- view
  authority control:
- export record
  dblp key:
  - conf/focs/IndykW03
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/focs/IndykW03
Piotr Indyk, David P. Woodruff:
Tight Lower Bounds for the Distinct Elements Problem. FOCS 2003: 283-288
2002
[c1]
- view
  authority control:
- export record
  dblp key:
  - conf/eurocrypt/WoodruffD02
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/eurocrypt/WoodruffD02
David P. Woodruff, Marten van Dijk:
Cryptography in an Unbounded Computational Model. EUROCRYPT 2002: 149-164

Editorship

see FAQ

What is the meaning of the colors in the publication lists?

2024
[e2]
- view
  authority control:
- export record
  dblp key:
  - conf/soda/2024
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/soda/2024
David P. Woodruff:
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024. SIAM 2024, ISBN 978-1-61197-791-2 [contents]
2022
[e1]
- view
- export record
  dblp key:
  - conf/icalp/2022
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/conf/icalp/2022
Mikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff:
49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France. LIPIcs 229, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022, ISBN 978-3-95977-235-8 [contents]

Reference Works

see FAQ

What is the meaning of the colors in the publication lists?

2018
[r2]
- view
  authority control:
- export record
  dblp key:
  - reference/db/Woodruff18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/reference/db/Woodruff18
David P. Woodruff:
Frequency Moments. Encyclopedia of Database Systems (2nd ed.) 2018
2009
[r1]
- view
  authority control:
- export record
  dblp key:
  - reference/db/Woodruff09
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/reference/db/Woodruff09
David P. Woodruff:
Frequency Moments. Encyclopedia of Database Systems 2009: 1169-1170

Informal and Other Publications

see FAQ

What is the meaning of the colors in the publication lists?

2025
[i248]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2501-01801
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2501-01801
David P. Woodruff, Taisuke Yasuda:
John Ellipsoids via Lazy Updates. CoRR abs/2501.01801 (2025)
[i247]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2501-03132
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2501-03132
Zhihao Jia, Qi Pang, Trung Tran, David P. Woodruff, Zhihao Zhang, Wenting Zheng:
Communication Bounds for the Distributed Experts Problem. CoRR abs/2501.03132 (2025)
[i246]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2502-08029
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2502-08029
Raphael A. Meyer, William Swartworth, David P. Woodruff:
Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra. CoRR abs/2502.08029 (2025)
[i245]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2502-19865
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2502-19865
Sandeep Silwal, David P. Woodruff, Qiuyi Zhang:
Beyond Worst-Case Dimensionality Reduction for Sparse Vectors. CoRR abs/2502.19865 (2025)
[i244]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2503-19629
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2503-19629
Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness. CoRR abs/2503.19629 (2025)
[i243]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2504-07237
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2504-07237
David P. Woodruff, Shenghao Xie, Samson Zhou:
Perfect Sampling in Turnstile Streams Beyond Small Moments. CoRR abs/2504.07237 (2025)
[i242]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2504-15292
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2504-15292
Anne Driemel, Morteza Monemizadeh, Eunjin Oh, Frank Staals, David P. Woodruff:
Range Counting Oracles for Geometric Problems. CoRR abs/2504.15292 (2025)
[i241]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2504-16229
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2504-16229
Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff, Samson Zhou:
Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings. CoRR abs/2504.16229 (2025)
[i240]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2504-18394
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2504-18394
Alina Ene, Alessandro Epasto, Vahab Mirrokni, Hoai-An Nguyen, Huy L. Nguyen, David P. Woodruff, Peilin Zhong:
Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures. CoRR abs/2504.18394 (2025)
[i239]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2504-20883
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2504-20883
Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu, Ali Vakilian, David P. Woodruff:
Guessing Efficiently for Constrained Subspace Approximation. CoRR abs/2504.20883 (2025)
[i238]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2504-21175
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2504-21175
Shiyuan Feng, William Swartworth, David P. Woodruff:
Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model. CoRR abs/2504.21175 (2025)
[i237]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2506-05503
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2506-05503
Shiyuan Feng, Ying Feng, George Z. Li, Zhao Song, David P. Woodruff, Lichen Zhang:
On Differential Privacy for Adaptively Solving Search Problems via Sketching. CoRR abs/2506.05503 (2025)
[i236]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2506-07342
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2506-07342
Honghao Lin, Hoai-An Nguyen, David P. Woodruff:
On Sketching Trimmed Statistics. CoRR abs/2506.07342 (2025)
[i235]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2506-22608
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2506-22608
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee, Thanasis Pittas, David P. Woodruff, Samson Zhou:
On Fine-Grained Distinct Element Estimation. CoRR abs/2506.22608 (2025)
[i234]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2507-11484
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2507-11484
N. Efe Çekirge, William Gay, David P. Woodruff:
Multipass Linear Sketches for Geometric LP-Type Problems. CoRR abs/2507.11484 (2025)
[i233]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2508-07067
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2508-07067
Honghao Lin, Hoai-An Nguyen, William Swartworth, David P. Woodruff:
Unbiased Insights: Optimal Streaming Algorithms for ℓ_p Sampling, the Forget Model, and Beyond. CoRR abs/2508.07067 (2025)
[i232]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2509-16180
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2509-16180
Gautam Kamath, Alireza F. Pour, Matthew Regehr, David P. Woodruff:
Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph. CoRR abs/2509.16180 (2025)
[i231]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2509-16801
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2509-16801
Zhao Song, David P. Woodruff, Lichen Zhang:
Sublinear Time Quantum Sensitivity Sampling. CoRR abs/2509.16801 (2025)
2024
[i230]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2401-09278
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2401-09278
Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David P. Woodruff, Elad Hazan:
Adaptive Regret for Bandits Made Possible: Two Queries Suffice. CoRR abs/2401.09278 (2024)
[i229]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2402-17327
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2402-17327
Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, Michael Wunder:
Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond. CoRR abs/2402.17327 (2024)
[i228]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2403-19146
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2403-19146
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, Guanghao Ye:
Improving the Bit Complexity of Communication for Distributed Convex Optimization. CoRR abs/2403.19146 (2024)
[i227]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2403-20283
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2403-20283
Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang:
A New Information Complexity Measure for Multi-pass Streaming with Applications. CoRR abs/2403.20283 (2024)
[i226]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2403-20307
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2403-20307
Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong:
Optimal Communication for Classic Functions in the Coordinator Model and Beyond. CoRR abs/2403.20307 (2024)
[i225]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2406-02431
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2406-02431
David P. Woodruff, Taisuke Yasuda:
Reweighted Solutions for Weighted Low Rank Approximation. CoRR abs/2406.02431 (2024)
[i224]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2406-02432
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2406-02432
David P. Woodruff, Taisuke Yasuda:
Coresets for Multiple ℓ_p Regression. CoRR abs/2406.02432 (2024)
[i223]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2406-02910
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2406-02910
Hossein Esfandiari, Vahab Mirrokni, Praneeth Kacham, David P. Woodruff, Peilin Zhong:
High-Dimensional Geometric Streaming for Nearly Low Rank Data. CoRR abs/2406.02910 (2024)
[i222]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2406-06735
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2406-06735
William Swartworth, David P. Woodruff:
Fast Sampling Based Sketches for Tensors. CoRR abs/2406.06735 (2024)
[i221]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2406-06808
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2406-06808
Ying Feng, Aayush Jain, David P. Woodruff:
Fast White-Box Adversarial Streaming Without a Random Oracle. CoRR abs/2406.06808 (2024)
[i220]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2406-06821
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2406-06821
Rajesh Jayaram, David P. Woodruff, Samson Zhou:
Streaming Algorithms with Few State Changes. CoRR abs/2406.06821 (2024)
[i219]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2406-13231
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2406-13231
Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, Jason Zhang:
Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut. CoRR abs/2406.13231 (2024)
[i218]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2406-17660
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2406-17660
Aashiq Muhamed, Oscar Li, David P. Woodruff, Mona T. Diab, Virginia Smith:
Grass: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients. CoRR abs/2406.17660 (2024)
[i217]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2407-03262
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2407-03262
David P. Woodruff, Taisuke Yasuda:
Nearly Linear Sparsification of ℓ_p Subspace Approximation. CoRR abs/2407.03262 (2024)
[i216]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2407-11959
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2407-11959
Praneeth Kacham, David P. Woodruff:
Faster Algorithms for Schatten-p Low Rank Approximation. CoRR abs/2407.11959 (2024)
[i215]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2408-08494
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2408-08494
Yi Li, Honghao Lin, David P. Woodruff:
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms. CoRR abs/2408.08494 (2024)
[i214]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2409-06453
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2409-06453
Milind Prabhu, David P. Woodruff:
Learning Multiple Secrets in Mastermind. CoRR abs/2409.06453 (2024)
[i213]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2409-16153
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2409-16153
Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou:
A Strong Separation for Adversarially Robust ℓ₀ Estimation for Linear Sketches. CoRR abs/2409.16153 (2024)
[i212]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2410-05462
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2410-05462
Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham, David P. Woodruff:
LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions. CoRR abs/2410.05462 (2024)
[i211]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2411-03227
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2411-03227
William Swartworth, David P. Woodruff:
Tight Sampling Bounds for Eigenvalue Approximation. CoRR abs/2411.03227 (2024)
[i210]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2411-13028
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2411-13028
Hamed Shirzad, Honghao Lin, Ameya Velingker, Balaji Venkatachalam, David P. Woodruff, Danica J. Sutherland:
A Theory for Compressibility of Graph Transformers for Transductive Learning. CoRR abs/2411.13028 (2024)
[i209]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2411-16278
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2411-16278
Hamed Shirzad, Honghao Lin, Balaji Venkatachalam, Ameya Velingker, David P. Woodruff, Danica J. Sutherland:
Even Sparser Graph Transformers. CoRR abs/2411.16278 (2024)
[i208]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2412-01143
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2412-01143
Matthew Ding, Alexandro Garces, Jason Li, Honghao Lin, Jelani Nelson, Vihan Shah, David P. Woodruff:
Space Complexity of Minimum Cut Problems in Single-Pass Streams. CoRR abs/2412.01143 (2024)
[i207]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2412-05807
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2412-05807
David P. Woodruff, Samson Zhou:
Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters. CoRR abs/2412.05807 (2024)
[i206]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2412-06063
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2412-06063
Zhao Song, Ali Vakilian, David P. Woodruff, Samson Zhou:
On Socially Fair Low-Rank Approximation and Column Subset Selection. CoRR abs/2412.06063 (2024)
[i205]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2412-11963
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2412-11963
Praneeth Kacham, David P. Woodruff:
Approximating the Top Eigenvector in Random Order Streams. CoRR abs/2412.11963 (2024)
2023
[i204]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2302-05707
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2302-05707
Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou:
On Differential Privacy and Adaptive Data Analysis with Bounded Space. CoRR abs/2302.05707 (2023)
[i203]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2303-01709
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2303-01709
David P. Woodruff, Fred Zhang, Samson Zhou:
Streaming Algorithms for Learning with Experts: Deterministic Versus Robust. CoRR abs/2303.01709 (2023)
[i202]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2304-00051
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2304-00051
Alexander Munteanu, Simon Omlor, David P. Woodruff:
Almost Linear Constant-Factor Sketching for 𝓁₁ and Logistic Regression. CoRR abs/2304.00051 (2023)
[i201]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2304-02261
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2304-02261
Tung Mai, Alexander Munteanu, Cameron Musco, Anup B. Rao, Chris Schwiegelshohn, David P. Woodruff:
Optimal Sketching Bounds for Sparse Linear Regression. CoRR abs/2304.02261 (2023)
[i200]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2304-06853
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2304-06853
Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff:
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming. CoRR abs/2304.06853 (2023)
[i199]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2304-07413
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2304-07413
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou:
Robust Algorithms on Adaptive Inputs from Bounded Adversaries. CoRR abs/2304.07413 (2023)
[i198]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2304-09217
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2304-09217
David P. Woodruff, Taisuke Yasuda:
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online. CoRR abs/2304.09217 (2023)
[i197]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2304-09281
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2304-09281
William Swartworth, David P. Woodruff:
Optimal Eigenvalue Approximation via Sketching. CoRR abs/2304.09281 (2023)
[i196]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2305-05826
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2305-05826
Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff:
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. CoRR abs/2305.05826 (2023)
[i195]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2306-00732
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2306-00732
David P. Woodruff, Taisuke Yasuda:
Sharper Bounds for 𝓁_p Sensitivity Sampling. CoRR abs/2306.00732 (2023)
[i194]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2306-01869
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2306-01869
Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou:
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. CoRR abs/2306.01869 (2023)
[i193]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2306-06611
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2306-06611
Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff:
Learning the Positions in CountSketch. CoRR abs/2306.06611 (2023)
[i192]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2307-03529
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2307-03529
Ying Feng, David P. Woodruff:
Improved Algorithms for White-Box Adversarial Streams. CoRR abs/2307.03529 (2023)
[i191]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2307-05117
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2307-05117
Yi Li, Honghao Lin, David P. Woodruff:
𝓁_p-Regression in the Arbitrary Partition Model of Communication. CoRR abs/2307.05117 (2023)
[i190]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2308-15772
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2308-15772
Hai Pham, Young Jin Kim, Subhabrata Mukherjee, David P. Woodruff, Barnabás Póczos, Hany Hassan Awadalla:
Task-Based MoE for Multitask Multilingual Machine Translation. CoRR abs/2308.15772 (2023)
[i189]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2310-02882
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2310-02882
Vincent Cohen-Addad, David P. Woodruff, Samson Zhou:
Streaming Euclidean k-median and k-means with o(log n) Space. CoRR abs/2310.02882 (2023)
[i188]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2310-05869
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2310-05869
Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, Amir Zandieh:
HyperAttention: Long-context Attention in Near-Linear Time. CoRR abs/2310.05869 (2023)
[i187]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2310-19068
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2310-19068
Gregory Dexter, Petros Drineas, David P. Woodruff, Taisuke Yasuda:
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming. CoRR abs/2310.19068 (2023)
[i186]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2311-00642
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2311-00642
David P. Woodruff, Peilin Zhong, Samson Zhou:
Near-Optimal k-Clustering in the Sliding Window Model. CoRR abs/2311.00642 (2023)
[i185]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2311-01960
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2311-01960
Tamás Sarlós, Xingyou Song, David P. Woodruff, Qiuyi Zhang:
Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products. CoRR abs/2311.01960 (2023)
[i184]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2311-04158
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2311-04158
Swati Padmanabhan, David P. Woodruff, Qiuyi (Richard) Zhang:
Computing Approximate 𝓁_p Sensitivities. CoRR abs/2311.04158 (2023)
[i183]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2311-17281
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2311-17281
Praneeth Kacham, David P. Woodruff:
Lower Bounds on Adaptive Sensing for Matrix Recovery. CoRR abs/2311.17281 (2023)
[i182]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2311-17868
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2311-17868
Justin Y. Chen, Piotr Indyk, David P. Woodruff:
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions. CoRR abs/2311.17868 (2023)
[i181]
- view
  - electronic edition @ iacr.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/iacr/DinurSWZ23
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/iacr/DinurSWZ23
Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou:
On Differential Privacy and Adaptive Data Analysis with Bounded Space. IACR Cryptol. ePrint Arch. 2023: 171 (2023)
2022
[i180]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2202-04515
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2202-04515
David P. Woodruff, Amir Zandieh:
Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time. CoRR abs/2202.04515 (2022)
[i179]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2202-05120
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2202-05120
Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff:
Low-Rank Approximation with 1/ε^1/3 Matrix-Vector Products. CoRR abs/2202.05120 (2022)
[i178]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2202-09797
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2202-09797
Yi Li, David P. Woodruff:
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. CoRR abs/2202.09797 (2022)
[i177]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2203-07557
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2203-07557
Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Fast Regression for Structured Inputs. CoRR abs/2203.07557 (2022)
[i176]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2203-09572
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2203-09572
Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang:
Triangle and Four Cycle Counting with Predictions in Graph Streams. CoRR abs/2203.09572 (2022)
[i175]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2204-03782
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2204-03782
Deanna Needell, William Swartworth, David P. Woodruff:
Testing Positive Semidefiniteness Using Linear Measurements. CoRR abs/2204.03782 (2022)
[i174]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2204-03790
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2204-03790
David P. Woodruff, Taisuke Yasuda:
High-Dimensional Geometric Streaming in Polynomial Space. CoRR abs/2204.03790 (2022)
[i173]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2204-06653
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2204-06653
Praneeth Kacham, David P. Woodruff:
Sketching Algorithms and Lower Bounds for Ridge Regression. CoRR abs/2204.06653 (2022)
[i172]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2204-09136
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2204-09136
Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou:
The White-Box Adversarial Data Stream Model. CoRR abs/2204.09136 (2022)
[i171]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2204-09837
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2204-09837
Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou:
Memory Bounds for the Experts Problem. CoRR abs/2204.09837 (2022)
[i170]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2206-12110
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2206-12110
Honghao Lin, Tian Luo, David P. Woodruff:
Learning Augmented Binary Search Trees. CoRR abs/2206.12110 (2022)
[i169]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2206-12802
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2206-12802
Alexander Munteanu, Simon Omlor, Zhao Song, David P. Woodruff:
Bounding the Width of Neural Networks via Coupled Initialization - A Worst Case Analysis. CoRR abs/2206.12802 (2022)
[i168]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2207-07417
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2207-07417
Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang:
Low Rank Approximation for General Tensor Networks. CoRR abs/2207.07417 (2022)
[i167]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2207-07822
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2207-07822
Sepideh Mahabadi, David P. Woodruff, Samson Zhou:
Adaptive Sketches for Robust Regression with Importance Sampling. CoRR abs/2207.07822 (2022)
[i166]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2207-08075
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2207-08075
Yi Li, Honghao Lin, David P. Woodruff, Yuheng Zhang:
Streaming Algorithms with Large Approximation Factors. CoRR abs/2207.08075 (2022)
[i165]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2207-08268
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2207-08268
David P. Woodruff, Taisuke Yasuda:
Online Lewis Weight Sampling. CoRR abs/2207.08268 (2022)
[i164]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2209-05676
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2209-05676
Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang:
Recovery from Non-Decomposable Distance Oracles. CoRR abs/2209.05676 (2022)
[i163]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2209-15219
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2209-15219
David P. Woodruff, Fred Zhang, Qiuyi Zhang:
Optimal Query Complexities for Dynamic Trace Estimation. CoRR abs/2209.15219 (2022)
[i162]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2211-06790
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2211-06790
Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou:
Near-Linear Sample Complexity for L_p Polynomial Regression. CoRR abs/2211.06790 (2022)
[i161]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2211-07132
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2211-07132
Yi Li, Honghao Lin, David P. Woodruff:
The 𝓁_p-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines. CoRR abs/2211.07132 (2022)
[i160]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/corr/abs-2211-09964
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2211-09964
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. CoRR abs/2211.09964 (2022)
2021
[i159]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2101-07546
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2101-07546
Graham Cormode, Charlie Dickens, David P. Woodruff:
Subspace exploration: Bounds on Projected Frequency Estimation. CoRR abs/2101.07546 (2021)
[i158]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2102-12317
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2102-12317
Yi Li, Honghao Lin, David P. Woodruff:
Learning-Augmented Sketches for Hessians. CoRR abs/2102.12317 (2021)
[i157]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2104-12946
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2104-12946
Yi Li, David P. Woodruff, Taisuke Yasuda:
Exponentially Improved Dimensionality Reduction for 𝓁₁: Subspace Embeddings and Independence Testing. CoRR abs/2104.12946 (2021)
[i156]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2105-03773
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2105-03773
David P. Woodruff, Samson Zhou:
Separations for Estimating Large Frequency Moments on Data Streams. CoRR abs/2105.03773 (2021)
[i155]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2105-08005
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2105-08005
Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David P. Woodruff, Samson Zhou:
Learning a Latent Simplex in Input-Sparsity Time. CoRR abs/2105.08005 (2021)
[i154]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2105-11338
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2105-11338
Akshay Kamath, Eric Price, David P. Woodruff:
A Simple Proof of a New Set Disjointness with Applications to Data Streams. CoRR abs/2105.11338 (2021)
[i153]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2106-08544
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2106-08544
Zhili Feng, Fred Roosta, David P. Woodruff:
Non-PSD Matrix Sketching with Applications to Regression and Optimization. CoRR abs/2106.08544 (2021)
[i152]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2107-01335
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2107-01335
Cyrus Rashtchian, David P. Woodruff, Peng Ye, Hanlin Zhu:
Average-Case Communication Complexity of Statistical Problems. CoRR abs/2107.01335 (2021)
[i151]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2107-02578
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2107-02578
Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou:
Noisy Boolean Hidden Matching with Applications. CoRR abs/2107.02578 (2021)
[i150]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2107-02846
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2107-02846
Shuchi Chawla, Jelani Nelson, Chris Umans, David P. Woodruff:
Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020. CoRR abs/2107.02846 (2021)
[i149]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2107-05672
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2107-05672
Rajesh Jayaram, Alireza Samadian, David P. Woodruff, Peng Ye:
In-Database Regression in Input Sparsity Time. CoRR abs/2107.05672 (2021)
[i148]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2107-06615
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2107-06615
Alexander Munteanu, Simon Omlor, David P. Woodruff:
Oblivious sketching for logistic regression. CoRR abs/2107.06615 (2021)
[i147]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2107-07141
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2107-07141
Anubhav Baweja, Justin Jia, David P. Woodruff:
An Efficient Semi-Streaming PTAS for Tournament Feedback ArcSet with Few Passes. CoRR abs/2107.07141 (2021)
[i146]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2107-07657
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2107-07657
Shuli Jiang, Dongyu Li, Irene Mengze Li, Arvind V. Mahankali, David P. Woodruff:
Streaming and Distributed Algorithms for Robust Column Subset Selection. CoRR abs/2107.07657 (2021)
[i145]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2107-07889
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2107-07889
Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David P. Woodruff:
Single Pass Entrywise-Transformed Low Rank Approximation. CoRR abs/2107.07889 (2021)
[i144]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2107-08090
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2107-08090
Nadiia Chepurko, Kenneth L. Clarkson, Praneeth Kacham, David P. Woodruff:
Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. CoRR abs/2107.08090 (2021)
[i143]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2108-09420
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2108-09420
Zhao Song, David P. Woodruff, Zheng Yu, Lichen Zhang:
Fast Sketching of Polynomial Kernels of Polynomial Degree. CoRR abs/2108.09420 (2021)
[i142]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2108-09887
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2108-09887
Yi Li, David P. Woodruff:
The Product of Gaussian Matrices is Close to Gaussian. CoRR abs/2108.09887 (2021)
[i141]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2108-12017
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2108-12017
Rajesh Jayaram, David P. Woodruff, Samson Zhou:
Truly Perfect Samplers for Data Streams and Sliding Windows. CoRR abs/2108.12017 (2021)
[i140]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2110-14094
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2110-14094
Jon Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou:
Learning-Augmented k-means Clustering. CoRR abs/2110.14094 (2021)
[i139]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2111-00664
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2111-00664
Shuli Jiang, Hai Pham, David P. Woodruff, Qiuyi (Richard) Zhang:
Optimal Sketching for Trace Estimation. CoRR abs/2111.00664 (2021)
[i138]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2111-00668
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2111-00668
David P. Woodruff, Taisuke Yasuda:
Improved Algorithms for Low Rank Approximation from Sparsity. CoRR abs/2111.00668 (2021)
[i137]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2111-03953
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2111-03953
Piotr Indyk, Shyam Narayanan, David P. Woodruff:
Frequency Estimation with One-Sided Error. CoRR abs/2111.03953 (2021)
[i136]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2111-04888
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2111-04888
Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda:
Active Sampling for Linear Regression Beyond the $\ell_2$ Norm. CoRR abs/2111.04888 (2021)
2020
[i135]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2002-08202
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2002-08202
Rajesh Jayaram, David P. Woodruff, Qiuyi Zhang:
Span Recovery for Deep Neural Networks with Applications to Input Obfuscation. CoRR abs/2002.08202 (2020)
[i134]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2003-02972
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2003-02972
Cyrus Rashtchian, Aneesh Sharma, David P. Woodruff:
LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew. CoRR abs/2003.02972 (2020)
[i133]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2003-14265
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2003-14265
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, Eylon Yogev:
A Framework for Adversarially Robust Streaming Algorithms. CoRR abs/2003.14265 (2020)
[i132]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2004-07986
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2004-07986
Zhao Song, David P. Woodruff, Peilin Zhong:
Average Case Column Subset Selection for Entrywise 𝓁₁-Norm Loss. CoRR abs/2004.07986 (2020)
[i131]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2004-10969
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2004-10969
Sepideh Mahabadi, Ilya P. Razenshteyn, David P. Woodruff, Samson Zhou:
Non-Adaptive Adaptive Sampling on Turnstile Streams. CoRR abs/2004.10969 (2020)
[i130]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2004-12646
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2004-12646
Yi Li, David P. Woodruff:
Input-Sparsity Low Rank Approximation in Schatten Norm. CoRR abs/2004.12646 (2020)
[i129]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2006-12748
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2006-12748
Agniva Chowdhury, Petros Drineas, David P. Woodruff, Samson Zhou:
Approximation Algorithms for Sparse Principal Component Analysis. CoRR abs/2006.12748 (2020)
[i128]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2006-14015
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2006-14015
Cyrus Rashtchian, David P. Woodruff, Hanlin Zhu:
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems. CoRR abs/2006.14015 (2020)
[i127]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2007-03633
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2007-03633
Alexandr Andoni, Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff:
Streaming Complexity of SVMs. CoRR abs/2007.03633 (2020)
[i126]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2007-03927
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2007-03927
David P. Woodruff, Amir Zandieh:
Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling. CoRR abs/2007.03927 (2020)
[i125]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2007-06744
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2007-06744
Edith Cohen, Rasmus Pagh, David P. Woodruff:
WOR and p's: Sketches for 𝓁_p-Sampling Without Replacement. CoRR abs/2007.06744 (2020)
[i124]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2007-09890
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2007-09890
Simin Liu, Tianrui Liu, Ali Vakilian, Yulin Wan, David P. Woodruff:
On Learned Sketches for Randomized Numerical Linear Algebra. CoRR abs/2007.09890 (2020)
[i123]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2007-10307
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2007-10307
Arvind V. Mahankali, David P. Woodruff:
Optimal 𝓁₁ Column Subset Selection and a Fast PTAS for Low Rank Approximation. CoRR abs/2007.10307 (2020)
[i122]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2010-09649
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2010-09649
Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff:
Hutch++: Optimal Stochastic Trace Estimation. CoRR abs/2010.09649 (2020)
[i121]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2011-04125
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2011-04125
Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, David P. Woodruff:
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra. CoRR abs/2011.04125 (2020)
[i120]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2011-04564
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2011-04564
Praneeth Kacham, David P. Woodruff:
Reduced-Rank Regression with Operator Norm Error. CoRR abs/2011.04564 (2020)
[i119]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2011-07471
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2011-07471
David P. Woodruff, Samson Zhou:
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators. CoRR abs/2011.07471 (2020)
[i118]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-2011-08432
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-2011-08432
Quang Minh Hoang, Trong Nghia Hoang, Hai Pham, David P. Woodruff:
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes. CoRR abs/2011.08432 (2020)
[i117]
- view
  - electronic edition @ weizmann.ac.il (open access)
  - details & citations
- export record
  dblp key:
  - journals/eccc/BravermanGW20
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/eccc/BravermanGW20
Mark Braverman, Sumegha Garg, David P. Woodruff:
The Coin Problem with Applications to Data Streams. Electron. Colloquium Comput. Complex. TR20 (2020)
2019
[i116]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1902-10328
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1902-10328
Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff:
Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. CoRR abs/1902.10328 (2019)
[i115]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1903-03520
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1903-03520
Vladimir Braverman, Moses Charikar, William Kuszmaul, David P. Woodruff, Lin F. Yang:
The One-Way Communication Complexity of Dynamic Time Warping Distance. CoRR abs/1903.03520 (2019)
[i114]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1903-12065
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1903-12065
Srikanta Tirthapura, David P. Woodruff:
Optimal Random Sampling from Distributed Streams Revisited. CoRR abs/1903.12065 (2019)
[i113]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1904-04126
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1904-04126
Rajesh Jayaram, Gokarna Sharma, Srikanta Tirthapura, David P. Woodruff:
Weighted Reservoir Sampling from Distributed Streams. CoRR abs/1904.04126 (2019)
[i112]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1904-05543
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1904-05543
Yi Li, Ruosong Wang, David P. Woodruff:
Tight Bounds for the Subspace Sketch Problem with Applications. CoRR abs/1904.05543 (2019)
[i111]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1904-09841
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1904-09841
Cameron Musco, Christopher Musco, David P. Woodruff:
Low-Rank Approximation from Communication Complexity. CoRR abs/1904.09841 (2019)
[i110]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1905-05376
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1905-05376
Kenneth L. Clarkson, Ruosong Wang, David P. Woodruff:
Dimensionality Reduction for Tukey Regression. CoRR abs/1905.05376 (2019)
[i109]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1905-06394
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1905-06394
Manuel Fernandez, David P. Woodruff, Taisuke Yasuda:
Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel k-means Clustering. CoRR abs/1905.06394 (2019)
[i108]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1905-07135
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1905-07135
David P. Woodruff, Guang Yang:
Separating k-Player from t-Player One-Way Communication, with Applications to Data Streams. CoRR abs/1905.07135 (2019)
[i107]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1906-00339
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1906-00339
Piotr Indyk, Ali Vakilian, Tal Wagner, David P. Woodruff:
Sample-Optimal Low-Rank Approximation of Distance Matrices. CoRR abs/1906.00339 (2019)
[i106]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1906-04661
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1906-04661
Yu Cheng, Ilias Diakonikolas, Rong Ge, David P. Woodruff:
Faster Algorithms for High-Dimensional Robust Covariance Estimation. CoRR abs/1906.04661 (2019)
[i105]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1906-05736
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1906-05736
Xiaoming Sun, David P. Woodruff, Guang Yang, Jialin Zhang:
Querying a Matrix through Matrix-Vector Products. CoRR abs/1906.05736 (2019)
[i104]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1906-05832
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1906-05832
Santosh S. Vempala, Ruosong Wang, David P. Woodruff:
The Communication Complexity of Optimization. CoRR abs/1906.05832 (2019)
[i103]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1907-05816
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1907-05816
Rajesh Jayaram, David P. Woodruff:
Towards Optimal Moment Estimation in Streaming and Distributed Models. CoRR abs/1907.05816 (2019)
[i102]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1909-01410
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1909-01410
Thomas D. Ahle, Michael Kapralov, Jakob Bæk Tejs Knudsen, Rasmus Pagh, Ameya Velingker, David P. Woodruff, Amir Zandieh:
Oblivious Sketching of High-Degree Polynomial Kernels. CoRR abs/1909.01410 (2019)
[i101]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1909-10668
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1909-10668
Manuel Fernandez, David P. Woodruff, Taisuke Yasuda:
The Query Complexity of Mastermind with 𝓁_p Distances. CoRR abs/1909.10668 (2019)
[i100]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1909-12441
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1909-12441
Huaian Diao, Zhao Song, David P. Woodruff, Xin Yang:
Total Least Squares Regression in Input Sparsity Time. CoRR abs/1909.12441 (2019)
[i99]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1909-13384
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1909-13384
Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, David P. Woodruff:
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation. CoRR abs/1909.13384 (2019)
[i98]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1911-05991
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1911-05991
Manuel Fernandez, David P. Woodruff, Taisuke Yasuda:
Graph Spanners in the Message-Passing Model. CoRR abs/1911.05991 (2019)
[i97]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1911-06958
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1911-06958
Frank Ban, David P. Woodruff, Qiuyi (Richard) Zhang:
Regularized Weighted Low Rank Approximation. CoRR abs/1911.06958 (2019)
[i96]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1911-11368
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1911-11368
Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff:
Pseudo-deterministic Streaming. CoRR abs/1911.11368 (2019)
[i95]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1912-04177
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1912-04177
Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff:
Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation. CoRR abs/1912.04177 (2019)
[i94]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1912-06060
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1912-06060
Xiaofei Shi, David P. Woodruff:
Sublinear Time Numerical Linear Algebra for Structured Matrices. CoRR abs/1912.06060 (2019)
[i93]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1912-12003
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1912-12003
Zhili Feng, Praneeth Kacham, David P. Woodruff:
Strong Coresets for Subspace Approximation and k-Median in Nearly Linear Time. CoRR abs/1912.12003 (2019)
[i92]
- view
  - electronic edition @ weizmann.ac.il (open access)
  - details & citations
- export record
  dblp key:
  - journals/eccc/GoldwasserGMW19
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/eccc/GoldwasserGMW19
Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, David P. Woodruff:
Pseudo-deterministic Streaming. Electron. Colloquium Comput. Complex. TR19 (2019)
2018
[i91]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1801-04414
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1801-04414
Ruosong Wang, David P. Woodruff:
Tight Bounds for 𝓁_p Oblivious Subspace Embeddings. CoRR abs/1801.04414 (2018)
[i90]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1803-02270
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1803-02270
Vladimir Braverman, Emanuele Viola, David P. Woodruff, Lin F. Yang:
Revisiting Frequency Moment Estimation in Random Order Streams. CoRR abs/1803.02270 (2018)
[i89]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1803-08777
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1803-08777
Rajesh Jayaram, David P. Woodruff:
Data Streams with Bounded Deletions. CoRR abs/1803.08777 (2018)
[i88]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1804-09673
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1804-09673
Vasileios Nakos, Xiaofei Shi, David P. Woodruff, Hongyang Zhang:
Improved Algorithms for Adaptive Compressed Sensing. CoRR abs/1804.09673 (2018)
[i87]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1805-00212
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1805-00212
Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou:
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. CoRR abs/1805.00212 (2018)
[i86]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1805-03765
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1805-03765
Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, Samson Zhou:
Near Optimal Linear Algebra in the Online and Sliding Window Models. CoRR abs/1805.03765 (2018)
[i85]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1805-08571
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1805-08571
Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David P. Woodruff:
On Coresets for Logistic Regression. CoRR abs/1805.08571 (2018)
[i84]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1805-10885
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1805-10885
Sumit Ganguly, David P. Woodruff:
High Probability Frequency Moment Sketches. CoRR abs/1805.10885 (2018)
[i83]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1806-06429
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1806-06429
Aditya Krishnan, Sidhanth Mohanty, David P. Woodruff:
On Sketching the q to p norms. CoRR abs/1806.06429 (2018)
[i82]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1806-10222
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1806-10222
John Hainline, Brendan Juba, Hai S. Le, David P. Woodruff:
Conditional Sparse 𝓁_p-norm Regression With Optimal Probability. CoRR abs/1806.10222 (2018)
[i81]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1807-00878
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1807-00878
David P. Woodruff, Qin Zhang:
Distributed Statistical Estimation of Matrix Products with Applications. CoRR abs/1807.00878 (2018)
[i80]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1807-02571
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1807-02571
Graham Cormode, Charlie Dickens, David P. Woodruff:
Leveraging Well-Conditioned Bases: Streaming \& Distributed Summaries in Minkowski p-Norms. CoRR abs/1807.02571 (2018)
[i79]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1807-06101
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1807-06101
Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David P. Woodruff:
A PTAS for 𝓁_p-Low Rank Approximation. CoRR abs/1807.06101 (2018)
[i78]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1808-05497
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1808-05497
Rajesh Jayaram, David P. Woodruff:
Perfect L_p Sampling in a Data Stream. CoRR abs/1808.05497 (2018)
[i77]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1809-02961
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1809-02961
Christian Sohler, David P. Woodruff:
Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension. CoRR abs/1809.02961 (2018)
[i76]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1809-06986
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1809-06986
Ainesh Bakshi, David P. Woodruff:
Sublinear Time Low-Rank Approximation of Distance Matrices. CoRR abs/1809.06986 (2018)
[i75]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1810-08171
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1810-08171
Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang:
Testing Matrix Rank, Optimally. CoRR abs/1810.08171 (2018)
[i74]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1811-01442
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1811-01442
Zhao Song, David P. Woodruff, Peilin Zhong:
Towards a Zero-One Law for Entrywise Low Rank Approximation. CoRR abs/1811.01442 (2018)
[i73]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1811-01885
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1811-01885
Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff:
Learning Two Layer Rectified Neural Networks in Polynomial Time. CoRR abs/1811.01885 (2018)
[i72]
- view
  - electronic edition @ weizmann.ac.il (open access)
  - details & citations
- export record
  dblp key:
  - journals/eccc/SongWZ18
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/eccc/SongWZ18
Zhao Song, David P. Woodruff, Peilin Zhong:
Relative Error Tensor Low Rank Approximation. Electron. Colloquium Comput. Complex. TR18 (2018)
2017
[i71]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/ChenSWZ17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/ChenSWZ17
Jiecao Chen, He Sun, David P. Woodruff, Qin Zhang:
Communication-Optimal Distributed Clustering. CoRR abs/1702.00196 (2017)
[i70]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/LiW17b
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/LiW17b
Yi Li, David P. Woodruff:
Embeddings of Schatten Norms with Applications to Data Streams. CoRR abs/1702.05626 (2017)
[i69]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/KapralovNPWWY17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/KapralovNPWWY17
Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh:
Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams. CoRR abs/1704.00633 (2017)
[i68]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/MuscoW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/MuscoW17
Cameron Musco, David P. Woodruff:
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. CoRR abs/1704.03371 (2017)
[i67]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/MuscoNSUW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/MuscoNSUW17
Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, David P. Woodruff:
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. CoRR abs/1704.04163 (2017)
[i66]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/SongWZ17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/SongWZ17
Zhao Song, David P. Woodruff, Peilin Zhong:
Relative Error Tensor Low Rank Approximation. CoRR abs/1704.08246 (2017)
[i65]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/BalcanLWZ17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BalcanLWZ17
Maria-Florina Balcan, Yingyu Liang, David P. Woodruff, Hongyang Zhang:
Optimal Sample Complexity for Matrix Completion and Related Problems via 𝓁s₂-Regularization. CoRR abs/1704.08683 (2017)
[i64]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/ChierichettiG0L17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/ChierichettiG0L17
Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, David P. Woodruff:
Algorithms for $\ell_p$ Low Rank Approximation. CoRR abs/1705.06730 (2017)
[i63]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/PriceSW17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/PriceSW17
Eric Price, Zhao Song, David P. Woodruff:
Fast Regression with an $\ell_\infty$ Guarantee. CoRR abs/1705.10723 (2017)
[i62]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1709-02919
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1709-02919
Yi Li, Vasileios Nakos, David P. Woodruff:
On Low-Risk Heavy Hitters and Sparse Recovery Schemes. CoRR abs/1709.02919 (2017)
[i61]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1709-07093
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1709-07093
Jarvis D. Haupt, Xingguo Li, David P. Woodruff:
Near Optimal Sketching of Low-Rank Tensor Regression. CoRR abs/1709.07093 (2017)
[i60]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1710-11253
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1710-11253
Karl Bringmann, Pavel Kolev, David P. Woodruff:
Approximation Algorithms for ࡁ₀-Low Rank Approximation. CoRR abs/1710.11253 (2017)
[i59]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1711-01596
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1711-01596
Cameron Musco, David P. Woodruff:
Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? CoRR abs/1711.01596 (2017)
[i58]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1712-09473
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1712-09473
Huaian Diao, Zhao Song, Wen Sun, David P. Woodruff:
Sketching for Kronecker Product Regression and P-splines. CoRR abs/1712.09473 (2017)
[i57]
- view
  - electronic edition via DOI (open access)
  - details & citations
  authority control:
- export record
  dblp key:
  - journals/dagstuhl-reports/DietzfelbingerM17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/dagstuhl-reports/DietzfelbingerM17
Martin Dietzfelbinger, Michael Mitzenmacher, Rasmus Pagh, David P. Woodruff, Martin Aumüller:
Theory and Applications of Hashing (Dagstuhl Seminar 17181). Dagstuhl Reports 7(5): 1-21 (2017)
[i56]
- view
  - electronic edition @ nii.ac.jp (open access)
  - details & citations
- export record
  dblp key:
  - journals/shonan-reports/BravermanWY17
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/shonan-reports/BravermanWY17
Vladimir Braverman, David P. Woodruff, Ke Yi:
Processing Big Data Streams (NII Shonan Meeting 2017-7). NII Shonan Meet. Rep. 2017 (2017)
2016
[i55]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/BravermanCWY16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BravermanCWY16
Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff, Lin F. Yang:
Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors. CoRR abs/1601.07473 (2016)
[i54]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/WoodruffZ16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/WoodruffZ16
David P. Woodruff, Peilin Zhong:
Distributed Low Rank Approximation of Implicit Functions of a Matrix. CoRR abs/1601.07721 (2016)
[i53]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/BhattacharyyaDW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BhattacharyyaDW16
Arnab Bhattacharyya, Palash Dey, David P. Woodruff:
An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems. CoRR abs/1603.00213 (2016)
[i52]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/BravermanCINWW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BravermanCINWW16
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, Jelani Nelson, Zhengyu Wang, David P. Woodruff:
BPTree: an ℓ₂ heavy hitters algorithm using constant memory. CoRR abs/1603.00759 (2016)
[i51]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/Woodruff16a
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/Woodruff16a
David P. Woodruff:
New Algorithms for Heavy Hitters in Data Streams. CoRR abs/1603.01733 (2016)
[i50]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/LiW16h
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/LiW16h
Yi Li, David P. Woodruff:
On Approximating Functions of the Singular Values in a Stream. CoRR abs/1604.08679 (2016)
[i49]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/KapralovPW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/KapralovPW16
Michael Kapralov, Vamsi K. Potluru, David P. Woodruff:
How to Fake Multiply by a Gaussian Matrix. CoRR abs/1606.05732 (2016)
[i48]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/SongWZ16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/SongWZ16
Zhao Song, David P. Woodruff, Peilin Zhong:
Low Rank Approximation with Entrywise ℓ₁-Norm Error. CoRR abs/1611.00898 (2016)
[i47]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/AvronCW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/AvronCW16
Haim Avron, Kenneth L. Clarkson, David P. Woodruff:
Faster Kernel Ridge Regression Using Sketching and Preconditioning. CoRR abs/1611.03220 (2016)
[i46]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/AvronCW16a
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/AvronCW16a
Haim Avron, Kenneth L. Clarkson, David P. Woodruff:
Sharper Bounds for Regression and Low-Rank Approximation with Regularization. CoRR abs/1611.03225 (2016)
[i45]
- view
  - electronic edition @ nii.ac.jp (open access)
  - details & citations
- export record
  dblp key:
  - journals/shonan-reports/KannanMW16
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/shonan-reports/KannanMW16
Ravindran Kannan, Michael W. Mahoney, David P. Woodruff:
Recent Advances in Randomized Numerical Linear Algebra (NII Shonan Meeting 2016-10). NII Shonan Meet. Rep. 2016 (2016)
2015
[i44]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/GhashamiLPW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/GhashamiLPW15
Mina Ghashami, Edo Liberty, Jeff M. Phillips, David P. Woodruff:
Frequent Directions : Simple and Deterministic Matrix Sketching. CoRR abs/1501.01711 (2015)
[i43]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/BalcanLSW015
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BalcanLSW015
Maria-Florina Balcan, Yingyu Liang, Le Song, David P. Woodruff, Bo Xie:
Distributed Kernel Principal Component Analysis. CoRR abs/1503.06858 (2015)
[i42]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/BackursIPRW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BackursIPRW15
Arturs Backurs, Piotr Indyk, Eric Price, Ilya P. Razenshteyn, David P. Woodruff:
Nearly-optimal bounds for sparse recovery in generic norms, with applications to $k$-median sketching. CoRR abs/1504.01076 (2015)
[i41]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/BoutsidisW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BoutsidisW15
Christos Boutsidis, David P. Woodruff:
Communication-optimal Distributed Principal Component Analysis in the Column-partition Model. CoRR abs/1504.06729 (2015)
[i40]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/EsfandiariHW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/EsfandiariHW15
Hossein Esfandiari, MohammadTaghi Hajiaghayi, David P. Woodruff:
Applications of Uniform Sampling: Densest Subgraph and Beyond. CoRR abs/1506.04505 (2015)
[i39]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/BravermanGMNW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BravermanGMNW15
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff:
Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality. CoRR abs/1506.07216 (2015)
[i38]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/CohenNW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/CohenNW15
Michael B. Cohen, Jelani Nelson, David P. Woodruff:
Optimal approximate matrix product in terms of stable rank. CoRR abs/1507.02268 (2015)
[i37]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/ClarksonW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/ClarksonW15
Kenneth L. Clarkson, David P. Woodruff:
Input Sparsity and Hardness for Robust Subspace Approximation. CoRR abs/1510.06073 (2015)
[i36]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/BravermanCIW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BravermanCIW15
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin, David P. Woodruff:
Beating CountSketch for Heavy Hitters in Insertion Streams. CoRR abs/1511.00661 (2015)
[i35]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/AndoniCKQWZ15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/AndoniCKQWZ15
Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang:
On Sketching Quadratic Forms. CoRR abs/1511.06099 (2015)
[i34]
- view
  - electronic edition @ weizmann.ac.il (open access)
  - details & citations
- export record
  dblp key:
  - journals/eccc/MolinaroWY15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/eccc/MolinaroWY15
Marco Molinaro, David P. Woodruff, Grigory Yaroslavtsev:
Amplification of One-Way Information Complexity via Codes and Noise Sensitivity. Electron. Colloquium Comput. Complex. TR15 (2015)
[i33]
- view
  - electronic edition @ weizmann.ac.il (open access)
  - details & citations
- export record
  dblp key:
  - journals/eccc/WeinsteinW15
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/eccc/WeinsteinW15
Omri Weinstein, David P. Woodruff:
The Simultaneous Communication of Disjointness with Applications to Data Streams. Electron. Colloquium Comput. Complex. TR15 (2015)
2014
[i32]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/AndoniKW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/AndoniKW14
Alexandr Andoni, Robert Krauthgamer, David P. Woodruff:
The Sketching Complexity of Graph Cuts. CoRR abs/1403.7058 (2014)
[i31]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/BoutsidisW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BoutsidisW14
Christos Boutsidis, David P. Woodruff:
Optimal CUR Matrix Decompositions. CoRR abs/1405.7910 (2014)
[i30]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/LiSWW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/LiSWW14
Yi Li, Xiaoming Sun, Chengu Wang, David P. Woodruff:
On The Communication Complexity of Linear Algebraic Problems in the Message Passing Model. CoRR abs/1407.4755 (2014)
[i29]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/BalcanKLW14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/BalcanKLW14
Maria-Florina Balcan, Vandana Kanchanapally, Yingyu Liang, David P. Woodruff:
Improved Distributed Principal Component Analysis. CoRR abs/1408.5823 (2014)
[i28]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/Woodruff14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/Woodruff14
David P. Woodruff:
Sketching as a Tool for Numerical Linear Algebra. CoRR abs/1411.4357 (2014)
[i27]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/ChenQWZ14
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/ChenQWZ14
Jiecao Chen, Bo Qin, David P. Woodruff, Qin Zhang:
A Sketching Algorithm for Spectral Graph Sparsification. CoRR abs/1412.8225 (2014)
2013
[i26]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1304-4636
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1304-4636
David P. Woodruff, Qin Zhang:
When Distributed Computation does not Help. CoRR abs/1304.4636 (2013)
[i25]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1305-5580
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1305-5580
David P. Woodruff, Qin Zhang:
Subspace Embeddings and ℓ_p-Regression Using Exponential Random Variables. CoRR abs/1305.5580 (2013)
2012
[i24]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1205-3518
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1205-3518
Eric Price, David P. Woodruff:
Lower Bounds for Adaptive Sparse Recovery. CoRR abs/1205.3518 (2012)
[i23]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1206-5725
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1206-5725
Jelani Nelson, Huy L. Nguyên, David P. Woodruff:
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation. CoRR abs/1206.5725 (2012)
[i22]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1207-4684
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1207-4684
Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, Xiangrui Meng, David P. Woodruff:
The Fast Cauchy Transform: with Applications to Basis Construction, Regression, and Subspace Approximation in L1. CoRR abs/1207.4684 (2012)
[i21]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1207-6365
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1207-6365
Kenneth L. Clarkson, David P. Woodruff:
Low Rank Approximation and Regression in Input Sparsity Time. CoRR abs/1207.6365 (2012)
[i20]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1211-1056
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1211-1056
Moritz Hardt, David P. Woodruff:
How Robust are Linear Sketches to Adaptive Inputs? CoRR abs/1211.1056 (2012)
2011
[i19]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1106-0365
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1106-0365
Khanh Do Ba, Piotr Indyk, Eric Price, David P. Woodruff:
Lower Bounds for Sparse Recovery. CoRR abs/1106.0365 (2011)
[i18]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1109-3843
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1109-3843
Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff:
Fast approximation of matrix coherence and statistical leverage. CoRR abs/1109.3843 (2011)
[i17]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1110-3850
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1110-3850
Piotr Indyk, Eric Price, David P. Woodruff:
On the Power of Adaptivity in Sparse Recovery. CoRR abs/1110.3850 (2011)
[i16]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1110-4414
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1110-4414
Eric Price, David P. Woodruff:
(1+eps)-approximate Sparse Recovery. CoRR abs/1110.4414 (2011)
[i15]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1112-5153
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1112-5153
David P. Woodruff, Qin Zhang:
Tight Bounds for Distributed Functional Monitoring. CoRR abs/1112.5153 (2011)
2010
[i14]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1007-4191
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1007-4191
Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff:
Fast Moment Estimation in Data Streams in Optimal Space. CoRR abs/1007.4191 (2010)
[i13]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1010-4408
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1010-4408
Kenneth L. Clarkson, Elad Hazan, David P. Woodruff:
Sublinear Optimization for Machine Learning. CoRR abs/1010.4408 (2010)
[i12]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-1011-6100
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-1011-6100
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev:
Steiner Transitive-Closure Spanners of d-Dimensional Posets. CoRR abs/1011.6100 (2010)
2009
[i11]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-0904-2027
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-0904-2027
Jelani Nelson, David P. Woodruff:
A Near-Optimal Algorithm for L1-Difference. CoRR abs/0904.2027 (2009)
[i10]
- view
  - electronic edition @ weizmann.ac.il (open access)
  - details & citations
- export record
  dblp key:
  - journals/eccc/BhattacharyyaGJRW09
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/eccc/BhattacharyyaGJRW09
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-Closure Spanners of the Hypercube and the Hypergrid. Electron. Colloquium Comput. Complex. TR09 (2009)
2008
[i9]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-0808-1787
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-0808-1787
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff:
Transitive-Closure Spanners. CoRR abs/0808.1787 (2008)
[i8]
- view
  - electronic edition @ arxiv.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/corr/abs-0811-3648
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/corr/abs-0811-3648
Daniel M. Kane, Jelani Nelson, David P. Woodruff:
Revisiting Norm Estimation in Data Streams. CoRR abs/0811.3648 (2008)
2007
[i7]
- view
  - electronic edition @ weizmann.ac.il (open access)
  - details & citations
- export record
  dblp key:
  - journals/eccc/Woodruff07
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/eccc/Woodruff07
David P. Woodruff:
New Lower Bounds for General Locally Decodable Codes. Electron. Colloquium Comput. Complex. TR07 (2007)
2006
[i6]
- view
  - electronic edition @ iacr.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/iacr/RamzanW06
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/iacr/RamzanW06
Zulfikar Ramzan, David P. Woodruff:
Fast Algorithms for the Free Riders Problem in Broadcast Encryption. IACR Cryptol. ePrint Arch. 2006: 293 (2006)
[i5]
- view
  - electronic edition @ iacr.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/iacr/Woodruff06
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/iacr/Woodruff06
David P. Woodruff:
Revisiting the Efficiency of Malicious Two-Party Computation. IACR Cryptol. ePrint Arch. 2006: 397 (2006)
2005
[i4]
- view
  - electronic edition @ weizmann.ac.il (open access)
  - details & citations
- export record
  dblp key:
  - journals/eccc/ECCC-TR05-009
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR05-009
David P. Woodruff, Sergey Yekhanin:
A Geometric Approach to Information-Theoretic Private Information Retrieval. Electron. Colloquium Comput. Complex. TR05 (2005)
[i3]
- view
  - electronic edition @ weizmann.ac.il (open access)
  - details & citations
- export record
  dblp key:
  - journals/eccc/ECCC-TR05-117
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/eccc/ECCC-TR05-117
Piotr Indyk, David P. Woodruff:
Polylogarithmic Private Approximations and Efficient Matching. Electron. Colloquium Comput. Complex. TR05 (2005)
2004
[i2]
- view
  - electronic edition @ iacr.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/iacr/WoodruffS04
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/iacr/WoodruffS04
David P. Woodruff, Jessica Staddon:
Private Inference Control. IACR Cryptol. ePrint Arch. 2004: 130 (2004)
[i1]
- view
  - electronic edition @ iacr.org (open access)
  - details & citations
- export record
  dblp key:
  - journals/iacr/DijkGPRSSW04
- ask others
- share record
  persistent URL:
  - https://dblp.org/rec/journals/iacr/DijkGPRSSW04
Marten van Dijk, Robert Granger, Dan Page, Karl Rubin, Alice Silverberg, Martijn Stam, David P. Woodruff:
Practical Cryptography in High Dimensional Tori. IACR Cryptol. ePrint Arch. 2004: 352 (2004)

Coauthor Index

see FAQ

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.