Lunch Seminar Theoretical Computer Science

This is the joint research seminar by the theory groups in the department of computer science. We discuss various topics in the wide area of algorithms, theoretical computer science, learning theory, computational social choice, etc.

When: Thursday 12:15 - 13:15, theory lounge (B 116, Sand 13).

How:

• If you attend the seminar, you are welcome to bring your lunch with you.
• If you present something in the seminar: the talk is supposed to be at most 45 min (including discussion, we would like to finish after 60 min). Remember that attendants have very diverse backgrounds, do not assume that they have any knowledge in your particular field (aim your talk to the level of a Master student, then it should be fine). If your talk is interactive, or you have little puzzles in between, all the better :-)

Comments? Questions? Want to be added to the mailing list? Want to present something? Talk to Ulrike von Luxburg.

Upcoming meetings

Past Meetings

• 13.7.2017 Talk by Abbas Mehrabian (UBC): PAC learning mixtures of Gaussians

  Abstract: We consider PAC learning of probability distributions (aka density estimation), where we are given an iid sample generated from an unknown target distribution, and want to output a distribution that is close to the target in total variation distance. First, we show that the class of mixtures of k axis-aligned Gaussians in R^d is PAC-learnable with sample complexity O(kd/epsilon^4), which is tight in k and d. Second, we show that the class of mixtures of k Gaussians in R^d is PAC-learnable in the agnostic setting with sample complexity O(kd^2/epsilon^4). This is joint work with Hassan Ashtiani and Shai Ben-David, and is available at arXiv:1706.01596.

• 1.6.2017 Talk by Nutan Limaye (IIT Bombay): Isolation Lemma for Directed Reachability and NL vs. L

  Abstract: We discuss versions of isolation lemma for problems in NP and NL. We then show that improving the success probability of the isolation lemma is equivalent to some complexity theoretic collapses such as NP is in P/poly and NL is in L/poly. Basic familiarity with complexity classes such as NP, P/poly, NL will be assumed. All the other notions used in the talk will be introduced during the talk.

• 22.6.2017 Ulrike will demonstrate her ``Envelope Computer'': a machine, built from nothing but envelopes and sheets of papers, that can learn to play Tic Tac Toe (used to demonstrate machine learning to school kids, no science involved, but fun to see).
• 11.5.2017 Talk by Henry Förster: Smooth Orthogonal and Octilinear Drawings of Low Edge Complexity

  Abstract: Orthogonal graph drawing is a deeply studied and well established model for graph drawing with efficient algorithms providing good aesthetics and readability. Two models research has focused on in recent years are smooth orthogonal graph drawing and octilinear graph drawing which both can be regarded as extensions of orthogonal graph drawing. In particular bend minimization appears to be more difficult for these new concepts than in the orthogonal model yet NP-hardness results are missing for the smooth orthogonal model and are limited to graphs with maximum degree of at least 6 in the octilinear model. We analyze relationships between the graph classes which can be drawn bendless in those two new models and show that there is both a cut and a symmetric difference. Further we prove NP-hardness for a restricted version of the bendless drawing problem on 4-planar graphs for both the smooth orthogonal and the octilinear model. Finally we present a drawing technique that produces bi-monotone drawings with at most one bend per edge in both models where we also can guarantee a linear number of bendless edges in the smooth orthogonal model.

• 27.4.2017 Guest talk by Nikhil Balaji: Some questions around Skolem's problem

  A linear recurrence sequence is an infinite sequence of numbers with the property that the n-th term in the sequence can be expressed as a linear function of a fixed number of its previous terms. Linear recurrences have been investigated by mathematicians and computer scientists for centuries now. One of the most extensively studied linear recurrence is of course the Fibonacci sequence, which pops up in fields in diverse areas of engineering, mathematics, to biology. In this talk, I'll present a classic computational problem relating to linear recurrences, which remains unsolved and which finds application in several areas of computer science (linear program termination, probabilistic automata), theoretical biology (analysis of L-systems, population biology) and combinatorics (generating functions).

• 16.2. 2017 No lunch seminar, but everybody welcome to attend the crowd sourcing seminar
• 9.2.2017 Talk by Michael Perrot, Université Saint-Étienne: Learning Metrics with a Controlled Behaviour

  Abstract: The goal in Machine Learning is to acquire new knowledge from data. To achieve this many algorithms make use of a notion of distance or similarity between examples. A very representative example is the nearest neighbour classifier which is based on the idea that two similar examples should share the same label: it thus critically depends on the notion of metric considered. Depending on the task at hand these metrics should have different properties but manually choosing an adapted comparison function can be tedious and difficult. The idea behind Metric Learning is to automatically tailor such metrics to the problem at hand. One of the main limitation of standard methods is that the control over the behaviour of the learned metrics is often limited. In this talk I will present two approaches specifically designed to overcome this problem. In the first one we consider a general framework able to take into account a reference metric acting as a guide for the learned metric. We are then interested in theoretically studying the interest of using such side information. In the second approach we propose to control the underlying transformation of the learned metric. Specifically we use some recent advances in the field of Optimal Transport to force it to follow a particular geometrical transformation.

