p7cs.DM

cs.DM

54 papers

Sparser Johnson-Lindenstrauss Transforms

Daniel M. Kane, Jelani Nelson

1012.1577

Fast approximation of matrix coherence and statistical leverage

Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, David P. Woodruff

1109.3843

Phase Transitions in Semidefinite Relaxations

Adel Javanmard, Andrea Montanari, Federico Ricci-Tersenghi

1511.08769

Twice-Ramanujan Sparsifiers

Joshua Batson, Daniel A. Spielman, Nikhil Srivastava

0808.0163

A Topological Characterization of Modulo-$p$ Arguments and Implications for Necklace Splitting

Aris Filos-Ratsikas, Alexandros Hollender, Katerina Sotiraki, Manolis Zampetakis

2003.11974

Bipartite Perfect Matching is in quasi-NC

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

1601.06319

Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack

Anna R. Karlin, Claire Mathieu, C. Thach Nguyen

1007.1283

Signals on Graphs: Uncertainty Principle and Sampling

Mikhail Tsitsvero, Sergio Barbarossa, Paolo Di Lorenzo

1507.08822

Graphical Cake Cutting via Maximin Share

Edith Elkind, Erel Segal-Halevi, Warut Suksompong

2105.04755

Proof of the satisfiability conjecture for large k

Jian Ding, Allan Sly, Nike Sun

1411.0650

On the limitation of spectral methods: From the Gaussian hidden clique problem to rank one perturbations of Gaussian tensors

Andrea Montanari, Daniel Reichman, Ofer Zeitouni

1411.6149

Supersparse Linear Integer Models for Optimized Medical Scoring Systems

Berk Ustun, Cynthia Rudin

1502.04269

Finding Hidden Cliques in Linear Time with High Probability

Yael Dekel, Ori Gurel-Gurevich, Yuval Peres

1010.2997

Toward An Uncertainty Principle For Weighted Graphs

Bastien Pasdeloup, Réda Alami, Vincent Gripon, Michael Rabbat

1503.03291

Communities in Networks

Mason A. Porter, Jukka-Pekka Onnela, Peter J. Mucha

0902.3788

The condensation phase transition in random graph coloring

Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Rassmann, Dan Vilenchik

1404.5513

Multi-channel Opportunistic Access: A Case of Restless Bandits with Multiple Plays

Sahand Haji Ali Ahmad, Mingyan Liu

0910.1954

Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs

Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra

1610.02704

Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials

Viresh Patel, Guus Regts

1607.01167

Dividing a Graphical Cake

Xiaohui Bei, Warut Suksompong

1910.14129

A counterexample to the Hirsch conjecture

Francisco Santos

1006.2814

Upper-bounding the k-colorability threshold by counting covers

Amin Coja-Oghlan

1305.0177

Extremal results in sparse pseudorandom graphs

David Conlon, Jacob Fox, Yufei Zhao

1204.6645

Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time

Yin Tat Lee, He Sun

1508.03261

Nearly Tight Low Stretch Spanning Trees

Ittai Abraham, Yair Bartal, Ofer Neiman

0808.2017

On the Complexity of Random Satisfiability Problems with Planted Solutions

Vitaly Feldman, Will Perkins, Santosh Vempala

1311.4821

On the method of typical bounded differences

Lutz Warnke

1212.5796

Fast Semidifferential-based Submodular Function Optimization

Rishabh Iyer, Stefanie Jegelka, Jeff Bilmes

1308.1006

Subgraph Sparsification and Nearly Optimal Ultrasparsifiers

Alexandra Kolla, Yury Makarychev, Amin Saberi, Shanghua Teng

0912.1623

The domination number of on-line social networks and random geometric graphs

Anthony Bonato, Marc Lozier, Dieter Mitsche, Xavier Pérez-Giménez, Paweł Prałat

1412.1189

A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions

Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan

0909.4727

Reconstruction for Powerful Graph Representations

Leonardo Cotta, Christopher Morris, Bruno Ribeiro

2110.00577

Efficient computation of approximate pure Nash equilibria in congestion games

Ioannis Caragiannis, Angelo Fanelli, Nick Gravin, Alexander Skopalik

1104.2690

Constructive Algorithms for Discrepancy Minimization

Nikhil Bansal

1002.2259

Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions

Rishabh Iyer, Stefanie Jegelka, Jeff Bilmes

1311.2110

Computing the Independence Polynomial: from the Tree Threshold down to the Roots

Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák

1608.02282

Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints

Rishabh Iyer, Jeff Bilmes

1311.2106

Spectral Sparsification of Graphs

Daniel A. Spielman, Shang-Hua Teng

0808.4134

The Price of Connectivity in Fair Division

Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, Warut Suksompong

1908.05433

Chasing the k-colorability threshold

Amin Coja-Oghlan, Dan Vilenchik

1304.1063

Combining geometry and combinatorics: A unified approach to sparse signal recovery

R. Berinde, A. C. Gilbert, P. Indyk, H. Karloff, M. J. Strauss

0804.4666

The statistical restricted isometry property and the Wigner semicircle distribution of incoherent dictionaries

Shamgar Gurevich, Ronny Hadani

0812.2602

A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning

Daniel A. Spielman, Shang-Hua Teng

0809.3232

Lower bounds for oblivious subspace embeddings

Jelani Nelson, Huy L. Nguyen

1308.3280

Going after the k-SAT Threshold

Amin Coja-Oghlan, Konstantinos Panagiotou

1212.1682

On the chromatic number of a random hypergraph

Martin Dyer, Alan Frieze, Catherine Greenhill

1208.0812

The Bethe Partition Function of Log-supermodular Graphical Models

Nicholas Ruozzi

1202.6035

Catching the k-NAESAT Threshold

Amin Coja-Oghlan, Konstantinos Panagiotou

1111.1274

On independent sets in random graphs

Amin Coja-Oghlan, Charilaos Efthymiou

1007.1378

Factor models on locally tree-like graphs

Amir Dembo, Andrea Montanari, Nike Sun

1110.4821

Entropy, Optimization and Counting

Mohit Singh, Nisheeth K. Vishnoi

1304.8108

Matching is as Easy as the Decision Problem, in the NC Model

Nima Anari, Vijay V. Vazirani

1901.10387

The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains

David I Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, Pierre Vandergheynst

1211.0053

On belief propagation guided decimation for random k-SAT

Amin Coja-Oghlan

1007.1328