p7math.CO

math.CO

113 papers

Algebraic Graph Theory

M Reza Salarian

2604.20890

Neural network identifiability for a family of sigmoidal nonlinearities

Verner Vlačić, Helmut Bölcskei

1906.06994

Much Faster Algorithms for Matrix Scaling

Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Oliveira, Avi Wigderson

1704.02315

Random weighted projections, random quadratic forms and random eigenvectors

Van Vu, Ke Wang

1306.3099

Sum-of-squares lower bounds for planted clique

Raghu Meka, Aaron Potechin, Avi Wigderson

1503.06447

Exponential approximation and Stein's method of exchangeable pairs

Jason Fulman, Nathan Ross

1207.5073

Stochastic Block Models and Reconstruction

Elchanan Mossel, Joe Neeman, Allan Sly

1202.1499

Lower bounds on the size of semidefinite programming relaxations

James R. Lee, Prasad Raghavendra, David Steurer

1411.6317

On the singularity probability of discrete random matrices

Jean Bourgain, Van Vu, Philip Matchett Wood

0905.0461

Random matrices: The distribution of the smallest singular values

Terence Tao, Van Vu

0903.0614

Three Puzzles on Mathematics, Computation, and Games

Gil Kalai

1801.02602

The Non-Backtracking Spectrum of the Universal Cover of a Graph

Omer Angel, Joel Friedman, Shlomo Hoory

0712.0192

A Fourier-analytic Approach to Counting Partial Hadamard Matrices

Warwick de Launey, David A. Levin

1003.4003

Mutually unbiased triplets from non-affine families of complex Hadamard matrices in dimension six

D. Goyeneche

1209.4126

Construction, classification and parametrization of complex Hadamard matrices

Ferenc Szöllősi

1110.5590

SIC-POVMs: A new computer study

A. J. Scott, M. Grassl

0910.5784

Limits of local-global convergent graph sequences

Hamed Hatami, László Lovász, Balázs Szegedy

1205.4356

The Matching Problem in General Graphs is in Quasi-NC

Ola Svensson, Jakub Tarnawski

1704.01929

Approximating Continuous Functions by ReLU Nets of Minimal Width

Boris Hanin, Mark Sellke

1710.11278

The Hirsch conjecture holds for normal flag complexes

Karim Alexander Adiprasito, Bruno Benedetti

1303.3598

A simple SVD algorithm for finding hidden partitions

Van Vu

1404.3918

Nonparametric graphon estimation

Patrick J. Wolfe, Sofia C. Olhede

1309.5936

Stein's method and the rank distribution of random matrices over finite fields

Jason Fulman, Larry Goldstein

1211.0504

Finding Hidden Cliques in Linear Time with High Probability

Yael Dekel, Ori Gurel-Gurevich, Yuval Peres

1010.2997

Graph Expansion and Communication Costs of Fast Matrix Multiplication

Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz

1109.1693

Communication is bounded by root of rank

Shachar Lovett

1306.1877

Approximating permanents and hafnians

Alexander Barvinok

1601.07518

Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs

Samir Datta, Raghav Kulkarni, Sambuddha Roy

0802.2850

Littlewood-Richardson polynomials

A. I. Molev

0704.0065

On replica symmetry of large deviations in random graphs

Eyal Lubetzky, Yufei Zhao

1210.7013

Co-clustering separately exchangeable network data

David Choi, Patrick J. Wolfe

1212.4093

Local algorithms for independent sets are half-optimal

Mustazee Rahman, Balint Virag

1402.0485

The condensation phase transition in random graph coloring

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

1404.5513

On Pseudocyclic Association Schemes

M. E. Muzychuk, I. N. Ponomarenko

0910.0682

Large deviations of empirical neighborhood distribution in sparse random graphs

Charles Bordenave, Pietro Caputo

1308.5725

Pipage Rounding, Pessimistic Estimators and Matrix Concentration

