Michael Kapralov

Available identifiers

zbMath Open kapralov.michaelMaRDI QIDQ2322504

List of research outcomes

Publication	Date of Publication	Type
https://portal.mardi4nfdi.de/entity/Q6126334	2024-04-09	Paper
https://portal.mardi4nfdi.de/entity/Q6147352	2024-01-15	Paper
https://portal.mardi4nfdi.de/entity/Q6147368	2024-01-15	Paper
https://portal.mardi4nfdi.de/entity/Q6147369	2024-01-15	Paper
Towards tight bounds for spectral sparsification of hypergraphs	2023-11-14	Paper
Toeplitz Low-Rank Approximation with Sublinear Query Complexity	2022-11-21	Paper
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling	2022-07-18	Paper
Oblivious Sketching of High-Degree Polynomial Kernels	2021-02-02	Paper
Differentially Private Release of Synthetic Graphs	2021-02-02	Paper
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples	2021-02-02	Paper
Fast and Space Efficient Spectral Sparsification in Dynamic Streams	2021-02-02	Paper
An optimal space lower bound for approximating MAX-CUT	2020-01-30	Paper
A universal sampling method for reconstructing signals with simple Fourier transforms	2020-01-30	Paper
Dimension-independent Sparse Fourier Transform	2019-10-15	Paper
Perfect matchings in \(\tilde{O}(n^{1.5})\) time in regular bipartite graphs	2019-09-04	Paper
(Nearly) Sample-Optimal Sparse Fourier Transform	2019-06-20	Paper
Approximating matching size from random streams	2019-06-20	Paper
Online submodular welfare maximization: Greedy is optimal	2019-05-15	Paper
On differentially private low rank approximation	2019-05-15	Paper
Better bounds for matchings in the streaming model	2019-05-15	Paper
https://portal.mardi4nfdi.de/entity/Q5743414	2019-05-10	Paper
https://portal.mardi4nfdi.de/entity/Q4633805	2019-05-06	Paper
(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space	2018-07-16	Paper
Streaming Lower Bounds for Approximating MAX-CUT	2017-10-05	Paper
Sparse fourier transform in any constant dimension with nearly-optimal sample complexity in sublinear time	2017-09-29	Paper
An adaptive sublinear-time block sparse fourier transform	2017-08-17	Paper
Single Pass Spectral Sparsification in Dynamic Streams	2017-03-10	Paper
Spectral sparsification via random spanners	2016-10-07	Paper
Spanners and sparsifiers in dynamic streams	2015-09-03	Paper
Perfect matchings in o( n log n ) time in regular bipartite graphs	2014-08-13	Paper
Perfect Matchings in $O(n\log n)$ Time in Regular Bipartite Graphs	2013-09-25	Paper
NNS Lower Bounds via Metric Expansion for l  ∞  and EMD	2013-08-12	Paper
Embedding Paths into Trees: VM Placement to Minimize Congestion	2012-09-25	Paper
Multiplicative Approximations of Random Walk Transition Probabilities	2011-08-17	Paper
Improved Bounds for Online Stochastic Matching	2010-09-06	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Michael Kapralov