The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
The essence of mathematics is proving theorems — and so, that is what mathematicians do: they prove theorems. But to tell the truth, what they really want to prove once in their lifetime, is a Lemma, like the one by Fatou in analysis, the Lemma of Gauss in number theory, or the Burnside-Frobenius Lemma in combinatorics.
The nearest neighbor problem is defined as follows: Given a metric space X and a fixed finite subset S ⊂ X of n “sites”, preprocess S and build a data structure so that queries of the following kind can be answered efficiently: Given a point q ∈ X find one of the points p ∈ S closest to q (see Figure 1).
This tutorial is aiming at some randomized approaches for geometric optimization that have been developed over the last ten to fifteen years. The methods are simple, sometimes even the analysis is. The simplicity of the methods entails that they use very little of the underlying structure of the problems to tackle, and, as a consequence, they are applicable to a whole range of problems. Most prominently,...
One recent direction in coding theory has been to study linear codes over the alphabet Z4 and apply the Gray map from Z4 to binary pairs to obtain binary nonlinear codes better than comparable binary linear codes. This connection between linear codes over Z4 and nonlinear binary codes was also the breakthrough in solving an old puzzle of the apparent duality between...
For vertices x,y of a connected graph G let DG(x,y) denote the length of a longest (x,y)-path in G. Strangely enough D(.,.) defines a somewhat exotic metric on the vertex set V(G). To see this, consider a longest (x, z)-path P and a longest (y,x)- path Q in G. For the first vertex v on Q in V(P) we then have D(y,z) ≥ |Q(y,v]| + |P(v,z]| and D(x,y) ≥ |P(x,v]| + |Q(v,y]|...
This article gives an outline of a lecture about ordered binary decision diagrams (OBDDs). Introduced in 1986, OBDDs nowadays are the state-of-the-art data structure for representation of Boolean functions in electronic design automation (EDA). An overview is given about the data structure, its properties, algorithmic behaviour, and the most important applications. Proofs and technical details...
Deterministic models for project scheduling and control suffer from the fact that they assume complete information and neglect random influences that occur during project execution. A typical consequence is the underestimation of the expected project duration and cost frequently observed in practice. This phenomenon occurs even in the absence of resource constraints, and has been the subject of extensive...
While everybody seems to immediately understand and accept the commonly used model of a random graph - simply toss a coin for every edge to decide whether it is there - the situation gets harder when we require that the random graph must satisfy some additional constraints such as having no triangles or being transitive.
The most common algorithm for computing the determinant ofan n×n matrix A is Gaussian elimination and needs O(nsu3) additions, subtractions, multiplications, and divisions. On the other hand, the explicit definition of the determinant as the sum of n! products, $$ c:\left\{ \begin{gathered} {\mathbf{ }}A^{n - 1} \to A^n \hfill \\ a_1 a_2 \ldots a_{n - 1} \mapsto a_1 a_2 \ldots a_{n - 1} a_n . \hfill...
A check digit system with one check character over an alphabet A is a code $$ c:\left\{ \begin{gathered} A^{n - 1} \to A^n \hfill \\ a_1 a_2 \ldots a_{n - 1} \mapsto a_1 a_2 \ldots a_{n - 1} a_n . \hfill \\ \end{gathered} \right. $$ which is used to detect (but not in general to correct) single errors (i.e. errors in one component) and other errors of certain patterns (discussed below).
In this article, we will discuss algorithmic group theory from the point of view of pure mathematics. We will investigate some of the problems and show why many problems are accessible just for a few years. In algebra there are many problems, which are easy to state, sometimes even easy to prove, and where one might be surprised that there is no algorithmic solution. The two most developed areas of...
The 0/1-Borsuk problem asks whether every subset of {0, 1}d can be partitioned into at most d + 1 sets of smaller diameter. This is known to be false in high dimensions (in particular for d ≥ 561, due to Kahn & Kalai, Nilli, and Raigorodskii), and yields the known counter-examples to Borsuk’s problem posed in 1933. Here we ask whether there might be counterexamples in low dimension as well...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.