Nicholas J. A. Harvey, Neil Olver

1307.2274

Random graphs with a given degree sequence

Sourav Chatterjee, Persi Diaconis, Allan Sly

1005.1136

The Satisfiability Threshold for k-XORSAT

Boris Pittel, Gregory B. Sorkin

1212.1905

Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges

Roberto Imbuzeiro Oliveira

0911.0600

Strong Scaling of Matrix Multiplication Algorithms and Memory-Independent Communication Lower Bounds

Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz

1202.3177

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

Local semicircle law for random regular graphs

Roland Bauerschmidt, Antti Knowles, Horng-Tzer Yau

1503.08702

Ramanujan graphings and correlation decay in local algorithms

Agnes Backhausz, Balazs Szegedy, Balint Virag

1305.6784

On reverse hypercontractivity

Elchanan Mossel, Krzysztof Oleszkiewicz, Arnab Sen

1108.1210

Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes

Adam W. Marcus, Nikhil Srivastava, Daniel A. Spielman

1505.08010

Maximum entropy Gaussian approximation for the number of integer points and volumes of polytopes

Alexander Barvinok, John Hartigan

0903.5223

On combinatorial testing problems

Louigi Addario-Berry, Nicolas Broutin, Luc Devroye, Gábor Lugosi

0908.3437

A counterexample to the Hirsch conjecture

Francisco Santos

1006.2814

Spectra of general hypergraphs

Anirban Banerjee, Arnab Char, Bibhash Mondal

1601.02136

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

The classification of tensor categories of two-colored noncrossing partitions

Pierre Tarrago, Moritz Weber

1509.00988

Communication-Optimal Parallel Algorithm for Strassen's Matrix Multiplication

Grey Ballard, James Demmel, Olga Holtz, Benjamin Lipshitz, Oded Schwartz

1202.3173

Phase transitions in exponential random graphs

Charles Radin, Mei Yin

1108.0649

On the Complexity of Random Satisfiability Problems with Planted Solutions

Vitaly Feldman, Will Perkins, Santosh Vempala

1311.4821

Faster all-pairs shortest paths via circuit complexity

Ryan Williams

1312.6680

The determinant bound for discrepancy is almost tight

Jiri Matousek

1101.0767

On the method of typical bounded differences

Lutz Warnke

1212.5796

Invariant Gaussian processes and independent sets on regular graphs of large girth

Endre Csóka, Balázs Gerencsér, Viktor Harangi, Bálint Virág

1305.3977

On locally constructible spheres and balls

Bruno Benedetti, Günter M. Ziegler

0902.0436

The solution space geometry of random linear equations

Dimitris Achlioptas, Michael Molloy

1107.5550

Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees

Adam Marcus, Daniel A. Spielman, Nikhil Srivastava

1304.4132

Cored Hypergraphs, Power Hypergraphs and Their Laplacian H-Eigenvalues

Shenglong Hu, Liqun Qi, Jia-Yu Shao

1304.6839

Independence ratio and random eigenvectors in transitive graphs

Viktor Harangi, Bálint Virág

1308.5173

Approximation Limits of Linear Programs (Beyond Hierarchies)

Gábor Braun, Samuel Fiorini, Sebastian Pokutta, David Steurer

1204.0957

A Refined Laser Method and Faster Matrix Multiplication

Josh Alman, Virginia Vassilevska Williams

2010.05846

On a conjecture of Sokal concerning roots of the independence polynomial

Han Peters, Guus Regts

1701.08049

Sparse graphs: metrics and random models

Bela Bollobas, Oliver Riordan

0812.2656

On the KŁR conjecture in random graphs

D. Conlon, W. T. Gowers, W. Samotij, M. Schacht

1305.2516

Computing inclusions of Schur modules

Steven V Sam

0810.4666

On a {K_4,K_{2,2,2}}-ultrahomogeneous graph

Italo J. Dejter

