Dual EM field in terms of original EM field In Maxwell theory we have dual description in terms of dual fields:
$$
\tilde{F}_{\mu\nu} = \partial_\mu \tilde{A}_\nu - \partial_\nu \tilde{A}_\mu
=
\varepsilon_{\mu\nu\rho\sigma} F^{\rho\sigma}
$$
$$
F_{\mu\nu} = \partial_\mu A_\nu - \partial_\nu A_\mu 
$$
How to solve this equation for $\tilde{A}_\mu$ in terms of $A_\mu$?

I have few ideas about solutions:
$$
\tilde{A}_\mu \propto \varepsilon_{\mu\nu\rho\sigma}x^\nu \partial^\rho A^\sigma
$$
Or something like this:
$$
\tilde{A}_\mu = \int^x \varepsilon_{\mu\nu\rho\sigma}dx^\nu \partial^\rho A^\sigma
$$
It also looks like that first solution is local, second solution is non-local.

Electro-magnetic duality:
Maxwell equations:
\begin{equation}
    \begin{cases}
    \partial_\mu F^{\mu\nu} = 0 \\
    \partial_\mu \tilde{F}^{\mu\nu} = 0
    \end{cases}
\end{equation}
are invariant under:
$$F^{\mu\nu} \leftrightarrow  \tilde{F}^{\mu\nu}$$
So we can formulate theory using dual e-m potential.
Or more formally using path integral:
$$
\begin{equation}
    \int DA \;e^{-\frac{1}{4e^2} F^{\mu\nu}F_{\mu\nu}}
    =
    \int DF D\tilde{A} \;e^{-\frac{1}{4e^2} F^{\mu\nu}F_{\mu\nu} + i\tilde{A}_\mu \varepsilon^{\mu\nu\rho\sigma}\partial_\nu F_{\rho\sigma}}
    =
    \int D\tilde{A} \; e^{-\frac{e^2}{4} \tilde{F}^{\mu\nu}\tilde{F}_{\mu\nu}}
\end{equation}$$
 A: Performing a Fourier transform, you find:
$2 \epsilon_{\mu\nu\rho\sigma}p^\rho \tilde{A}^\sigma(p) = p_\mu A_\nu(p) - p_\nu A_\mu(p)~.$
You can view each side of the equation as an operator that maps a vector to an antisymmetric tensor, acting on the vector $\tilde{A}$ on the left and on the vector $A$ on the right. Explicitly, upon defining
$\tilde{M}_{\mu\nu}^{~~~~\sigma}(p) = 2\epsilon_{\mu\nu\rho}^{~~~~~~~\sigma}p^\rho~,\\
M_{\mu\nu}^{~~~~\lambda}(p) = p_\mu \delta_
\nu^\lambda -p_\nu \delta_\mu^\lambda~,$
your equation becomes
$ \tilde{M}_{\mu\nu}^{~~~~\sigma}(p) \tilde{A}_\sigma(p) = M_{\mu\nu}^{~~~~\lambda}(p) A_\lambda(p)~.$
Now your problem becomes that of inverting either one of these two operators, say $\tilde{M}$ for definiteness (they are related to each other by contraction with the epsilon tensor, so it does not make a big difference which one you pick). Unfortunately they are not invertible, because you can easily check that the vector $p^\mu$ is mapped to the vanishing anti-symmetric tensor. That is not so surprising, it is just equivalent to the statement that the field strengths are invariant under gauge tranformations, but still it means that strictly speaking you cannot invert these operators and find $\tilde{A}$ in terms of $A$ (or viceversa). At most you can find a solution up to a gauge transformation, i.e. you can find $\tilde{A}_\mu$ up to a shift of the form $p_\mu C(p)$ where $C(p)$ is an arbitrary function of $p$. 
Once you accept that this is the most you can do, you can easily check that the operator
$\tilde{N}_\omega^{~~\mu\nu}(p)\,= \,b \,\frac{1}{p^2}\epsilon_\omega^{~~\mu\nu\tau}p_\tau$
-- with an appropriate choice of the numerical coefficient $b$ that I will not try to fix but can be fixed with a straightforward calculation -- accomplishes the task of almost-inverting $\tilde{M}(p)$, i.e. there exists a $C(p)$ such that 
$\tilde{N}_\omega^{~~\mu\nu}(p)\tilde{M}_{\mu\nu}^{~~~~\sigma}(p) \tilde{A}_\sigma(p) = \tilde{A}_\omega(p) + p_\omega C(p)~.$
(To fix the numerical constant $b$ you have to use the identity that relates the contraction of two epsilon tensors to sum of a bunch of products of Kronecher delta's.)
So the best possible answer to your question is --in momentum space-- 
$\tilde{A}_\omega(p) = \tilde{N}_\omega^{~~\mu\nu}(p) M_{\mu\nu}^{~~~~\lambda}(p) A_\lambda(p) - p_\omega C(p)~.$
Note that this relation is NOT polynomial in momentum, because the operator $\tilde{N}$ contains a $1/p^2$, and therefore is it not local. If you express it in position space it contains something like the inverse of a Laplacian (or D'Alembertian if you are in Lorentzian signature). There does not exist any local relation between a gauge field and its EM dual, basically because you need to invert a derivative to get one from the other. 
A: $\newcommand{\d}{\mathrm{d}}$
The dual field is $\tilde{A}$ where
$$ \d \tilde{A} = \star\; \d A. \tag{1}$$
$\tilde A$ is non-local in terms of $A$. A closed formula obtaining $\tilde A$ from $A$ is not known (to my knowledge at least). In spirit it should look more like your second relation, although not quite because of the contractions of indices hidden in the exterior derivatives.
One way to come closer to obtaining $\tilde{A}$ from $A$ would be to take equation (1) and integrate it over a manifold $M$ whose boundary is just a single point, $\cal P$. Then
\begin{align} \int_M \d \tilde A &= \int_M \star\; \d A \\
\int_{\partial M} \tilde A &= \int_M \star\; \d A \\[5mm]
\tilde A (\cal P) &= \int_M \star\; \d A.
\end{align}
Then you should probably imagine dragging $\cal P$ around to obtain $\tilde A$ everywhere in space, but I don't know how to do it in maths :(
In most cases (not in all cases of course) you don't quite care about what $\tilde A$ is itself because it appears either as $\d\tilde A$, which you know, or coupled like $\tilde A\wedge\d[\text{something}]$ so you can exchange this for $\d\tilde A \wedge[\text{something}]$.
A: Dual in this context is the Hodge dual, as far as I understand. 
The dual of a rank-2 tensor in 4d space is also a rank-2 tensor (hence the similarity between $F$ and $\tilde{F}$). The hodge dual of a vector (rank-1 tensor) is rank-3 tensor. You can start with 
$\mathbf{A}=A_\mu dx^\mu$
and then find 
$\star \mathbf{A} = \tilde{A}_{\nu\zeta\xi}\: dx^\nu dx^\zeta\ dx^\xi=\epsilon_{\mu\nu\zeta\xi}g^{\mu\kappa}A_\kappa dx^\nu dx^\zeta\ dx^\xi$ 
Where $g^{\mu\kappa}$ is the inverse metric.
I am not sure if it will help you in any way. I suppose if the metric is trivial, the dual $\tilde{A}$ is linearly dependent on $A$. But this is only true with trivial metric. So is this a worthwhile thing to do? 
