Startseite > Fachgruppen > Algorithmen und Komplexität > Lehre > Gems of Theoretical Computer Science

Gems of Theoretical Computer Science

Seminar, Winter Term 2022/23

The seminar based on a set of selected papers and textbook sections that demonstrate the beauty of problem solutions in the field of Theoretical Computer Science. We will find out that the preoccupation with sophisticated proof techniques, elegant arguments and surprising constructions is highly enjoyable. The seminar is inspired by the book "Perlen der Theoretischen Informatik " by Uwe Schöning, in which he presents a collection of results demonstrating highlights of Theoretical Computer Science. Of course, the selection of seminar topics is affected by the supervisor’s taste and research area.

Lecturer

Modul

  • Seminar I / Seminar II

Dates & Deadlines

The seminar takes place as a block seminar in the last week of lectures.

  • First meeting (distribution of topics):
    Monday, 10 October, 4:15pm, room F1.110
  • We strongly recommend a initial meeting with your advisor significantly earlier and not later than
    Thursday, 3 November
    For this meeting, you are expected to have read the paper, and come with concrete questions:
  • Short Talks (5-10 minute introduction to your topic):
    Wednesday, 9 November, 9:00 am to 5:00 pm, room F0.231
  • Submission deadline of the 0-version of seminar thesis (see Step II below):
    Tuesday, 13 December
    We strongly recommend to give at least part of the thesis to your advisor in advance to this deadline, in consultation with him
  • Submission deadline of the reviews (see Step III below):
    Wednesday, 21 December
  • We strongly recommend self organized test presentations (see Step IV below):
    Monday, 9 January to Friday, 13 January
  • Submission deadline of the final version of the seminar thesis:
    Sunday, 29 January
  • Block Seminar, Presentation of your work (see Step I below):
    Thursday, 2 February and Friday, 3 February both entire day, room F0.231

Topics and Registrations

The topics (see below) are given in the first meeting. Reservations or defaults of issues are not possible. You should have a look at the topics (see below) and respective papers before the first meeting and make your mind up about your topic preferences.

Demands

I) Presentation

45 minutes presentation.
15 minutes discussion and questions.
Your audience: Your fellow students.
    
As a minimal requirement, the presentation should motivate your model, formally introduce the problem, explain the necessary techniques, and provide insight into the necessary algorithms and their analysis (i.e., with proofs!). Some ideas e.g. "Scientific Working"

II) Seminar thesis

Essay of length 12 to 20 pages written according to the standards of a scientific paper. Submitting work of others is cheating and a violation of academic plagiarism rules, which is a serious offense. We use a commercial, Internet-based plagiarism detection service to check your submissions. Also the simple copying of the original work into the own thesis causes the failure of the seminar.

Note that the 0-version of your thesis should be as closely to your final thesis as possible. In particular, it must be complete content-wise (the minimum number of pages also applies to the 0-version!).

III) Reviews

  • Peer review procedure similar to scientific publications
  • You submit your thesis (paper) at the seminar's Panda page
  • Some (2) peers (other students) review your submission
    • Read and understand the submitted paper
    • Criticize your paper
    • Make recommendations on how to improve
    • Be honest, polite, and helpful when writing your reviews
  • Each student has to write 2 reviews (each 1-2 pages)