0704.1493

An update on the Hirsch conjecture

Edward D. Kim, Francisco Santos

0907.1186

Exponential Lower Bounds for Polytopes in Combinatorial Optimization

Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, Ronald de Wolf

1111.0837

Perfect Matchings as IID Factors on Non-Amenable Groups

Russell Lyons, Fedor Nazarov

0911.0092

The lower tail: Poisson approximation revisited

Svante Janson, Lutz Warnke

1406.1248

Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes

Alexander Barvinok

0709.3810

On the number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

Alexander Barvinok

0806.1480

The measurable Kesten theorem

Miklos Abert, Yair Glasner, Balint Virag

1111.2080

Hyperbolicity and stable polynomials in combinatorics and probability

Robin Pemantle

1210.3231

Multivariate Fuss-Catalan numbers

Jean-Christophe Aval

0711.0906

Algorithmic barriers from phase transitions

Dimitris Achlioptas, Amin Coja-Oghlan

0803.2122

Constructive Algorithms for Discrepancy Minimization

Nikhil Bansal

1002.2259

Independent sets in hypergraphs

József Balogh, Robert Morris, Wojciech Samotij

1204.6530

Regular Uniform Hypergraphs, $s$-Cycles, $s$-Paths and Their largest Laplacian H-Eigenvalues

Liqun Qi, Jiayu Shao, Qun Wang

1309.2163

The Class of Random Graphs Arising from Exchangeable Random Measures

Victor Veitch, Daniel M. Roy

1512.03099

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

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

1608.02282

The quaternary complex Hadamard matrices of orders 10, 12, and 14

Pekka H. J. Lampio, Ferenc Szöllősi, Patric R. J. Östergård

1204.5164

Degree sequences of random digraphs and bipartite graphs

Brendan D. McKay, Fiona Skerman

1302.2446

Words Maps and Spectra of Random Graph Lifts

Nati Linial, Doron Puder

0806.1993

Planar Graph Perfect Matching is in NC

Nima Anari, Vijay V. Vazirani

1709.07822

Poisson Cloning Model for Random Graphs

Jeong Han Kim

0805.4133

Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces

Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi

1708.02222

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

Zero-free regions of partition functions with applications to algorithms and graph limits

Guus Regts

1507.02089

Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division

Elad Aigner-Horev, Erel Segal-Halevi

1901.09527

The cut metric, random graphs, and branching processes

Bela Bollobas, Svante Janson, Oliver Riordan

0901.2091

Graph limits and exchangeable random graphs

Persi Diaconis, Svante Janson

0712.2749

Testing properties of graphs and functions

Laszlo Lovasz, Balazs Szegedy

0803.1248

A refinement of the Cameron-Erdős Conjecture

Noga Alon, József Balogh, Robert Morris, Wojciech Samotij

1202.5200

Counting sum-free sets in Abelian groups

Noga Alon, József Balogh, Robert Morris, Wojciech Samotij

1201.6654

Combinatorial theorems in sparse random sets

D. Conlon, W. T. Gowers

1011.4310

On phase transition in the hard-core model on ${\bf Z}^d$

David Galvin, Jeff Kahn

1206.3144

Decompositions, approximate structure, transference, and the Hahn-Banach theorem

W. T. Gowers

0811.3103

An inverse theorem for the uniformity seminorms associated with the action of $F^ω$

Vitaly Bergelson, Terence Tao, Tamar Ziegler

0901.2602

The inverse conjecture for the Gowers norm over finite fields via the correspondence principle

Terence Tao, Tamar Ziegler

0810.5527

Going after the k-SAT Threshold

Amin Coja-Oghlan, Konstantinos Panagiotou

1212.1682

Computing the partition function for graph homomorphisms

Alexander Barvinok, Pablo Soberón

1406.1771

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

Entropy, Optimization and Counting

Mohit Singh, Nisheeth K. Vishnoi

1304.8108