| [home] - [up] |
Abstract: We consider a scenario where we want to query a large dataset that is stored in external memory and does not fit into main memory. The most constrained resources in such a situation are the size of the main memory and the number of random accesses to external memory. We note that sequentially streaming data from external memory through main memory is much less prohibitive.
We propose an abstract model of this scenario in which we restrict the size of the main memory and the number of random accesses to external memory, but do not restrict sequential reads. A distinguishing feature of our model is that it admits the usage of unlimited external memory for storing intermediate results, such as several hard disks that can be accessed in parallel.
In this model, we prove lower bounds for sorting the input data. As opposed to related results for models without auxiliary external memory for intermediate results, we cannot rely on communication complexity to establish these lower bounds. Instead, we simulate our model by a non-uniform computation model for which we can establish the lower bounds by combinatorial means.
(Joint work with Martin Grohe, HU Berlin).
Colloquium - 16 Uhr s.t.
Abstract: Constraint satisfaction is a concept generalizing the well-known problem whether a given boolean formula has a satisfying truth assignment. Constraint satisfaction problem consists of a set of variables, a set of possible values of variables and a set of constraints where each constraint defines possible combinations of values on some set of variables. The solution of a problem is an assigment of values to the variables which satisfy all the constraints. In the surjective constraint satisfaction we additionaly require that the assignment must be such that each possible value is assigned to at least one variable.
In the talk we present a motivation of the surjective satisfaction problem and prove the complete characterization of the Boolean surjective constraint satisfaction.