IV) Test run of your presentation

  • Do a test run with your presentation.
  • Meet in groups of approx. 3-4 students
  • Give each other feedback
  • Negotiate date yourselves (see Panda page for the participants' email adresses)

We expect your active participation (as opposed to mere attendance) at all presentations of this seminar.

Grading

Your final grade will be based on the following:

  • Quality of your seminar thesis
  • Quality of your final presentation
  • Commitment, diligence, and compliance with our deadlines.

Note that we will grade each of the above parts individually, and that you have to pass each part (i.e., 4.0 or better) to pass this course.

Remarks

General

Each topic has one or several references that should be understood as starting points for your research. Hence, it is very likely that you will need further papers or textbooks to fully understand your topic. The actual content of your seminar thesis as well as your seminar talk should be discussed with your adviser.
It is your responsibility to contact your adviser and schedule appointments with them early enough. We strongly recommend you to discuss questions regarding the topic, the composition, and the structure of your written seminar thesis with your adviser. The same holds for your seminar talk. Note that finding an appointment directly before your thesis' submission or seminar talk cannot be guaranteed, since the advisers need to arrange their appointments with their own teaching and research.
If you are looking for additional research papers, the following links might be helpful:

Seminar Thesis

We expect an essay of length 12 to 20 pages written according to the standards of a scientific paper. A simple summary of the referenced literature is insufficient. We expect you to identify the important ideas and proofs of the referenced literature and present them in a correct and appropriate way. The mandatory typesetting for your thesis is LaTeX (see below for details). All citations must be marked as such and referenced with their origin. Plagiarism directly leads to failure of the seminar. Note that plagiarism not only includes copies from the original literature, but also copies from other authors (e.g., other seminar theses) or translations of them.

Title and Abstract

Create a brief abstract that summarizes the problem and the main results. An abstract is kept short (typically 10-20 lines). Also make up a title for your thesis (note that this is not necessarily the title of the used literature or the title from our topic list). It is important to make your own reasoning about a title that describes the thesis best from your point of view.

References

Each thesis contains a reference list that contains at least the literature used in your thesis. In the digital libraries of DBLP, ACM, IEEE, or Springer you can find detailed literature reference information. For conferencing proceedings or journals ALWAYS specify the pages. For journals, additionally provide volume and journal number. Do not rely on the authors to do their references correct (e.g., reference list in a paper or at the author's website). Sometimes this references are wrong or incomplete. Also do not rely on search engines like CiteSeer or Google Scholar: always verify the correctness and completeness of your references. Especially, it is insufficient if you only provide links to the papers or citations in the web.

Further Reading

For further reading we advice


Topic 1:   Self-Stabilizing Systems in Spite of Distributed Control

In his seminal work, Dijkstra studies the existence of self-stabilizing protocols. In general, distributed systems are error-prone, and the idea of self-stabilizing protocols is that the involved processes react to errors and redirect the system into a legitimate state. Self-Stabilizing protocols fulfill two properties: convergence and closure. Starting in an illegal state, the execution of the protocol leads to a legitimate state in finite time. Moreover, as soon as a legitimate state is reached, the protocol remains in a legitimate state (as long as no further error occurs). The concrete definition of illegal and legitimate states depends on the application. Up to this work, it was unclear whether such protocols may exist in general. Dijkstra answers the question positively by introducing three self-stabilizing protocols for the distributed token ring. In [1] the original paper is contained. Later on, in [2] a proof that the protocols are indeed self-stabilizing is given.

Literature:

  1. Dijkstra, Edsger W.: Self-stabilizing systems in spite of distributed control. Communications of the ACM 17.11 (1974): pp.643-644
  2. Dijkstra, Edsger W.: A belated proof of self-stabilization. Distributed Computing 1.1 (1986): pp.5-6

Advisor: Jannik Castenow

Topic 2:   Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility

We consider distributed computations, by identical autonomous mobile entities, that solve the Point Convergence problem: given an arbitrary initial configuration of entities, disposed in the Euclidean plane, move in such a way that, for all ε>0, a configuration is eventually reached and maintained in which the separation between all entities is at most ε. The problem has been previously studied in a variety of settings. Our study concerns the minimal assumptions under which entities, moving asynchronously with limited and unknown visibility range and subject to limited imprecision in measurements, can be guaranteed to converge in this way. We present an algorithm that solves Point Convergence, provided the degree of asynchrony is bounded by some arbitrarily large but fixed constant. This provides a strong positive answer to a decade old open question posed by Katreniak. We also prove that, in an otherwise comparable setting, Point Convergence is impossible with unbounded asynchrony. This serves to distinguish the power of bounded and unbounded asynchrony in the control of autonomous mobile entities, settling at the same time a long-standing question whether in the Euclidean plane synchronous entities are more powerful than asynchronous ones.

Literature:

Kirkpatrick, David, et al.: Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. 2021, pp. 9-19

Advisor: Jannik Castenow

Topic 3:   Gathering over Meeting Nodes in Infinite Grid

The gathering on meeting points problem requires the robots to gather at one of the pre-defined meeting points. This paper investigates a discrete version of the problem where the robots and meeting nodes are deployed on the nodes of an anonymous infinite square grid. The robots are identical, autonomous, anonymous, and oblivious. They operate under an asynchronous scheduler. Robots do not have any agreement on a global coordinate system. Initial configurations, for which the problem is unsolvable, have been characterized. A deterministic distributed algorithm has been proposed to solve the problem, for the rest of the configurations.

Advisor: Jannik Castenow


Topic 4:   A Peer-to-Peer Based Cloud Storage Supporting Orthogonal Range Queries of Arbitrary Dimension

Consider the problem of storing and retrieving data in a distributed system. A data-item can be viewed as a point in a multi-dimensional space. Each dimension reflects some attribute of the data (size, creation date, data type, …). In such a system not only the simple search for a single item is important but also how a set of data-items can be accessed. For example, a query might be interested in all data-items where the size is in between 2MB and 10MB and the date of creation was within the last month. In the given paper, the authors explore how a distributed system can be organized such that these multi-dimensional range queries are efficiently processed, while the architecture of the network shall be simple (and as far as possible independent of the used data).

Literature:

M. Benter, T. Knollmann, F. Meyer auf der Heide, A. Setzer, J. Sundermeier: A Peer-to-Peer Based Cloud Storage Supporting Orthogonal Range Queries of Arbitrary Dimension. ALGOCLOUD 2018, pp. 48-56

Advisor: Till Knollmann

Topic 5:   Impossibility of distributed consensus with one faulty process

The FLP (Fischer, Lynch, Patterson) result was a ground-breaking result regarding the consensus problem in asynchronous systems where a set of participants communicate via messages. In an asynchronous system, the participants do not interact synchronously but each one has its own pace (one participant might be very slow in processing messages, while some other is extremely fast). The goal of the consensus problem is that all participants agree upon a common value in finite time (for example, agree on if a transaction is valid or not). In the given paper, the authors study if achieving a consensus in an asynchronous system is possibly if one of the participants might crash.

Literature:

M.J. Fischer, N.A. Lynch, M.S. Paterson: Impossibility of Distributed Consensus with One Faulty Process. Journal of the ACM, Volume 32, Issue 2 (April 1985), pp 374–382

Advisor: Till Knollmann

Topic 6:   Non-Linear Ski Rental

We consider the following generalization of the classic ski rental problem. A task of unknown duration must be carried out using one of two alternatives called "buy" and "rent", each with a one-time startup cost and an ongoing cost which is a function of the duration. Switching from rent to buy also incurs a one-time cost. The goal is to minimize the competitive ratio, i.e., the worst-case ratio between the cost paid and the optimal cost, over all possible durations. For linear or exponential cost functions, the best deterministic and randomized on-line strategies are well known. In this work we analyze a much more general case, assuming only that the cost functions are continuous and satisfy certain mild monotonicity conditions. For this general case we provide (1) an algorithm that computes the deterministic strategy with the best competitive ratio, and (2) an approximation algorithm that, given ε>0, computes a randomized strategy whose competitive ratio is within (1+ε) from the best possible, in time polynomial in ε-1. Our algorithm assumes access to a black box that can compute the functions and their inverses, as well as find their extreme points.

Literature:

Advisor: Till Knollmann


Topic 7:   The Complexity of Scheduling Trees with Communication Delay

Consider the problem of finding a minimum-length schedule on m machines for a set of n unit-length tasks with a forest of intrees as precedence relation, and with unit interprocessor communication delays. First, they prove that this problem is NP-complete; second, they derive a linear time algorithm for the special case that m equals 2.

Link: www.sciencedirect.com/science/article/pii/S0196677496900073

Advisor: Simon Pukrop

Topic 8:   Complexity of Machine Scheduling Problems

They survey and extend the results on the complexity of machine scheduling problems. After a brief review of the central concept of NP-completeness they give a classification of scheduling problems on single, different and identical machines and study the influence of various parameters on their complexity. The problems for which a polynomial-bounded algorithm is available are listed and NP-completeness is established for a large number of other machine scheduling problems.
This is an older Paper (1977) which established one of the first distinctions between "easy" and "hard" scheduling problems.

Link: https://www.sciencedirect.com/science/article/pii/S016750600870743X

Advisor: Simon Pukrop

Topic 9:   Three, four, five, six, or the complexity of scheduling with communication delays

A set of unit-time tasks has to be processed on identical parallel processors subject to precedence constraints and unit-time communication delays; does there exist a schedule of length at most d? The problem has two variants, depending on whether the number of processors is restrictively small or not. For the first variant the question can be answered in polynomial time for d = 3 and is NP-complete for d = 4. The second variant is solvable in polynomial time for d = 5 and NP-complete for d = 6. As a consequence, neither of the corresponding optimization problems has a polynomial approximation scheme, unless P = NP.

Link: https://www.sciencedirect.com/science/article/pii/0167637794900248

Advisor: Simon Pukrop


Topic 10:   Improving Online Algorithms via ML Predictions

In online scheduling, scheduling decisions have to be made without full knowledge of the instance, and in the non-clairvoyant setting, in particular, full knowledge about tasks and their processing times is only attained after they have been fully executed. The present paper considers two classical scheduling problems in this setting with an addition – the input includes guesses regarding some of the missing knowledge. These guesses could, for instance, be attained via machine learning. The authors design algorithms that are both consistent, i.e., outperform pure online algorithms if the predictions are good, and robust, i.e., do not perform too badly if the predictions are bad or even adversarial.

Citation:

Manish Purohit, Zoya Svitkina, Ravi Kumar: Improving Online Algorithms via ML Predictions. NeurIPS 2018: 9684-9693

Link: https://proceedings.neurips.cc/paper/2018/file/73a427badebe0e32caa2e1fc7530b7f3-Paper.pdf

Advisor: Marten Maack

Topic 11:  Distortion-Oblivious Algorithms for Minimizing Flow Time

The authors consider scheduling on a single machine with the goal of minimizing the total flow time in an online setting with predictions. Jobs arrive over time and upon arrival an estimate of the respective processing time is provided. However, these estimates may be distorted and the distortion can be measured by a parameter. The authors provide algorithms that can guarantee a certain solution quality depending on this parameter, without knowing the value of the parameter beforehand.

Citation:

Yossi Azar, Stefano Leonardi, Noam Touitou: Distortion-Oblivious Algorithms for Minimizing Flow Time. SODA 2022: 252-274

Link: https://arxiv.org/pdf/2109.08424.pdf

Advisor: Marten Maack

Topic 12:   Flow time scheduling and prefix Beck-Fiala

The authors draw a connection between discrepancy theory and scheduling problems on unrelated machines with the goal of minimizing the maximum or total flow

time. This leads to improved algorithmic results and shows that improvements for certain problems in discrepancy theory directly yield better algorithms for the scheduling problems.

Citation:

Nikhil Bansal, Lars Rohwedder, Ola Svensson: Flow time scheduling and prefix Beck-Fiala. STOC 2022: 331-342

Link: arxiv.org/abs/2202.02217

Advisor: Marten Maack


Topic 13:   Adaptive display algorithm for interactive frame rates during visualization of complex virtual environments

We describe an adaptive display algorithm for interactive frame rates during visualization of very complex virtual environments. The algorithm relies upon a hierarchical model representation in which objects are described at multiple levels of detail and can be drawn with various rendering algorithms. The idea behind the algorithm is to adjust image quality adaptively to maintain a uniform, user-specified target frame rate. We perform a constrained optimization to choose a level of detail and rendering algorithm for each potentially visible object in order to generate the “best” image possible within the target frame time. Tests show that the algorithm generates more uniform frame rates than other previously described detail elision algorithms with little noticeable difference in image quality during visualization of complex models.

Citation:

Thomas A. Funkhouser, Carlo H. Séquin: SIGGRAPH '93: Proceedings of the 20th annual conference on Computer graphics and interactive techniques, September 1993 Pages 247–254

Link:https://doi.org/10.1145/166117.166149

Advisor: André Graute

Topic 14:   Direct visibility of point sets

This paper proposes a simple and fast operator, the "Hidden" Point Removal operator, which determines the visible points in a point cloud, as viewed from a given viewpoint. Visibility is determined without reconstructing a surface or estimating normals. It is shown that extracting the points that reside on the convex hull of a transformed point cloud, amounts to determining the visible points. This operator is general - it can be applied to point clouds at various dimensions, on both sparse and dense point clouds, and on viewpoints internal as well as external to the cloud. It is demonstrated that the operator is useful in visualizing point clouds, in view-dependent reconstruction and in shadow casting.

Citation:

Sagi Katz, Ayellet Tal, Ronen Basri: ACM Transactions on Graphics, Volume 26, Issue 3, July 2007

Link: doi.org/10.1145/1276377.1276407

Advisor: André Graute

Topic 15:   Neural Sparse Voxel Fields

Photo-realistic free-viewpoint rendering of real-world scenes using classical computer graphics techniques is challenging, because it requires the difficult step of capturing detailed appearance and geometry models. Recent studies have demonstrated promising results by learning scene representations that implicitly encode both geometry and appearance without 3D supervision. However, existing approaches in practice often show blurry renderings caused by the limited network capacity or the difficulty in finding accurate intersections of camera rays with the scene geometry. Synthesizing high-resolution imagery from these representations often requires time-consuming optical ray marching. In this work, we introduce Neural Sparse Voxel Fields (NSVF), a new neural scene representation for fast and high-quality free-viewpoint rendering. NSVF defines a set of voxel-bounded implicit fields organized in a sparse voxel octree to model local properties in each cell. We progressively learn the underlying voxel structures with a differentiable ray-marching operation from only a set of posed RGB images. With the sparse voxel octree structure, rendering novel views can be accelerated by skipping the voxels containing no relevant scene content. Our method is typically over 10 times faster than the state-of-the-art (namely, NeRF(Mildenhall et al., 2020)) at inference time while achieving higher quality results. Furthermore, by utilizing an explicit sparse voxel representation, our method can easily be applied to scene editing and scene composition. We also demonstrate several challenging tasks, including multi-scene learning, free-viewpoint rendering of a moving human, and large-scale scene rendering. Code and data are available at our website: this https URL.

Citation:

Lingjie Liu, Jiatao Gu, Kyaw Zaw Lin, Tat-Seng Chua, Christian Theobalt: 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada

Link: doi.org/10.48550/arXiv.2007.11571

Advisor: André Graute


Topic 16:   Dynamic Perfect Hashing

The dynamic dictionary problem is considered: provide an algorithm for storing a dynamic set, allowing the operations insert, delete, and lookup. A dynamic perfect hashing strategy is given: a randomized algorithm for the dynamic dictionary problem that takes O(1) worst-case time for lookups and O(1) amortized expected time for insertions and deletions; it uses space proportional to the size of the set stored. Furthermore, lower bounds for the time complexity of a class of deterministic algorithms for the dictionary problem are proved.

Literature:

M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, R. Tarjan: Dynamic Perfect Hashing: Upper and Lower Bounds. Siam J. Comput., Vol. 23, No. 4, pp. 738-761 (1994)

Advisor: Friedhelm Meyer auf der Heide

Topic 17:   Efficient Simulations among Several Models of Parallel Computers

A parallel computer (PC) with fixed communication network is called fair if the degree of this network is bounded, otherwise it is called unfair. In a PC with predictable communication each processor can precompute the addresses of the processors it wants to communicate with in the next t steps  in O(t) steps.
For an arbitrary \epsilon >0 we define fair PCs M and M’ with O(n+epsilon) processors, each. M (M’) can simulate each unfair PC with predictable communication and O(log(n)) storage locations per processor (each fair PC) with n processors with constant time loss.

Literatur:

Friedhelm Meyer auf der Heide: Efficient Simulations Among Several Models of Parallel Computers. SIAM J. Comput. 15(1): 106-119 (1986)

https://epubs.siam.org/doi/epdf/10.1137/0215008

Advisor: Friedhelm Meyer auf der Heide

Topic 18:   Efficiency of Universal Parallel Computers

We consider parallel computers (PCs) with fixed communication network and bounded degree. We deal with the following question: How efficiently can one PC, a so-called universal PC, simulate each PC with n processors? Previously, a universal PC with O(n) processors and time loss O(log(n)) was constructed. In this seminar talk we define three types of simulations the most general of which includes all known simulations. We prove non-linear time-processor tradeoffs for universal PCs associated with the above types.

Literature:

Friedhelm Meyer auf der Heide: Efficiency of Universal Parallel Computers. Acta Informatica 19: 269-296 (1983)

https://link.springer.com/content/pdf/10.1007/BF00265559.pdf

Advisor: Friedhelm Meyer auf der Heide


Topic 19:   The Structural Power of Reconfigurable Circuits in the Amoebot Model

Padalkin, Andreas ; Scheideler, Christian ; Warner, Daniel

The amoebot model [Derakhshandeh et al., SPAA 2014] has been proposed as a model for programmable matter consisting of tiny, robotic elements called amoebots. We consider the reconfigurable circuit extension [Feldmann et al., JCB 2022] of the geometric (variant of the) amoebot model that allows the amoebot structure to interconnect amoebots by so-called circuits. A circuit permits the instantaneous transmission of signals between the connected amoebots. In this paper, we examine the structural power of the reconfigurable circuits.
We start with some fundamental problems like the stripe computation problem where, given any connected amoebot structure S, an amoebot u in S, and some axis X, all amoebots belonging to axis X through u have to be identified. Second, we consider the global maximum problem, which identifies an amoebot at the highest possible position with respect to some direction in some given amoebot (sub)structure. A solution to this problem can then be used to solve the skeleton problem, where a (not necessarily simple) cycle of amoebots has to be found in the given amoebot structure which contains all boundary amoebots. A canonical solution to that problem can then be used to come up with a canonical path, which provides a unique characterization of the shape of the given amoebot structure. Constructing canonical paths for different directions will then allow the amoebots to set up a spanning tree and to check symmetry properties of the given amoebot structure.
The problems are important for a number of applications like rapid shape transformation, energy dissemination, and structural monitoring. Interestingly, the reconfigurable circuit extension allows polylogarithmic-time solutions to all of these problems.

drops.dagstuhl.de/opus/volltexte/2022/16793

Advisor: Jonas Harbig

Topic 20:   On the Computational Power of Energy-Constrained Mobile Robots: Algorithms and Cross-Model Analysis.

Kevin Buchin, Paola Flocchini, Irina Kostitsyna, Tom Peters, Nicola Santoro and Koichi Wada.

We consider distributed systems of identical autonomous computational entities, called robots, moving and operating in the plane in synchronous Look - Compute - Move (LCM ) cycles. The algorithmic capabilities of these systems have been extensively investigated in the literature under four distinct models (OBLOT, FSTA, FCOM, LUMI ), each identifying different levels of memory persistence and communication capabilities of the robots. Despite their differences, they all always assume that robots have unlimited amounts of energy. In this paper, we remove this assumption and start the study of the computational capabilities of robots whose energy is limited, albeit renewable. We first study the impact that memory persistence and communication capabilities have on the computational power of such energy-constrained systems of robots; we do so by analyzing the computational relationship between the four models under this energy constraint. We provide a complete characterization of this relationship. We then study the difference in computational power caused by the energy restriction and provide a complete characterization of the relationship between energy-constrained and unrestricted robots in each model. We prove that within LUMI there is no difference; an integral part of the proof is the design and analysis of an algorithm that in LUMI allows energy-constrained robots to execute correctly any protocol for robots with unlimited energy. We then show the (apparently counterintuitive) result that in all other models, the energy constraint actually provides the robots with a computational advantage.

https://link.springer.com/chapter/10.1007/978-3-031-09993-9_3

Advisor: Jonas Harbig


Submission of your Seminar Thesis

The thesis has to be created with LaTeX using our customized template, which you can download here, or you can clone the git-repository. We will create a complete volume consisting of all submissions.

You have to submit the LaTeX sources (your subfolder from the template is enough) AND a complete pdf of your seminar thesis. All files should be contained in only one zip or tar.gz file. Please do NOT include your matriculation number in your thesis.

For the LaTeX document you have to follow the following rules:

  • Each author gets his own prefix. (Example: the author "Matthias Fischer" gets his unique prefix "MaFi". Make sure there are no conflicts with other students.)
  • All your LaTeX files and pictures have to be contained in a single subfolder of the template using your prefix as name.
  • There is only one "*.tex" file for your complete seminar thesis.
  • The name of your LaTeX file consists only of your prefix supplemented by the suffix ".tex" (e.g., "MaFi.tex").
  • You can modify the "SI" folder and "SI.tex" in the template as a starting point.
  • The document must be compiled with pdflatex. Hence, pictures must be included as pdf, jpg or png.
  • To compile the document, you need to include your LaTeX file by adding the command "\includeseminar{...}" to the "main.tex" file in the root folder. (e.g., "\includeseminar{MaFi/MaFi}")
  • Your file must be encoded in UTF-8.
  • Your highest breakdown-level is \section. (Thus, you can use \section, \subsection, \subsubsection, \paragraph, etc.)
  • To distinguish all self-defined commands, labels and references, each author gets his own prefix. (Example: the author "Matthias Fischer" gets his unique prefix "MaFi".)
  • Each command, label and reference consists of the prefix, followed by an individual identifier. Thus, if Matthias wants to call a label "myCoolLabel", the label has to be defined by \label{MaFi:MyCoolLabel}.
  • After the \maketitle call in your LaTeX document, you have to add your abstract with the command "\abstract{ ... }". After the abstract add your local table of contents with the commands "\makeminitoc".
  • We only use the svmult theorem environment. This means, the option "nospthms" and the package "amsthm" can not be used. (The package "amsthm" is not compatible to "svmult".)
  • We do not use the BibTeX compiler to process literature references. Instead of this, you have to add your literature references like presented in the template file "SI.tex". You have to follow the style given in the template file, i.e., "author, title, year,...".
  • To format the pseudocode of your algorithms you can either use algorithmicx together with its floating environment "algorithm" from the package algorithms, or you can use the listings environment. We recommend to start with predefined commands as given by package algpseudocode. We do not use the package "algorithmic".
  • You are not allowed to modify the "main.tex" file (apart from the \includeseminar command) or any other file in the root folder of the template. This also means, that you cannot use any other packages as specified in the main file.