Integer Feasibility of Random Polytopes

On the significance of solving some linear programs with some integer variables

G. Dantzig · 1960

Earlier work this paper cites.

Reducibility among combinatorial problems

R. Karp · 1972

Earlier work this paper cites.

Six standard deviations suffice

J. Spencer · 1985

Earlier work this paper cites.

Probabilistic analysis of two heuristics for the 3-satisfiability problem

M. T. Chao and J. Franco · 1986

Earlier work this paper cites.

Discrepancy of set-systems and matrices

L. Lovász, J. Spencer, and K. Vesztergombi · 1986

Earlier work this paper cites.

Minkowski’s convex body theorem and integer programming

R. Kannan · 1987

Earlier work this paper cites.

Ten lectures on the probabilistic method

J. Spencer · 1987

Earlier work this paper cites.

Succinct certificates for almost all subset sum problems

M. L. Furst and R. Kannan · 1989

Earlier work this paper cites.

Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k k -satisfiability problem

M. T. Chao and J. Franco · 1990

Cited alongside, same era.

Mick gets some (the odds are on his side)

V. Chvátal and B. Reed · 1992

Cited alongside, same era.

On the satisfiability and maximum satisfiability of random 3-cnf formulas

A. Broder, A. Frieze, and E. Upfal · 1993

Cited alongside, same era.

Discrepancy in arithmetic progressions

J. Matoušek and J. Spencer · 1996

Cited alongside, same era.

Sharp thresholds of graph properties and the k-sat problem

E. Friedgut · 1998

Cited alongside, same era.

An Lp version of the Beck-Fiala conjecture

J. Matoušek · 1998

Cited alongside, same era.

A two-round variant of em for gaussian mixtures

S. Dasgupta and L. J. Schulman · 2000

Later among the works it cites.

Random graphs

B. Bollobás · 2001

Later among the works it cites.

Random knapsack in expected polynomial time

R. Beier and B. Vöcking · 2003

Later among the works it cites.

Basis reduction and the complexity of branch-and-bound

G. Pataki, M. Tural, and E. B. Wong · 2010

Later among the works it cites.

Tight hardness for minimizing discrepancy

M. Charikar, A. Newman, and A. Nikolov · 2011

Closest in time.

Constructive discrepancy minimization by walking on the edges

S. Lovett and R. Meka · 2012

Closest in time.

The geometry of differential privacy: the sparse and approximate cases