All reports by Author Rajeev Motwani:

__
TR06-156
| 7th December 2006
__

Tomas Feder, Rajeev Motwani#### Finding large cycles in Hamiltonian graphs

__
TR06-041
| 6th March 2006
__

Tomas Feder, Rajeev Motwani, An Zhu#### k-connected spanning subgraphs of low degree

__
TR06-040
| 6th March 2006
__

Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu#### Channel assignment in wireless networks and classification of minimum graph homomorphism

__
TR98-008
| 15th January 1998
__

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy#### Proof verification and the hardness of approximation problems.

__
TR95-023
| 16th May 1995
__

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani#### On Syntactic versus Computational views of Approximability

Tomas Feder, Rajeev Motwani

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 >>>

Tomas Feder, Rajeev Motwani, An Zhu

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 >>>

Tomas Feder, Gagan Aggarwal, Rajeev Motwani, An Zhu

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 >>>

Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy

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

<em> constant </em> number of bits in the proof.

If a string is in the language, then there exists a proof ...
more >>>

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

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 >>>