263 papers
cs ds
0/02026
7- JulTight Lower Bounds for the Multi-Secretary Problem via Bellman Certificatesno summary yetcs-ds2607.02150NYU0 citesJul 2, 2026
- JulAdversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile Streamsno summary yetcs-ds2607.06312CMU0 citesJul 7, 2026
- JulThe Power of Arrival Times in Random-Order Online Facility Locationno summary yetcs-ds2607.10564Princeton0 citesJul 12, 2026
- JunThreshold Minimum Cut with Terminal Quotas: Logarithmic and Planar Approximation Algorithmsno summary yetcs-ds2606.15324CMU0 citesJun 13, 2026
- JunMulti-Vector Embeddings are Provably More Expressive than Single Vector Embeddingsno summary yetcs-ds2606.23475Google Research0 citesJun 22, 2026
- JunSpace-Efficient Language Generation in the Limitno summary yetcs-ds2606.25777Stanford0 citesJun 24, 2026
- AprFast Concurrent Primitives Despite Contentionno summary yetcs-ds2604.14530NYU0 citesApr 16, 2026
2024
7- DecData-Driven Solution Portfoliosno summary yetcs-ds2412.00717Google Research0 citesDec 1, 2024
- JulFaster Algorithms for Schatten-p Low Rank Approximationno summary yetcs-ds2407.11959Google Research0 citesJul 16, 2024
- JulImproving Online Algorithms via ML Predictionsno summary yetcs-ds2407.17712Google Research124 citesJul 25, 2024
- MayOnline Load and Graph Balancing for Random Order Inputsno summary yetcs-ds2405.07949Google Research0 citesMay 13, 2024
- AprIt's Hard to HAC with Average Linkage!no summary yetcs-ds2404.14730Google Research0 citesApr 23, 2024
- FebStreaming Algorithms for Connectivity Augmentationno summary yetcs-ds2402.10806Microsoft Research0 citesFeb 16, 2024
- FebParallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depthno summary yetcs-ds2402.14950Google Research4 citesFeb 22, 2024
2023
5- NovA Combinatorial Approach to Robust PCAno summary yetcs-ds2311.16416Google Research0 citesNov 28, 2023
- JulImproved Diversity Maximization Algorithms for Matching and Pseudoforestno summary yetcs-ds2307.04329Microsoft Research0 citesJul 10, 2023
- AprOptimal Sketching Bounds for Sparse Linear Regressionno summary yetcs-ds2304.02261Adobe1 citesApr 5, 2023
- MarOptimal Fully Dynamic $k$-Center Clustering for Adaptive and Oblivious Adversariesno summary yetcs-ds2303.11843Google Research9 citesMar 21, 2023
- JanDifferentially Private Continual Releases of Streaming Frequency Moment Estimationsno summary yetcs-ds2301.05605Google Research1 citesJan 13, 2023
2022
5- DecDeMEtRIS: Counting (near)-Cliques by Crawlingno summary yetcs-ds2212.03957Google Research3 citesDec 7, 2022
- NovOnline Learning and Bandits with Queried Hintsno summary yetcs-ds2211.02703Google Research0 citesNov 4, 2022
- NovPrivate Counting of Distinct and k-Occurring Items in Time Windowsno summary yetcs-ds2211.11718Google Research3 citesNov 21, 2022
- SepOnline Demand Scheduling with Failoversno summary yetcs-ds2209.00710Microsoft Research0 citesSep 1, 2022
- MarImproved Approximation Algorithms and Lower Bounds for Search-Diversification Problemsno summary yetcs-ds2203.01857Google Research1 citesMar 3, 2022
2021
20- DecClustering Mixtures with Almost Optimal Separation in Polynomial Timeno summary yetcs-ds2112.00706Microsoft Research0 citesDec 1, 2021
- NovRobust Estimation for Random Graphsno summary yetcs-ds2111.05320Google Research1 citesNov 9, 2021
- NovOptimal Decremental Connectivity in Non-Sparse Graphsno summary yetcs-ds2111.09376Google Research0 citesNov 17, 2021
- NovApproximation Algorithms for LCS and LIS with Truly Improved Running Timesno summary yetcs-ds2111.10538Adobe1 citesNov 20, 2021
- OctTight and Robust Private Mean Estimation with Few Usersno summary yetcs-ds2110.11876Google Research5 citesOct 22, 2021
- SepC-MinHash: Practically Reducing Two Permutations to Just Oneno summary yetcs-ds2109.04595Baidu1 citesSep 10, 2021
- AugScheduling with Communication Delay in Near-Linear Timeno summary yetcs-ds2108.02770Google Research1 citesAug 5, 2021
- JulTowards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Timeno summary yetcs-ds2107.06582Google Research4 citesJul 14, 2021
- JulOn the Extended TSP Problemno summary yetcs-ds2107.07815Meta / FAIR2 citesJul 16, 2021
- JulFast Low-Rank Tensor Decomposition by Ridge Leverage Score Samplingno summary yetcs-ds2107.10654Google Research2 citesJul 22, 2021
- JunNumerical Composition of Differential Privacyno summary yetcs-ds2106.02848Microsoft Research0 citesJun 5, 2021
- JunHierarchical Agglomerative Graph Clustering in Nearly-Linear Timeno summary yetcs-ds2106.05610Google Research10 citesJun 10, 2021
- JunCorrelation Clustering in Constant Many Parallel Roundsno summary yetcs-ds2106.08448Google Research3 citesJun 15, 2021
- May$\ell_2$-norm Flow Diffusion in Near-Linear Timeno summary yetcs-ds2105.14629Google Research0 citesMay 30, 2021
- AprLocally Private k-Means in One Roundno summary yetcs-ds2104.09734Google Research1 citesApr 20, 2021
- JanOn the Approximation Relationship between Optimizing Ratio of Submodular (RS) and Difference of Submodular (DS) Functionsno summary yetcs-ds2101.01631DeepMind2 citesJan 5, 2021
- JanPlanar Reachability Under Single Vertex or Edge Failuresno summary yetcs-ds2101.02574Google Research0 citesJan 7, 2021
- JanSpectral Clustering Oracles in Sublinear Timeno summary yetcs-ds2101.05549Google Research0 citesJan 14, 2021
- JanMinimum Cost Flows, MDPs, and $\ell_1$-Regression in Nearly Linear Time for Dense Instancesno summary yetcs-ds2101.05719Google Research14 citesJan 14, 2021
- JanHierarchical Clustering via Sketches and Hierarchical Correlation Clusteringno summary yetcs-ds2101.10639Google Research0 citesJan 26, 2021
2020
34- DecSearching, Sorting, and Cake Cutting in Roundsno summary yetcs-ds2012.00738Google Research0 citesDec 1, 2020
- NovCombinatorial Bernoulli Factoriesno summary yetcs-ds2011.03865Google Research0 citesNov 7, 2020
- NovSecretaries with Adviceno summary yetcs-ds2011.06726Google Research5 citesNov 13, 2020
- NovConsistent k-Clustering for General Metricsno summary yetcs-ds2011.06888Google Research0 citesNov 13, 2020
- NovTo Close Is Easier Than To Open: Dual Parameterization To k-Medianno summary yetcs-ds2011.08083Google Research0 citesNov 16, 2020
- SepZuckerli: A New Compressed Representation for Graphsno summary yetcs-ds2009.01353Google Research1 citesSep 2, 2020
- SepOn Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphsno summary yetcs-ds2009.05039Google Research0 citesSep 10, 2020
- SepAn improved quantum-inspired algorithm for linear regressionno summary yetcs-ds2009.07268Adobe48 citesSep 15, 2020
- SepMetrical Service Systems with Transformationsno summary yetcs-ds2009.08266Microsoft Research1 citesSep 17, 2020
- SepNear-Optimal Decremental Hopsets with Applicationsno summary yetcs-ds2009.08416Google Research2 citesSep 17, 2020
- AugConsistent $k$-Median: Simpler, Better and Robustno summary yetcs-ds2008.06101Microsoft Research2 citesAug 13, 2020
- JulAll-Pairs LCA in DAGs: Breaking through the $O(n^{2.5})$ barrierno summary yetcs-ds2007.08914Google Research1 citesJul 17, 2020
- JulRobust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationno summary yetcs-ds2007.15839Microsoft Research6 citesJul 31, 2020
- JunA Survey on Approximation in Parameterized Complexity: Hardness and Algorithmsno summary yetcs-ds2006.04411Google Research1 citesJun 8, 2020
- JunFully Dynamic Algorithm for Constrained Submodular Optimizationno summary yetcs-ds2006.04704Google Research1 citesJun 8, 2020
- JunSliding Window Algorithms for k-Clustering Problemsno summary yetcs-ds2006.05850Google Research10 citesJun 10, 2020
- JunRobust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingno summary yetcs-ds2006.06980Microsoft Research5 citesJun 12, 2020
- MayEdge-Weighted Online Bipartite Matchingno summary yetcs-ds2005.01929Google Research22 citesMay 5, 2020
- MayScheduling Flows on a Switch to Optimize Response Timesno summary yetcs-ds2005.09724Google Research1 citesMay 19, 2020
- AprGrammar-Compressed Indexes with Logarithmic Search Timeno summary yetcs-ds2004.01032LinkedIn0 citesApr 1, 2020
- AprAdversarially Robust Streaming Algorithms via Differential Privacyno summary yetcs-ds2004.05975Google Research8 citesApr 13, 2020
- AprOnline Multiserver Convex Chasing and Optimizationno summary yetcs-ds2004.07346Microsoft Research0 citesApr 15, 2020
- AprMaximizing Determinants under Matroid Constraintsno summary yetcs-ds2004.07886Amazon3 citesApr 16, 2020
- AprVariable Decomposition for Prophet Inequalities and Optimal Orderingno summary yetcs-ds2004.10163Google Research2 citesApr 21, 2020
- AprScheduling Precedence-Constrained Jobs on Related Machines with Communication Delayno summary yetcs-ds2004.10776Google Research4 citesApr 22, 2020
- AprBatched Predecessor and Sorting with Size-Priced Information in External Memoryno summary yetcs-ds2004.13197Google Research0 citesApr 27, 2020
- MarOptimal Contextual Pricing and Extensionsno summary yetcs-ds2003.01703Google Research1 citesMar 3, 2020
- MarLSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skewno summary yetcs-ds2003.02972Google Research1 citesMar 6, 2020
- MarA Framework for Adversarially Robust Streaming Algorithmsno summary yetcs-ds2003.14265Google Research20 citesMar 31, 2020
- MarThe Discrete Gaussian for Differential Privacyno summary yetcs-ds2004.00010Google Research37 citesMar 31, 2020
- FebFair Correlation Clusteringno summary yetcs-ds2002.02274Google Research7 citesFeb 6, 2020
- FebSpan Recovery for Deep Neural Networks with Applications to Input Obfuscationno summary yetcs-ds2002.08202Google Research0 citesFeb 19, 2020
- FebThe Power of Recourse: Better Algorithms for Facility Location in Online and Dynamic Modelsno summary yetcs-ds2002.10658Microsoft Research2 citesFeb 25, 2020
- JanTight Static Lower Bounds for Non-Adaptive Data Structuresno summary yetcs-ds2001.05053Google Research0 citesJan 14, 2020
2019
33- DecThe power of synergy in differential privacy: Combining a small curator with local randomizersno summary yetcs-ds1912.08951Google Research5 citesDec 18, 2019
- DecApproximate Maximum Matching in Random Streamsno summary yetcs-ds1912.10497Adobe0 citesDec 22, 2019
- NovPan-Private Uniformity Testingno summary yetcs-ds1911.01452Google Research5 citesNov 4, 2019
- NovStrong Self-Concordance and Samplingno summary yetcs-ds1911.05656Microsoft Research0 citesNov 13, 2019
- NovLow-Rank Toeplitz Matrix Estimation via Random Ultra-Sparse Rulersno summary yetcs-ds1911.08015Microsoft Research2 citesNov 19, 2019
- NovPERMUTATION Strikes Back: The Power of Recourse in Online Metric Matchingno summary yetcs-ds1911.12778Microsoft Research5 citesNov 28, 2019
- NovAdversarially Robust Low Dimensional Representationsno summary yetcs-ds1911.13268Google Research5 citesNov 29, 2019
- OctStreaming Balanced Clusteringno summary yetcs-ds1910.00788Google Research1 citesOct 2, 2019
- OctProphets, Secretaries, and Maximizing the Probability of Choosing the Bestno summary yetcs-ds1910.03798Microsoft Research2 citesOct 9, 2019
- OctScalable Nearest Neighbor Search for Optimal Transportno summary yetcs-ds1910.04126Microsoft Research10 citesOct 9, 2019
- OctRegret Bounds for Batched Banditsno summary yetcs-ds1910.04959Google Research8 citesOct 11, 2019
- OctNear-Optimal Massively Parallel Graph Connectivityno summary yetcs-ds1910.05385Google Research1 citesOct 11, 2019
- OctTemporal Network Samplingno summary yetcs-ds1910.08657Adobe2 citesOct 18, 2019
- SepDe(con)struction of the lazy-F loop: improving performance of Smith Waterman alignmentno summary yetcs-ds1909.00899Microsoft Research0 citesSep 3, 2019
- SepOblivious Sketching of High-Degree Polynomial Kernelsno summary yetcs-ds1909.01410Google Research2 citesSep 3, 2019
- AugCorrelation Clustering with Same-Cluster Queries Bounded by Optimal Costno summary yetcs-ds1908.04976AllenAI8 citesAug 14, 2019
- JulReliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphsno summary yetcs-ds1907.02266Google Research6 citesJul 4, 2019
- JulWalking Randomly, Massively, and Efficientlyno summary yetcs-ds1907.05391Google Research1 citesJul 11, 2019
- JulA Fast Minimum Degree Algorithm and Matching Lower Boundno summary yetcs-ds1907.12119Google Research1 citesJul 28, 2019
- JulIterative Budgeted Exponential Searchno summary yetcs-ds1907.13062DeepMind5 citesJul 30, 2019
- JunSorted Top-k in Roundsno summary yetcs-ds1906.05208Google Research0 citesJun 12, 2019
- JunFlows in Almost Linear Time via Adaptive Preconditioningno summary yetcs-ds1906.10340Microsoft Research0 citesJun 25, 2019
- MayEfficient Second-Order Shape-Constrained Function Fittingno summary yetcs-ds1905.02149Adobe0 citesMay 6, 2019
- MayChasing Convex Bodies with Linear Competitive Rationo summary yetcs-ds1905.11877Google Research2 citesMay 28, 2019
- MayClustering without Over-Representationno summary yetcs-ds1905.12753Google Research80 citesMay 29, 2019
- MayPrivate Hypothesis Selectionno summary yetcs-ds1905.13229Google Research7 citesMay 30, 2019
- AprLower Bounds for Oblivious Near-Neighbor Searchno summary yetcs-ds1904.04828Google Research0 citesApr 9, 2019
- AprStochastic Online Metric Matchingno summary yetcs-ds1904.09284Google Research3 citesApr 19, 2019
- AprTrace Reconstruction: Generalized and Parameterizedno summary yetcs-ds1904.09618Microsoft Research17 citesApr 21, 2019
- MarNear Optimal Online Algorithms and Fast Approximation Algorithms for Resource Allocation Problemsno summary yetcs-ds1903.03944Google Research0 citesMar 10, 2019
- FebA Unified Framework for Marketing Budget Allocationno summary yetcs-ds1902.01128Alibaba2 citesFeb 4, 2019
- JanEfficient Multiparty Interactive Coding for Insertions, Deletions and Substitutionsno summary yetcs-ds1901.09863Microsoft Research1 citesJan 28, 2019
- JanOnline Pandora's Boxes and Banditsno summary yetcs-ds1901.10698Google Research1 citesJan 30, 2019
2018
33- DecSemi-Online Bipartite Matchingno summary yetcs-ds1812.00134Google Research1 citesDec 1, 2018
- DecA Universal Sampling Method for Reconstructing Signals with Simple Fourier Transformsno summary yetcs-ds1812.08723Microsoft Research4 citesDec 20, 2018
- NovChasing Nested Convex Bodies Nearly Optimallyno summary yetcs-ds1811.00999Microsoft Research5 citesNov 2, 2018
- NovNonlinear Dimension Reduction via Outer Bi-Lipschitz Extensionsno summary yetcs-ds1811.03591Microsoft Research0 citesNov 8, 2018
- NovVectorized Character Counting for Faster Pattern Matchingno summary yetcs-ds1811.06127Microsoft Research1 citesNov 15, 2018
- NovPrivate Selection from Private Candidatesno summary yetcs-ds1811.07971Google Research3 citesNov 19, 2018
- NovParallel approach to sliding window sumsno summary yetcs-ds1811.10074Microsoft Research1 citesNov 25, 2018
- NovSolving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizationsno summary yetcs-ds1811.10722Adobe5 citesNov 26, 2018
- OctPath matrix and path energy of graphsno summary yetcs-ds1810.04870Meta / FAIR1 citesOct 11, 2018
- OctBilu-Linial stability, certified algorithms and the Independent Set problemno summary yetcs-ds1810.08414Google Research3 citesOct 19, 2018
- SepApproximation algorithms for stochastic clusteringno summary yetcs-ds1809.02271Google Research4 citesSep 7, 2018
- SepDynamic Resource Allocation in the Cloud with Near-Optimal Efficiencyno summary yetcs-ds1809.02688Microsoft Research4 citesSep 7, 2018
- SepMaximally Consistent Sampling and the Jaccard Index of Probability Distributionsno summary yetcs-ds1809.04052Google Research24 citesSep 11, 2018
- SepOnline Resource Allocation under Partially Predictable Demandno summary yetcs-ds1810.00447Google Research9 citesSep 30, 2018
- AugParallel and Streaming Algorithms for K-Core Decompositionno summary yetcs-ds1808.02546Google Research4 citesAug 7, 2018
- AugTesting Graph Clusterability: Algorithms and Lower Boundsno summary yetcs-ds1808.04807Microsoft Research3 citesAug 14, 2018
- AugNon-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexityno summary yetcs-ds1808.06932Google Research17 citesAug 19, 2018
- JulFlow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Modelsno summary yetcs-ds1807.02553Microsoft Research2 citesJul 6, 2018
- JulLearning Sums of Independent Random Variables with Sparse Collective Supportno summary yetcs-ds1807.07013Google Research0 citesJul 18, 2018
- JulSubmodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexityno summary yetcs-ds1807.07889Google Research41 citesJul 20, 2018
- JulRobust Set Reconciliation via Locality Sensitive Hashingno summary yetcs-ds1807.09694Google Research0 citesJul 25, 2018
- JunOptimal Design of Process Flexibility for General Production Systemsno summary yetcs-ds1806.02894Meta / FAIR5 citesJun 7, 2018
- JunDecremental SPQR-trees for Planar Graphsno summary yetcs-ds1806.10772Google Research3 citesJun 28, 2018
- MayCapturing Complementarity in Set Functions by Going Beyond Submodularity/Subadditivityno summary yetcs-ds1805.04436Microsoft Research3 citesMay 11, 2018
- MayWireless coverage prediction via parametric shortest pathsno summary yetcs-ds1805.06420Google Research1 citesMay 16, 2018
- AprOperator Scaling via Geodesically Convex Optimization, Invariant Theory and Polynomial Identity Testingno summary yetcs-ds1804.01076Microsoft Research1 citesApr 3, 2018
- AprGraph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithmno summary yetcs-ds1804.04239Meta / FAIR0 citesApr 11, 2018
- AprDifferentially Private k-Means with Constant Multiplicative Errorno summary yetcs-ds1804.08001Google Research28 citesApr 21, 2018
- FebMinimizing Latency in Online Ride and Delivery Servicesno summary yetcs-ds1802.02744Google Research5 citesFeb 8, 2018
- FebCompetitive caching with machine learned adviceno summary yetcs-ds1802.05399Microsoft Research50 citesFeb 15, 2018
- FebCapacitated Dynamic Programming: Faster Knapsack and Graph Algorithmsno summary yetcs-ds1802.06440Microsoft Research10 citesFeb 18, 2018
- FebMulti-Commodity Flow with In-Network Processingno summary yetcs-ds1802.09118Amazon14 citesFeb 26, 2018
- FebPolynomial Treedepth Bounds in Linear Coloringsno summary yetcs-ds1802.09665Google Research2 citesFeb 27, 2018
2017
13- Novk-server via multiscale entropic regularizationno summary yetcs-ds1711.01085Microsoft Research5 citesNov 3, 2017
- NovOnline Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Modelsno summary yetcs-ds1711.05764Google Research4 citesNov 15, 2017
- OctConvergence Rate of Riemannian Hamiltonian Monte Carlo and Faster Polytope Volume Computationno summary yetcs-ds1710.06261Microsoft Research4 citesOct 17, 2017
- SepDependent randomized rounding for clustering and partition systems with knapsack constraintsno summary yetcs-ds1709.06995Google Research0 citesSep 20, 2017
- AugAverage-case reconstruction for the deletion channel: subpolynomially many traces sufficeno summary yetcs-ds1708.00854Microsoft Research0 citesAug 1, 2017
- AugFinding Subcube Heavy Hitters in Analytics Data Streamsno summary yetcs-ds1708.05159Adobe0 citesAug 17, 2017
- JulRound Compression for Parallel Matching Algorithmsno summary yetcs-ds1707.03478Google Research3 citesJul 11, 2017
- MayDeterminant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Treesno summary yetcs-ds1705.00985Adobe2 citesMay 2, 2017
- MayAlgorithms for $\ell_p$ Low Rank Approximationno summary yetcs-ds1705.06730Google Research5 citesMay 18, 2017
- MayDecremental Single-Source Reachability in Planar Digraphsno summary yetcs-ds1705.11163Google Research0 citesMay 31, 2017
- AprMuch Faster Algorithms for Matrix Scalingno summary yetcs-ds1704.02315Microsoft Research13 citesApr 7, 2017
- AprOnline Weighted Matching: Breaking the $\frac{1}{2}$ Barrierno summary yetcs-ds1704.05384Google Research4 citesApr 18, 2017
- AprBeating 1-1/e for Ordered Prophetsno summary yetcs-ds1704.05836Microsoft Research61 citesApr 19, 2017
2016
21- NovApproximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spannersno summary yetcs-ds1611.00721OpenAI0 citesNov 2, 2016
- NovMultidimensional Binary Search for Contextual Decision-Makingno summary yetcs-ds1611.00829Google Research2 citesNov 2, 2016
- NovSampling Random Spanning Trees Faster than Matrix Multiplicationno summary yetcs-ds1611.07451Google Research0 citesNov 22, 2016
- OctLocal max-cut in smoothed polynomial timeno summary yetcs-ds1610.04807Microsoft Research1 citesOct 16, 2016
- OctAlmost Optimal Streaming Algorithms for Coverage Problemsno summary yetcs-ds1610.08096Google Research4 citesOct 25, 2016
- OctSubquadratic Submodular Function Minimizationno summary yetcs-ds1610.09800Microsoft Research0 citesOct 31, 2016
- OctSubmodular Optimization over Sliding Windowsno summary yetcs-ds1610.09984Google Research0 citesOct 31, 2016
- AugConsistent Hashing with Bounded Loadsno summary yetcs-ds1608.01350Google Research3 citesAug 3, 2016
- AugFaster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and Moreno summary yetcs-ds1608.03270Microsoft Research11 citesAug 10, 2016
- AugGreedy Maximization Framework for Graph-based Influence Functionsno summary yetcs-ds1608.04036Google Research0 citesAug 13, 2016
- JulMultidimensional Dynamic Pricing for Welfare Maximizationno summary yetcs-ds1607.05397Microsoft Research3 citesJul 19, 2016
- JunGeometric Median in Nearly Linear Timeno summary yetcs-ds1606.05225Microsoft Research10 citesJun 16, 2016
- JunMatroid Online Bipartite Matching and Vertex Coverno summary yetcs-ds1606.07863Microsoft Research0 citesJun 25, 2016
- MayGreedy Column Subset Selection: New Bounds and Distributed Algorithmsno summary yetcs-ds1605.08795Google Research31 citesMay 27, 2016
- AprSimultaneous Nearest Neighbor Searchno summary yetcs-ds1604.02188Microsoft Research0 citesApr 7, 2016
- MarNear-Optimal Sample Complexity Bounds for Circulant Binary Embeddingno summary yetcs-ds1603.03178Google Research4 citesMar 10, 2016
- MarFast Scalable Construction of (Minimal Perfect Hash) Functionsno summary yetcs-ds1603.04330Meta / FAIR2 citesMar 14, 2016
- MarRouting under Balanceno summary yetcs-ds1603.09009Microsoft Research0 citesMar 30, 2016
- FebGraphical Model Sketchno summary yetcs-ds1602.03105Adobe1 citesFeb 9, 2016
- FebCompressing Graphs and Indexes with Recursive Graph Bisectionno summary yetcs-ds1602.08820Meta / FAIR110 citesFeb 29, 2016
- JanFirefighting on Trees Beyond Integrality Gapsno summary yetcs-ds1601.00271Microsoft Research12 citesJan 3, 2016
2015
8- NovLearning Communities in the Presence of Errorsno summary yetcs-ds1511.03229Microsoft Research8 citesNov 10, 2015
- NovOn Binary Embedding using Circulant Matricesno summary yetcs-ds1511.06480Snap7 citesNov 20, 2015
- AugA Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regretno summary yetcs-ds1508.03769Google Research5 citesAug 15, 2015
- JulTruthful Online Scheduling with Commitmentsno summary yetcs-ds1507.00773Microsoft Research32 citesJul 2, 2015
- JulA bi-criteria approximation algorithm for $k$ Meansno summary yetcs-ds1507.04227Microsoft Research10 citesJul 15, 2015
- JunRandomized Composable Core-sets for Distributed Submodular Maximizationno summary yetcs-ds1506.06715Google Research10 citesJun 22, 2015
- MayPublic Transit Labelingno summary yetcs-ds1505.01446Microsoft Research6 citesMay 6, 2015
- JanSparse Solutions to Nonnegative Linear Systems and Applicationsno summary yetcs-ds1501.01689Google Research3 citesJan 7, 2015
2014
16- DecNear Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphsno summary yetcs-ds1412.0681Microsoft Research0 citesDec 1, 2014
- DecA Robust and Scalable Algorithm for the Steiner Problem in Graphsno summary yetcs-ds1412.2787Microsoft Research12 citesDec 8, 2014
- NovNearly Linear-Time Packing and Covering LP Solversno summary yetcs-ds1411.1124Microsoft Research2 citesNov 5, 2014
- NovFPTAS for #BIS with Degree Bounds on One Sideno summary yetcs-ds1412.0073Microsoft Research21 citesNov 29, 2014
- AugSpectral Approaches to Nearest Neighbor Searchno summary yetcs-ds1408.0751Microsoft Research6 citesAug 4, 2014
- AugSketch-based Influence Maximization and Computation: Scaling up with Guaranteesno summary yetcs-ds1408.6282Microsoft Research241 citesAug 26, 2014
- AugComputing Classic Closeness Centrality, at Scaleno summary yetcs-ds1409.0035Microsoft Research71 citesAug 29, 2014
- JulDictionary Learning and Tensor Decomposition via the Sum-of-Squares Methodno summary yetcs-ds1407.1543Microsoft Research5 citesJul 6, 2014
- JulLP-Based Algorithms for Capacitated Facility Locationno summary yetcs-ds1407.3263Microsoft Research6 citesJul 11, 2014
- JulIgnorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queriesno summary yetcs-ds1407.4094Microsoft Research35 citesJul 15, 2014
- JulOn the String Consensus Problem and the Manhattan Sequence Consensus Problemno summary yetcs-ds1407.6144OpenAI0 citesJul 23, 2014
- MayAdaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problemsno summary yetcs-ds1405.2875Microsoft Research6 citesMay 12, 2014
- AprApproximating the Regular Graphic TSP in near linear timeno summary yetcs-ds1404.2396Amazon0 citesApr 9, 2014
- AprMultiplicative Bidding in Online Advertisingno summary yetcs-ds1404.6727Google Research0 citesApr 27, 2014
- FebOptimal Gossip with Direct Addressingno summary yetcs-ds1402.2701Microsoft Research4 citesFeb 12, 2014
- FebFPTAS for Weighted Fibonacci Gates and Its Applicationsno summary yetcs-ds1402.4370Microsoft Research0 citesFeb 18, 2014
2013
21- DecBandits and Experts in Metric Spacesno summary yetcs-ds1312.1277Microsoft Research12 citesDec 4, 2013
- DecRounding Sum-of-Squares Relaxationsno summary yetcs-ds1312.6652Microsoft Research0 citesDec 23, 2013
- DecLocal algorithms for interactive clusteringno summary yetcs-ds1312.6724Google Research34 citesDec 24, 2013
- NovSmoothed Analysis of Tensor Decompositionsno summary yetcs-ds1311.3651Google Research11 citesNov 14, 2013
- OctFinding Dominators via Disjoint Set Unionno summary yetcs-ds1310.2118Microsoft Research0 citesOct 8, 2013
- SepPartition-Merge: Distributed Inference and Modularity Optimizationno summary yetcs-ds1309.6129DeepMind1 citesSep 24, 2013
- AugEfficient Algorithms for Privately Releasing Marginals via Convex Relaxationsno summary yetcs-ds1308.1385Microsoft Research6 citesAug 6, 2013
- JulAn efficient reconciliation algorithm for social networksno summary yetcs-ds1307.1690Google Research3 citesJul 5, 2013
- JulOn the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machinesno summary yetcs-ds1307.6505Meta / FAIR0 citesJul 24, 2013
- JunMatching with our Eyes Closedno summary yetcs-ds1306.2988Google Research0 citesJun 12, 2013
- MaySparsest Cut on Bounded Treewidth Graphs: Algorithms and Hardness Resultsno summary yetcs-ds1305.1347Microsoft Research15 citesMay 6, 2013
- MayBandits with Knapsacksno summary yetcs-ds1305.2545Microsoft Research214 citesMay 11, 2013
- AprImproved ARV Rounding in Small-set Expanders and Graphs of Bounded Threshold Rankno summary yetcs-ds1304.2060Microsoft Research0 citesApr 7, 2013
- AprAlgorithms for Cut Problems on Treesno summary yetcs-ds1304.3653Google Research0 citesApr 12, 2013
- AprPersonalized PageRank to a Target Nodeno summary yetcs-ds1304.4658Google Research26 citesApr 17, 2013
- AprUniqueness of Tensor Decompositions with Applications to Polynomial Identifiabilityno summary yetcs-ds1304.8087Google Research35 citesApr 30, 2013
- AprEntropy, Optimization and Countingno summary yetcs-ds1304.8108Microsoft Research5 citesApr 30, 2013
- AprLocal Graph Clustering Beyond Cheeger's Inequalityno summary yetcs-ds1304.8132Google Research28 citesApr 30, 2013
- FebMinimum length path decompositionsno summary yetcs-ds1302.2788DeepMind4 citesFeb 12, 2013
- JanMatroid and Knapsack Center Problemsno summary yetcs-ds1301.0745Meta / FAIR5 citesJan 4, 2013
- JanA Dynamic Programming Solution to a Generalized LCS Problemno summary yetcs-ds1301.7183Microsoft Research0 citesJan 30, 2013
2012
10- DecThe Geometry of Differential Privacy: the Sparse and Approximate Casesno summary yetcs-ds1212.0297Microsoft Research100 citesDec 3, 2012
- NovOnline Stochastic Bin Packingno summary yetcs-ds1211.2687Google Research25 citesNov 12, 2012
- OctLocal Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPsno summary yetcs-ds1210.1890Microsoft Research3 citesOct 5, 2012
- OctLow-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regressionno summary yetcs-ds1210.3135LinkedIn13 citesOct 11, 2012
- JulOn Privacy-Preserving Histogramsno summary yetcs-ds1207.1371Microsoft Research14 citesJul 4, 2012
- JunApproximation Algorithm for Non-Boolean MAX k-CSPno summary yetcs-ds1206.3603Microsoft Research1 citesJun 15, 2012
- AprPrivacy via the Johnson-Lindenstrauss Transformno summary yetcs-ds1204.2606Microsoft Research105 citesApr 12, 2012
- MarSHALE: An Efficient Algorithm for Allocation of Guaranteed Display Advertisingno summary yetcs-ds1203.3619Meta / FAIR6 citesMar 16, 2012
- MarDistance Queries from Sampled Data: Accurate and Efficientno summary yetcs-ds1203.4903Microsoft Research1 citesMar 22, 2012
- MarOnline Mixed Packing and Coveringno summary yetcs-ds1203.6695Microsoft Research43 citesMar 30, 2012
2011
6- NovComputing a Nonnegative Matrix Factorization -- Provablyno summary yetcs-ds1111.0952Microsoft Research8 citesNov 3, 2011
- AugOptimal Indexes for Sparse Bit Vectorsno summary yetcs-ds1108.2157Google Research0 citesAug 10, 2011
- JulThe Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problemsno summary yetcs-ds1107.2188Microsoft Research2 citesJul 12, 2011
- JunAn Efficient Partitioning Oracle for Bounded-Treewidth Graphsno summary yetcs-ds1106.4587Google Research0 citesJun 22, 2011
- AprRounding Semidefinite Programming Hierarchies via Global Correlationno summary yetcs-ds1104.4680Microsoft Research6 citesApr 25, 2011
- MarStratified B-trees and versioning dictionariesno summary yetcs-ds1103.4282Google Research12 citesMar 22, 2011
2010
7- OctEnergy-Efficient Multiprocessor Scheduling for Flow Time and Makespanno summary yetcs-ds1010.4110Microsoft Research7 citesOct 20, 2010
- SepApproximability of Capacitated Network Designno summary yetcs-ds1009.5734Google Research3 citesSep 29, 2010
- AugPrediction strategies without lossno summary yetcs-ds1008.3672Microsoft Research12 citesAug 22, 2010
- JulOnline Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocationsno summary yetcs-ds1007.1271Google Research140 citesJul 8, 2010
- JunApproximating Sparsest Cut in Graphs of Bounded Treewidthno summary yetcs-ds1006.3970Microsoft Research10 citesJun 21, 2010
- MarConstrained Non-Monotone Submodular Maximization: Offline and Secretary Algorithmsno summary yetcs-ds1003.1517Microsoft Research5 citesMar 7, 2010
- JanOnline Stochastic Packing Applied to Display Ad Allocationno summary yetcs-ds1001.5076Google Research39 citesJan 28, 2010
2009
5- DecRobust Fault Tolerant uncapacitated facility locationno summary yetcs-ds0912.3188Microsoft Research0 citesDec 16, 2009
- AugDeterministic Algorithms for the Lovasz Local Lemmano summary yetcs-ds0908.0375Microsoft Research1 citesAug 4, 2009
- JulContextual Bandits with Similarity Informationno summary yetcs-ds0907.3986Microsoft Research255 citesJul 23, 2009
- JunApproximating Scheduling Machines with Capacity Constraintsno summary yetcs-ds0906.3056Baidu0 citesJun 17, 2009
- MayOnline Stochastic Matching: Beating 1-1/eno summary yetcs-ds0905.4100Google Research40 citesMay 26, 2009
2008
8- NovPhase transition for Local Search on planted SATno summary yetcs-ds0811.2546Google Research5 citesNov 16, 2008
- NovFinding Sparse Cuts Locally Using Evolving Setsno summary yetcs-ds0811.3779Microsoft Research1 citesNov 23, 2008
- SepMulti-Armed Bandits in Metric Spacesno summary yetcs-ds0809.4882Microsoft Research44 citesSep 29, 2008
- JulRange Mediansno summary yetcs-ds0807.0222Google Research6 citesJul 1, 2008
- JulBloomier Filters: A second lookno summary yetcs-ds0807.0928Microsoft Research5 citesJul 6, 2008
- JulAlgorithms for Secretary Problems on Graphs and Hypergraphsno summary yetcs-ds0807.1139Google Research3 citesJul 7, 2008
- AprTruthful Unsplittable Flow for Large Capacity Networksno summary yetcs-ds0804.2112Microsoft Research0 citesApr 14, 2008
- MarAdmission Control to Minimize Rejections and Online Set Cover with Repetitionsno summary yetcs-ds0803.2842Microsoft Research0 citesMar 19, 2008
2007
4- DecA Partition-Based Relaxation For Steiner Treesno summary yetcs-ds0712.3568Microsoft Research0 citesDec 20, 2007
- NovData Structures for Mergeable Treesno summary yetcs-ds0711.1682Microsoft Research0 citesNov 11, 2007
- OctFaster Least Squares Approximationno summary yetcs-ds0710.1435Google Research16 citesOct 7, 2007
- JunRadix Sorting With No Extra Spaceno summary yetcs-ds0706.4107Google Research0 citesJun 27, 2007