Introduction depends on preliminaries. What to do? I am writing a paper but have the following problem. The introduction section requires basic knowledge of things introduced in the preliminaries. As I understand it, it is customary (in computer science) that one has an introduction and than preliminaries which would mean that most people would not understand the introduction section.

How should I deal with this kind of dependence?
We are introducing a new topic (from a comment you made) --- Then you'll want to look at papers that deal with new topics. Can't you just give a non-technical overview, something in which someone who doesn't know this topic can follow, with possibly a statement telling the reader that precise definitions of some of the terms are given in the preliminaries section? I've seen quite a few math papers do this, where there is an introduction followed by a "notations and definitions" section.

Here is a freely available example of a paper with a general introduction followed by a preliminaries section that gives detailed definitions of terms used in the introduction. Also, at the time the paper appeared, the main object of study (sigma-porous sets) was still fairly new and not widely known, and it was almost certainly not known by a typical reader of the journal in which this paper was published.