  We design an algorithm for approximating the size of \emph{Max Cut} in dense
graphs. Given a proximity parameter $\varepsilon \in (0,1)$, our algorithm
approximates the size of \emph{Max Cut} of a graph $G$ with $n$ vertices,
within an additive error of $\varepsilon n^2$, with sample complexity
$\mathcal{O}(\frac{1}{\varepsilon^3} \log^2 \frac{1}{\varepsilon} \log \log
\frac{1}{\varepsilon})$ and query complexity of
$\mathcal{O}(\frac{1}{\varepsilon^4} \log^3 \frac{1}{\varepsilon} \log \log
\frac{1}{\varepsilon})$. Since Goldreich, Goldwasser and Ron (JACM 98) gave the
first algorithm with sample complexity $\mathcal{O}(\frac{1}{\varepsilon^5}\log
\frac{1}{\varepsilon})$ and query complexity of
$\mathcal{O}(\frac{1}{\varepsilon^7}\log^2 \frac{1}{\varepsilon})$, there have
been several efforts employing techniques from diverse areas with a focus on
improving the sample and query complexities. Our work makes the first
improvement in the sample complexity as well as query complexity after more
than a decade from the previous best results of Alon, Vega, Kannan and
Karpinski (JCSS 03) and of Mathieu and Schudy (SODA 08) respectively, both with
sample complexity
$\mathcal{O}\left(\frac{1}{{\varepsilon}^4}{\log}\frac{1}{\varepsilon}\right)$.
We also want to note that the best time complexity of this problem was by Alon,
Vega, Karpinski and Kannan (JCSS 03). By combining their result with an
approximation technique by Arora, Karger and Karpinski (STOC 95), they obtained
an algorithm with time complexity of $2^{\mathcal{O}(\frac{1}{{\varepsilon}^2}
\log \frac{1}{\varepsilon})}$. In this work, we have improved this further to
$2^{\mathcal{O}(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon} )}$.
