Could there theoretically exist a material so light, that it can levitate in the air just due to the in height decreasing air pressure? Airplanes can fly because the pressure on the top of the wing is lower than on the bottom. But the difference in pressure must be huge in order to lift an enire airplane. Also, the difference in air pressure between, let's say, Mount Everest and sea level is not neglectable, thus, air pressure is  decreasing the heigher you go.

This is where I asked myself: Can we theoretically build a material which is light enough or high enough (or both), that can levitate just due to the difference in pressure on the top vs. the bottom like an on an airplane wing.

For example imagine you're holding a piece of paper horizontally, then air pressure on the top is slightly lower due to the decreasing air pressure and now just make the piece of paper as light as it needs to be to stay in the air like a wing on a flying airplane
Is this theoretically possible or are there other effects or simplifications I overlooked?
 A: Is this theoretically possible with only one single material? Yes. Any object occupying a volume of gas (or liquid, or solid) has a slightly higher pressure underneath it than the pressure on top of it (while sitting still) due to the pressure decreasing with height. If it is less dense than the air it occupies (combined weight of both its outside envelope and the mass inside), then the slightly differential air pressure will cause it to rise.  It will continue to rise until the differential air pressure matches the weight of the object.
A balloon's weight, combined with lighter than air gas inside achieves this. The helium in a balloon doesn't push on the top inner side of the balloon to make it go up. It is the stronger outside pressure on the bottom of the balloon than is on the top that makes it rise. The helium has enough pressure to maintain the envelope of the balloon, but low enough mass so that the entire weight of the balloon is less than the amount of air that occupies the same volume of the balloon.  Same idea for things that float on a liquid (the differential pressure is larger, allowing large ships made from metal).
It is not just like an airplane wing. Airplane wings accelerate the airflow downward  (with a bit of Bernoulli as well), like a water skier, and the wing needs to be moving through the air.

Is this theoretically possible or are there other effects or
  simplifications I overlooked?

Theoretically, two configurations I can think of:


*

*A single material heavier than air, but with a vacuum inside, light enough to be less dense overall, but strong enough to not only prevent air from leaking inside, but prevent the air from crushing it as well; or

*As you alluded to, a solid whose density is less than that of air.

A: A hot air balloon, or a helium-filled balloon floats in air, so either might meet your criteria.
If you're looking for a solid material, perhaps a sphere of very sparse aerogel, with its outside surface sealed with a thin layer of plastic then evacuated, could come close to what you have in mind.  But whatever the "material" is, it would need to have a lower mass density than the ambient air.
A: Congratulations! You have figured out the basis of Archimedes' principle. The article linked here gives a satisfactory explanation, though the main point can be made simply:
Consider a vertically-oriented cylinder within the fluid. The difference in pressure between the top and bottom of that cylinder is due to the weight of the fluid within it, and is just that weight divided by its cross-sectional area. Substitute a solid body of the same dimensions, and the difference in the force exerted by the fluid on the top and the bottom of that body -- the upthrust on it -- is the difference in pressure multiplied by the cross-sectional area. But that is just the weight of the fluid that formerly occupied the space taken by that body, and has now been displaced by it.
Considering any irregularly-shaped object as a bundle of thin cylinders, each buoyed by the fluid it displaces, it is clear that shape does not matter, only volume. The upthrust is greater than the body's weight if the body weighs less than the fluid it displaces, and as they are the same volumes, this is just when the body is less dense than the fluid.
The answer to your question, therefore, is that anything of a density equal to or less than than air will float in air, and balloons containing hydrogen or helium are the most common examples. Other answers have suggested vacuum aerogels, but an aerogel containing hydrogen or helium at atmospheric pressure is a more straightforward candidate, as it does not require the gel to have any great strength. For example, the lightest evacuated aerogel achieved so far has a density of 1000 $g/m^3$, and room temperature and pressure hydrogen has a density of 83.2 $g/m^3$, giving a density for the gel, when infused with hydrogen, of no more than 1083.2 $g/m^3$, less that the density of air in the same conditions - 1200 $g/m^3$ (the surface of the aerogel would have to be sealed with a membrane, but its contribution to the density would decrease with increasing volume, by the familiar surface area / volume scaling.)
More radically, this aerographene has an evacuated density of only 160 $g/m^3$.
A: An alternative to baloons is a spheric shell, with vacuum inside, with a thickness and material strength designed to resist to atmospheric pressure. The force upwards is the equivalent to the weight of air. And its weight is proportional to the surface and thickness. For a thin shell:
$$F_\text{up} = \mu_\text{air} g (4/3)\pi r^3$$
$$\text{weight} = \mu_\text{shell} g 4\pi r^2 \cdot \text{thickness}$$
In order to fluctuate $F_\text{up} \ge \text{weight} \Rightarrow \mu_\text{air}/\mu_\text{shell} \ge 3\cdot\text{thickness}/r$
For a shell made from steel ($\mu = 7850\ \mathrm{kg/m^3}$) with $10\ \mathrm{mm}$ of thickness, and for $\mu_\text{air} = 1.2\ \mathrm{kg/m^3}$
$$r_\text{min}= \frac{7850\ \mathrm{kg/m^3}}{1.2\ \mathrm{kg/m^3}} \times 3 \times 0.010\ \mathrm m = 196\ \mathrm m $$
If it could resist to the pressure of $1\ \mathrm{kg/cm^2}$ without collapsing is another question.
A: You're asking about air, I think, but if you mean gasses in general, then aerogels are a kind of substance that can float on xenon.  Wikipedia and YouTube have lots of information.
A: It's a vacuum balloon. A sphere of implausibly strong material, with a vacuum  inside. It will rise until the weight of the air it is displacing equals the weight of that implausibly strong sphere. And in Science Fiction, it can stay aloft indefinitely and adjust its altitude by means of a small vacuum pump, batteries, solar panels and a leak valve ....
For a proof of concept (were one needed) that might actually work up to a few thousand metres altitude, I'd look for the strongest aerogel I could find, wrap it in a thin tough plastic membrane, and suck the air out using a vacuum pump. If the aerogel did not collapse under the pressure, you may have your vacuum balloon.
In the real world we fill a membrane with helium or hydrogen, and this has no need for implausibly strong materials. They can rise until they go pop as the gas inside expands. Google has a "loon" project for balloons which regulate their altitude so they don't pop, creating high-altitude non-satellites to bring broadband and phone services to truly remote areas.
