We show how to find in Hamiltonian graphs a cycle of length $n^{\Omega(1/\log\log n)}$. This is a consequence of a more general result in which we show that if $G$ has maximum degree $d$ and has a cycle with $k$ vertices (or a 3-cyclable minor $H$ with $k$ vertices), then ... more >>>

We consider the problem of finding a $k$-vertex ($k$-edge) connected spanning subgraph $K$ of a given $n$-vertex graph $G$ while minimizing the maximum degree $d$ in $K$. We give a polynomial time algorithm for fixed $k$ that achieves an $O(\log n)$-approximation. The only known previous polynomial algorithms achieved degree $d+1$ ... more >>>

We study the problem of assigning different communication channels to acces points in a wireless Local Area Network. Each access point will be assigned a specific radio frequency channel. Since channels with similar frequencies interfere, it is desirable to assign far apart channels (frequencies) to nearby access points. Our goal ... more >>>

We show that every language in NP has a probablistic verifier that checks membership proofs for it using logarithmic number of random bits and by examining a constant number of bits in the proof. If a string is in the language, then there exists a proof such that ... more >>>

We attempt to reconcile the two distinct views of approximation classes: syntactic and computational. Syntactic classes such as MAX SNP allow for clean complexity-theoretic results and natural complete problems, while computational classes such as APX allow us to work with problems whose approximability is well-understood. Our results give a computational ... more >>>