• 2.2.2017 Talk by Klaus-Jörn Lange: Dense Completeness. The talk presents (surprisingly?) deep conections between complexity theory and the theory of formal languages.
• 26.1.2017 Talk by Michael Kaufmann: Stack and queue layouts via layered separators
• 19.1.2017 Talk by Patrizio Angelini: Title: Clustered Planarity with Pipes

  Abstract: We study the version of the C-Planarity problem in which edges connecting the same pair of clusters must be grouped into pipes, which generalizes the Strip Planarity problem. We give algorithms to decide several families of instances for the two variants in which the order of the pipes around each cluster is given as part of the input or can be chosen by the algorithm.

• 1.12.2016 Paper discussion: Backurs, A., Indyk, P.: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). STOC 2015
• 24.11.2016 Talk by Ronald de Haan (TU Wien): Complexity Results for Judgment Aggregation.

  Abstract: Judgment aggregation is a subfield of computational social choice that focuses on the process of aggregating individual opinions on a set of logically related issues into a single collective opinion. We will explain the basic concepts that play a role in the area of judgment aggregation. We will discuss several aggregation procedures that have been considered in the literature. Moreover, we consider several computational problems that play a role in judgment aggregation, and we discuss some recent (parameterized) complexity results for these problems.

• 17.11.2016 Talk by Giordano da Lozzo (Roma3, now Irvine): Intersection-Link Representations of Graphs

  Abstract: We consider drawings of graphs that contain dense subgraphs. We introduce intersection- link representations for such graphs, in which each vertex u is represented by a geometric object R(u) and in which each edge (u,v) is represented by the intersection between R(u) and R(v) if it belongs to a dense subgraph or by a curve connecting the boundaries of R(u) and R(v) otherwise. We study a notion of planarity, called Clique Planarity, for intersection-link representations of graphs in which the dense subgraphs are cliques.

• 3.11.2016, 12:15 Talk by Debarghya Ghoshdastidar: Two sample tests for random graphs
• 27.10.2016 12:15 Talk by Martin Beaudry (Univ. Sherbrooke, Quebec, Canada): Rock-Paper-Scissors

  Rock-Paper-Scissors: Using a well-known game as a pretext to look into the theory of formal languages. The Rock-Paper-Scissors game can be used (in a convoluted way) to define a formal language. Interestingly, proving that this language is regular can be done with tools and concepts that are seen in most undergraduate courses on languages, grammars, and automata.

• 20.10.2016 Talk by Ulrike von Luxburg: Theory of machine learning: data with little structure
• 11.10.2016, 12:15 Talk by Fabrizio Montecciani from Perugia: 1-Bend RAC Drawings of 1-Planar Graphs

  Graph Drawing is an area of computer science that studies models and algorithms for the representation of graphs. An emerging research line in Graph Drawing studies families of non-planar graphs that can be drawn so that crossing edges verify some desired properties. This topic is informally recognized as “beyond planarity”. Different types of properties give rise to different families of beyond planar graphs. Among them, particular attention has been devoted to 1-planar graphs and to RAC (Right Angle Crossing) drawable graphs. A graph is 1-planar if it has a drawing where each edge is crossed at most once. A drawing is RAC if the edges cross only at right angles. The relationships between 1-planar graphs and RAC drawings have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC drawable and graphs that have a straight-line RAC drawing but that are not 1-planar. One of the main questions still open is whether every 1-planar graph has a RAC drawing with at most one bend per edge. We positively answer this question.

• 4.10.2016, 12:15 Talk by Martin Groenemann from Köln, about 2-page book embeddings
• 19.7.2016 PCP Theorem 2: We watch the second half of online crash course of Luca Trevisan (starting at minute 55 roughly)
• 12.7.2016 PCP Theorem 1: We watch the first half of online crash course of Luca Trevisan
• 5.7.2016 Talk by Sebastian Schoener: An Introduction to Stone Duality

  Abstract: Stone Duality is the study of a collection of categorical dualities that connect order-theoretic structures with topological spaces. In the last years, this duality has found its application in Formal Language Theory. In this introductory talk, we will consider the duality that connects Boolean algebras with certain topological objects, namely Boolean spaces (these are the profinite spaces). We will discuss a very concrete instance of this duality and hint at Stone Duality's usefulness in Formal Language Theory. No prior exposure to topology or category theory is assumed.

