On the diameter of the set of satisfying assignments in random satisfiable k-CNF formulas (2009)
Feige, Uriel, Flaxman, Abraham D., Vilenchik, Dan
It is known that random k-CNF formulas have a so-called satisfiability threshold at a density (namely, clause-variable ratio) of roughly 2^k\ln 2: at densities slightly below this threshold almost...
complex networks. This has been the case since time immemorial. But only recently has technology allowed us to record the structure of these huge networks and use this information in decision making....
Angel, Omer, Flaxman, Abraham D., Wilson, David B.
In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to...
Maximum matchings in regular graphs of high girth (2008)
Abraham D. Flaxman, Shlomo Hoory
Let G = (V, E) be any d-regular graph with girth g on n vertices, for d ≥ 3. This note shows that G has a maximum matching which includes all but an exponentially small fraction of the vertices,...
Algorithms for random 3-SAT (2008)
This classic problem in complexity theory is concerned with efficiently finding a satisfying assignment to a propositional formula. The input is a formula with n Boolean variables which is expressed...
Abraham D. Flaxman, Juan Carlos Vera, Alan M. Frieze
In combinatorial optimization, a popular approach to NP-hard problems is the design of approximation algorithms. These algorithms typically run in polynomial time and are guaranteed to produce a...
In combinatorial optimization, a popular approach to NPhard problems is the design of approximation algorithms. These algorithms typically run in polynomial time and are guaranteed to produce a...
Abraham D. Flaxman, Michael Krivelevich
It is known [6] that if the edge costs of the complete graph K n are independent random variables, uniformly distributed between 0 and 1, then the expected cost of the minimum spanning tree is...
Abraham D. Flaxman, Alan M. Frieze
diameter of randomly perturbed digraphs and some applications
Bias reduction in traceroute sampling: towards a more accurate map of the Internet (2007)
Flaxman, Abraham D., Vera, Juan
Traceroute sampling is an important technique in exploring the internet router graph and the autonomous system graph. Although it is one of the primary techniques used in calculating statistics about...
Bias reduction in traceroute sampling: towards a more accurate map of the Internet (2007)
Abraham D. Flaxman, Juan Vera, Redmond Wa
Abstract. Traceroute sampling is an important technique in exploring the internet router graph and the autonomous system graph. Although it is one of the primary techniques used in calculating...
Presented to The Academic Faculty (2006)
Abraham D. Flaxman, Alan Frieze, R. Ravi, Manuel Blum, Luis Von Ahn, Maverick Woo, ...
This thesis considers the average case analysis of algorithms, focusing primarily on NP-hard combinatorial optimization problems. It includes a catalog of distributions frequently used in...
Solving medium-density subset sum problems in expected polynomial time (2005)
Abraham D. Flaxman, Bartosz Przydatek
The subset sum problem (SSP) (given n numbers and a target bound B, find a subset of the numbers summing to B), is one of the classical NP-hard problems. The hardness of SSP varies greatly with the...
Clifford Smyth, Abraham D. Flaxman
A permutation sum (resp. difference) set on a group G is a set F of bijections from G to G such that fg (resp. f −1g) is again a bijection for all f,g ∈ F (resp. f,g ∈ F with f � = g ∈ S),...
Martin Dyer, Abraham D. Flaxman, Alan M. Frieze, Eric Vigoda
coloring sparse random graphs with fewer colors than
Martin Dyer, Abraham D. Flaxman, Alan M. Frieze, Eric Vigoda
coloring sparse random graphs with fewer colors than
Online convex optimization in the bandit setting: gradient descent without a gradient (2004)
Flaxman, Abraham D., Kalai, Adam Tauman, McMahan, H. Brendan
We consider a the general online convex optimization framework introduced by Zinkevich. In this setting, there is a sequence of convex functions. Each period, we must choose a signle point (from some...
A Geometric Preferential Attachment Model of Networks (2004)
Abraham D. Flaxman, Alan M. Frieze, Juan Vera
We study a random graph Gn that combines certain aspects of geometric random graphs and preferential attachment graphs. This model yields a graph with power-law degree distribution where the...
A Geometric Preferential Attachment Model of Networks (2004)
Abraham D. Flaxman, Alan M. Frieze, Juan Vera
We study a random graph Gn that combines certain aspects of geometric random graphs and preferential attachment graphs. This model yields a graph with power-law degree distribution where the...