Easily refutable subformulas of large random 3CNF formulas (2009)
Abstract. A simple nonconstructive argument shows that most 3CNF formulas with cn clauses (where c is a large enough constant) are not satisfiable. It is an open question whether there is an...
ABSTRACT Routing Complexity of Faulty Networks (2009)
Omer Angel, Eran Ofek, Itai Benjamini
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the...
Easily refutable subformulas of large random 3CNF formulas (2008)
A simple nonconstructive argument shows that most CNF formulas with Ò clauses (where is a large enough constant) are not satisfiable. It is an open question whether there is an efficient refutation...
ABSTRACT Routing Complexity of Faulty Networks (2008)
Omer Angel, Eran Ofek, Itai Benjamini
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the...
A comprehensive study of GRB 070125, a most energetic gamma ray burst (2008)
Chandra, Poonam, Cenko, S. Bradley, Frail, Dale, Chevalier, Roger, Macquart, Jean-Pierre, Kulkarni, Shri, ...
We present a comprehensive multiwavelength analysis of the bright, long duration gamma-ray burst GRB 070125, comprised of observations in $\gamma$-ray, X-ray, optical, millimeter and centimeter...
Cenko, S. Bradley, Berger, Edo, Nakar, Ehud, Kasliwal, Mansi M., Cucchiara, Antonio, Kulkarni, Shri R., ...
We present optical spectra of the host galaxies of the short-duration gamma-ray burst GRB 070429B and the likely short-duration with extended emission GRB 070714B. In both cases, we find a single...
Geodesics and almost geodesic cycles in random regular graphs (2006)
Benjamini, Itai, Hoppen, Carlos, Ofek, Eran, Pralat, Pawel, Wormald, Nick
A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and...
Random 3CNF formulas elude the Lovasz theta function (2006)
Let $\phi$ be a 3CNF formula with n variables and m clauses. A simple nonconstructive argument shows that when m is sufficiently large compared to n, most 3CNF formulas are not satisfiable. It is an...
Finding a maximum independent set in a sparse random graph (2006)
We consider the problem of finding a maximum independent set in a random graph. The random graph G, which contains n vertices, is modelled as follows. Every edge is included independently with...
Random 3CNF formulas elude the Lovasz theta function (2006)
Let φ be a 3CNF formula with n variables and m clauses. A simple nonconstructive argument shows that when m is sufficiently large compared to n, most 3CNF formulas are not satisfiable. It is an open...
On the expansion of the giant component in percolated (n, d, λ) graphs (2006)
Let d ≥ d0 be a sufficiently large constant. A (n, d, c √ d) graph G is a d-regular graph over n vertices whose second largest (in absolute value) eigenvalue is at most c √ d. For any 0 < p...
Finding a maximum independent set in a sparse random graph (2006)
We consider the problem of finding a maximum independent set in a random graph. The random graph G is modelled as follows. Every edge is included independently with probability d n, where d is some...
Random 3CNF formulas elude the Lovasz theta function (2006)
Let φ be a 3CNF formula with n variables and m clauses. A simple nonconstructive argument shows that when m is sufficiently large compared to n, most 3CNF formulas are not satisfiable. It is an open...
Finding a maximum independent set in a sparse random graph (2006)
We consider the problem of finding a maximum independent set in a random graph. The random graph G is modelled as follows. Every edge is included independently with probability d, where d is some...
Witnesses for non-satisfiability of dense random 3CNF formulas (2006)
Uriel Feige, Jeong Han Kim, Eran Ofek
We consider random 3CNF formulas with n variables and m clauses. It is well known that when m> cn (for a sufficiently large constant c), most formulas are not satisfiable. However, it is not known...
Finding a maximum independent set in a sparse random graph (2006)
We consider the problem of finding a maximum independent set in a random graph. The random graph G is modelled as follows. Every edge is included independently with probability d, where d is some...
Random 3CNF formulas elude the Lovasz theta function (2006)
Let φ be a 3CNF formula with n variables and m clauses. A simple nonconstructive argument shows that when m is sufficiently large compared to n, most 3CNF formulas are not satisfiable. It is an open...
Finding a maximum independent set in a sparse random graph (2006)
We consider the problem of finding a maximum independent set in a random graph. The random graph G is modelled as follows. Every edge is included independently with probability d, where d is some...
Random 3CNF formulas elude the Lovasz theta function (2006)
1 Introduction A 3CNF formula OE over n variables is a set of m clauses, where each clausecontains exactly 3 literals. A formula OE is satisfiable if there is an assignmentto its n variables that...
The Progenitors of Short-Hard Gamma-Ray Bursts from an Extended Sample of Events (2005)
Gal-Yam, Avishay, Nakar, Ehud, Ofek, Eran, Fox, D. B., Cenko, S. B., Kulkarni, S. R., ...
The detection of the afterglow emission and host galaxies of short-hard gamma-ray bursts (SHBs) is one of the most exciting recent astronomical discoveries. Indications that SHB progenitors belong to...
On the expansion of the giant component in percolated (n,d,\lambda) graphs (2005)
Let d \geq d_0 be a sufficiently large constant. A (n,d,c \sqrt{d}) graph G is a d-regular graph over n vertices whose second largest (in absolute value) eigenvalue is at most c \sqrt{d}. For any 0 <...
Routing complexity of faulty networks (2005)
Omer Angel, Itai Benjamini, Eran Ofek, Udi Wieder
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the...
Routing complexity of faulty networks (2005)
Omer Angel, Itai Benjamini, Eran Ofek, Udi Wieder
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the...
Spectral techniques applied to sparse random graphs. Random Structures and Algorithms (2005)
We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let λ1 ≥... ≥ λn be the eigenvalues of an n-vertex graph, and let λ = max[λ2, |λn|]. Let c be a large enough...
Routing complexity of faulty networks (2005)
Omer Angel, Itai Benjamini, Eran Ofek, Udi Wieder
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the...
Spectral techniques applied to sparse random graphs. Random Structures and Algorithms (2005)
We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let λ1 ≥... ≥ λn be the eigenvalues of an n-vertex graph, and let λ = max[λ2, |λn|]. Let c be a large enough...
Spectral techniques applied to sparse random graphs. Random Structures and Algorithms (2005)
We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let 1 : : : n be the eigenvalues of an n-vertex graph, and let = max[ 2; j n j]. Let c be a large enough constant....
Routing Complexity of Faulty Networks (2004)
Angel, Omer, Benjamini, Itai, Ofek, Eran, Wieder, Udi
One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the...
Easily refutable subformulas of large random 3CNF formulas (2004)
Abstract: A simple nonconstructive argument shows that most 3CNF formulas with cn clauses (where c is a sufficiently large constant) are not satisfiable. It is an open question whether there is an...
Easily refutable subformulas of large random 3CNF formulas (2004)
A simple nonconstructive argument shows that most 3CNF formulas with cn clauses (where c is a large enough constant) are not satisfiable. It is an open question whether there is an efficient...
Easily refutable subformulas of large random 3CNF formulas (2004)
A simple nonconstructive argument shows that most 3CNF formulas with cn clauses (where c is a large enough constant) are not satisfiable. It is an open question whether there is an efficient...
Spectral techniques applied to sparse random graphs. Random Structures and Algorithms (2003)
Abstract We analyze the eigenvalue gap for the adjacency matrices of sparse random graphs. Let *1> =...> = *n be the eigenvalues of an n-vertex graph, and let * = max[*2, |*n|]. Let c be alarge...
Orphan GRB radio afterglows: Candidates and constraints on beaming (2002)
Levinson, Amir, Ofek, Eran, Waxman, Eli, Gal-Yam, Avishay
The number of orphan radio afterglows associated with gamma-ray bursts (GRBs) that should be detected by a flux limited radio survey, is calculated. It is shown that for jetted GRBs this number is...
Approximating maximum edge coloring in multigraphs (2002)
Uriel Feige, Eran Ofek, Udi Wieder
We study the complexity of the following problem that we call Max edge t-coloring: given a multigraph G and a parameter t, color as many edges as possible using t colors, such that no two adjacent...
Approximating maximum edge coloring in multigraphs (2002)
Uriel Feige, Eran Ofek, Udi Wieder
We study the complexity of the following problem that we call Max edge t-coloring: given a multigraph G and a parameter t, color as many edges as possible using t colors, such that no two adjacent...
Evidence for a New Class of Extreme UV Sources (1996)
Maoz, Dan, Ofek, Eran, Shemi, Amotz
Most of the sources detected in the extreme ultraviolet (EUV; 100 Ang to 600 Ang) by the Rosat WFC and EUVE all-sky surveys have been identified with active late-type stars and hot white dwarfs that...
Optical Identification of Quasar 0917+7122 in the Direction of an Extreme-Ultraviolet Source (1995)
Maoz, Dan, Ofek, Eran, Shemi, Amotz, Barth, Aaron, Filippenko, Alexei, Brotherton, Michael, ...
We report the optical identification of an $R=18.3$ mag, $z=2.432$ quasar at the position of a 6 cm radio source and a faint \rosat PSPC X-ray source. The quasar lies within the error circles of...