• 28.6.2016 Open problem session
• 21.6.2016 Talk by Michael Kaufmann: Experimental approaches for book embedding problems.

  Abstract: In a book embedding, the vertices of a graph are placed on the spine of a book and the edges are assigned to pages, so that edges of the same page do not cross. In 1986, Yannakakis gave a very complicated algorithm for book embedding any given planar graph on four pages. It is open since then, whether four pages are necessary or three pages suffice. I will present our approach to this problem by means of SAT solving, discuss the (mostly negative) findings and show how we developed new hypotheses that might help to solve this problem and some related ones.

• 14.6.2016 Talk by Janosch Doecker: Monotone SAT variants with bounded variable appearances.
  Abstract: We consider variants of the monotone satisfiability problem for boolean formulae in conjunctive normal form (Monotone SAT) with bounded variable appearances (monotone means that for each clause either all contained literals are positive or all of them are negative, respectively). The talk presents results of our research on these problems and is divided into three parts: 1) NP-completeness of Monotone 3-SAT-4 (each clause contains exactly three distinct literals and every variable appears at most four times in the formula) 2) NP-complete planar variants of Monotone SAT with bounded variable appearances 3) Discussion of an open question for the planar case
• 7.7.2016 Talk by Ruth Urner (MPI for Intelligent Systems, Tübingen): Learning Economic Parameters from Revealed Preferences

  Abstract: A common assumption in Economics is that agents are utility maximizers: an agent, facing prices for a set of goods, will choose to buy the bundle of goods that she most prefers among all bundles that she can afford, according to some concave, non-decreasing utility function. In the classical revealed preference analysis, the goal is to fit some concave, non-decreasing model to data from an agents past purchases. However, due to the richness of this model class, this approach will not generalize to predict future purchases well. A recent line of work, starting with Beigman and Vohra (2006) and Zadimoghaddam and Roth (2012), has addressed this issue by suggesting to learn restricted classes of utility function from revealed preference data.

  This talk will present recent advances in this line of work. We provide sample complexity guarantees and efficient algorithms for learning linear utility functions from revealed preference data. At a technical level, our work establishes connections between learning from revealed preferences and problems of multi-class learning, combining recent advances on sample complexity of multi-class learning based on compression schemes with a new algorithmic analysis yielding time- and sample-efficient procedures. Our technique yields numerous generalizations including the ability to learn other well-studied classes of utility functions, to deal with a misspecified model, and with non-linear prices. This may lead (and actually has lead already) to new solutions to a variety of learning problems in economic and game theoretic contexts.This talk is based on a joint work with Nina Balcan, Amit Daniely, Ruta Mehta and Vijay V. Vazirani, that appeared at WINE 14.

• 31.5.2016 Speaker: Stephen Kobourov, U.Arizona
  Proportional Contact Representation of Planar Graphs

  Abstract: In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. We show how to use Schnyder realizers and canonical orders for planar graphs to obtain different types of contact representations. Specifically, we describe an algorithm that guarantees 10-sided rectilinear polygons and runs in linear time. We also describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time.

• 10.5.2016 Tutorial on spectral graph theory 3 (Ulrike von Luxburg): Some theoretic results.
  I mainly discuss the contents of the paper Statistical-computational tradeoffs in planted problems and submatrix localization. Chen, Xu, JMLR 2015.
• 3.5. 2016 Tutorial on spectral graph theory 2 (Ulrike von Luxburg): Interactive Demo of Spectral clustering.
• 26.4.2016 Tutorial on spectral graph theory 1 (Ulrike von Luxburg): The basics
• 19.4.2016Talk by Sebastian Schneckenburger: Rental Harmony : Sperner’s lemma in fair division
• 12.4.2016 Tutorial by Britta Dorn: Cake cutting
• 7.4. 2016 Talk by Ulle Endriss (University of Amsterdam): Fair Allocation of Indivisible Goods
• 17.3.2016 Complexity and formal languages: Talk by Michael Ludwig on Visibility
  The concept of visibility has been reinvented several times. We are interested both in its algebraic characterizations in order to solve both some open decidability questions, and in its formal language features in order to shed some light on its complexity.
• 10.3.2016 Complexity and formal languages: Talk by Michael Cadilhac on formal languages
• 3.3.2016 Complexity and formal languages: Talk by Klaus-Jörn Lange on Complexity
  Abstract: We begin with an overview about the sad situation of complexity theory: an indication of the problems and of the meta-results indicating how difficult these problems are. The talk includesreferences to our current work which is introduced in the following two talks.
• 25.2.2016 Ordinal data analysis: Working session on open problems in the domain of ordinal data analysis
• 4.2.2016 Ordinal data analysis: Talk by Matthaeus Kleindessner on ordinal embeddings
• 18.2.2016 Ordinal data analysis: Talk by Siavash Haghiri: Data structures for comparison-based nearest neighbor search
• 28.1.2016: Ply numbers and proximity: A closer look to a specific problem
• 21.1.2016: Ply numbers and proximity: Algorithms
• 14.1.2016: Ply numbers and proximity: Overview