5,627 Works

From Observations to Prediction of Movement (Dagstuhl Seminar 18282)

Mark Birkin, Somayeh Dodge, Brittany Terese Fasy & Richard Philip Mann
This report documents the program and the outcomes of Dagstuhl Seminar 17282 "From Observations to Prediction of Movement". This seminar brought together researchers from Animal Behaviour, GIS, Computational Geometry, Data Science and other fields to exchange insights from these diverse fields. Presentations focused both on outstanding practical questions, as well as on fundamental mathematical and computational tools.

Malware Analysis: From Large-Scale Data Triage to Targeted Attack Recognition (Dagstuhl Seminar 17281)

Sarah Zennou, Saumya K. Debray, Thomas Dullien & Arun Lakhothia
This report summarizes the program and the outcomes of the Dagstuhl Seminar 17281, entitled "Malware Analysis: From Large-Scale Data Triage to Targeted Attack Recognition". The seminar brought together practitioners and researchers from industry and academia to discuss the state-of-the art in the analysis of malware from both a big data perspective and a fine grained analysis. Obfuscation was also considered. The meeting created new links within this very diverse community.

Citizen Science: Design and Engagement (Dagstuhl Seminar 17272)

Irene Celino, Oscar Corcho, Franz Hölker & Elena Simperl
This report documents the program and the outcomes of Dagstuhl Seminar 17272 "Citizen Science: Design and Engagement". In this report, we detail the briefly summarise the content of three invited keynote talks and two invited tutorials. We further outline the findings of five parallel working groups, which met on the first and third day of the workshop, in the areas of: sustainability, measuring success, community engagement, linking and quality.

Dagstuhl Manifestos, Table of Contents, Volume 6, Issue 1, 2016-2017

Marc Herbstritt
Dagstuhl Manifestos, Table of Contents, Volume 6, Issue 1, 2016-2017

Dagstuhl Reports, Table of Contents, Volume 7, Issue 4, 2017

Marc Herbstritt
Table of Contents, Frontmatter

Dagstuhl Reports, Table of Contents, Volume 7, Issue 6, 2017

Marc Herbstritt
Table of Contents, Frontmatter

Dagstuhl Reports, Table of Contents, Volume 7, Issue 5, 2017

Marc Herbstritt
Table of Contents, Frontmatter

Analysis and Synthesis of Floating-point Programs (Dagstuhl Seminar 17352)

Eva Darulova, Alastair F. Donaldson, Zvonimir Rakamaric & Cindy Rubio-González
This report summarises the presentations, discussion sessions and panel that took place during the Dagstuhl seminar on "Analysis and Synthesis of Floating-point Programs" that took place during August 27 - 30, 2017. We hope that the report will provide a useful resource for researchers today who are interested in understanding the state-of-the-art and open problems related to analysing and synthesising floating-point programs, and as a historical resource helping to clarify the status of this field...

Machine Learning and Formal Method (Dagstuhl Seminar 17351)

Sanjit A. Seshia, , Andreas Krause & Susmit Jha
This report documents the program and the outcomes of Dagstuhl Seminar 17351 "Machine Learning and Formal Methods". The seminar brought together practitioners and reseachers in machine learning and related areas (such as robotics) with those working in formal methods and related areas (such as programming languages and control theory). The meeting highlighted the connections between the two disciplines, and created new links between the two research communities.

SLEBOK: The Software Language Engineering Body of Knowledge (Dagstuhl Seminar 17342)

Benoît Combemale, Ralf Lämmel & Eric Van Wyk
This report documents the program and the outcomes of Dagstuhl Seminar 17342 "SLEBOK: The Software Language Engineering Body of Knowledge". Software Language Engineering (SLE) has emerged as a scientific field, with a strong motivation to connect and integrate different research disciplines such as compiler construction, reverse engineering, software transformation, model-driven engineering, and ontologies. This seminar supported further integration of said communities with the clear objective of assembling a Body of Knowledge on SLE (SLEBoK). The...

Scalable Set Visualizations (Dagstuhl Seminar 17332)

Yifan Hu, Luana Micallef, Martin Nöllenburg & Peter Rodgers
This report documents the program and outcomes of Dagstuhl Seminar 17332 "Scalable Set Visualizations", which took place August 14--18, 2017. The interdisciplinary seminar brought together 26 researchers from different areas in computer science and beyond such as information visualization, human-computer interaction, graph drawing, algorithms, machine learning, geography, and life sciences. During the seminar we had five invited overview talks on different aspects of set visualizations as well as a few ad-hoc presentations of ongoing work....

Computational Counting (Dagstuhl Seminar 18341)

Ivona Bezáková, Leslie Ann Goldberg & Mark R. Jerrum
This report documents the program and the outcomes of Dagstuhl Seminar 17341 "Computational Counting". The seminar was held from 20th to 25th August 2017, at Schloss Dagstuhl -- Leibnitz Center for Informatics. A total of 43 researchers from all over the world, with interests and expertise in different aspects of computational counting, actively participated in the meeting.

Foundations of Wireless Networking (Dagstuhl Seminar 17271)

Christina Fragouli, Magnús M. Halldórson, Kyle Jamieson & Bhaskar Krishnamachari
This report documents the talks and discussions of Dagstuhl Seminar 17271 "Foundations of Wireless Networking". The presented talks represent a wide spectrum of work on wireless networks.

Graph Clustering using Effective Resistance

Vedat Levi Alev, Nima Anari, Lap Chi Lau & Shayan Oveis Gharan
We design a polynomial time algorithm that for any weighted undirected graph G = (V, E, w) and sufficiently large \delta > 1, partitions V into subsets V(1),..., V(h) for some h>= 1, such that at most \delta^{-1} fraction of the weights are between clusters, i.e. sum(i < j) |E(V(i), V(j)| < w(E)/\delta and the effective resistance diameter of each of the induced subgraphs G[V(i)] is at most \delta^3 times the inverse of the average...

ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network

Irit Dinur & Pasin Manurangsi
We study 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph G = (V,E), an alphabet set Sigma and, for each edge {u, v}, a constraint C_uv, the goal is to find an assignment sigma from V to Sigma that satisfies as many constraints as possible, where a constraint C_uv is said to be satisfied by sigma if C_uv contains (sigma(u),sigma(v)). While the approximability of 2-CSPs is quite well...

Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers

Jacob Steinhardt, Moses Charikar & Gregory Valiant
We introduce a criterion, resilience, which allows properties of a dataset (such as its mean or best low rank approximation) to be robustly computed, even in the presence of a large fraction of arbitrary additional data. Resilience is a weaker condition than most other properties considered so far in the literature, and yet enables robust estimation in a broader variety of settings. We provide new information-theoretic results on robust distribution learning, robust estimation of stochastic...

Pseudo-Deterministic Proofs

Shafi Goldwasser, Ofer Grossman & Dhiraj Holden
We introduce pseudo-deterministic interactive proofs (psdIP): interactive proof systems for search problems where the verifier is guaranteed with high probability to output the same output on different executions. As in the case with classical interactive proofs, the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover. We view pseudo-deterministic interactive proofs as an extension of the study of pseudo-deterministic randomized polynomial time algorithms: the goal of the latter is to find...

Foundations of Homomorphic Secret Sharing

Elette Boyle, Niv Gilboa, Yuval Ishai, Huijia Lin & Stefano Tessaro
Homomorphic secret sharing (HSS) is the secret sharing analogue of homomorphic encryption. An HSS scheme supports a local evaluation of functions on shares of one or more secret inputs, such that the resulting shares of the output are short. Some applications require the stronger notion of additive HSS, where the shares of the output add up to the output over some finite Abelian group. While some strong positive results for HSS are known under specific...

Learning Dynamics and the Co-Evolution of Competing Sexual Species

Georgios Piliouras & Leonard J. Schulman
We analyze a stylized model of co-evolution between any two purely competing species (e.g., host and parasite), both sexually reproducing. Similarly to a recent model [Livnat et al. FOCS'14] the fitness of an individual depends on whether the truth assignments on n variables that reproduce through recombination satisfy a particular Boolean function. Whereas in the original model a satisfying assignment always confers a small evolutionary advantage, in our model the two species are in an...

Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs

Shay Solomon
In graph sparsification, the goal has almost always been of global nature: compress a graph into a smaller subgraph (sparsifier) that maintains certain features of the original graph. Algorithms can then run on the sparsifier, which in many cases leads to improvements in the overall runtime and memory. This paper studies sparsifiers that have bounded (maximum) degree, and are thus locally sparse, aiming to improve local measures of runtime and memory. To improve those local...

Recovering Structured Probability Matrices

Qingqing Huang, Sham M. Kakade, Weihao Kong & Gregory Valiant
We consider the problem of accurately recovering a matrix B of size M by M, which represents a probability distribution over M^2 outcomes, given access to an observed matrix of "counts" generated by taking independent samples from the distribution B. How can structural properties of the underlying matrix B be leveraged to yield computationally efficient and information theoretically optimal reconstruction algorithms? When can accurate reconstruction be accomplished in the sparse data regime? This basic problem...

An Axiomatic Study of Scoring Rule Markets

Rafael Frongillo & Bo Waggoner
Prediction markets are well-studied in the case where predictions are probabilities or expectations of future random variables. In 2008, Lambert, et al. proposed a generalization, which we call "scoring rule markets" (SRMs), in which traders predict the value of arbitrary statistics of the random variables, provided these statistics can be elicited by a scoring rule. Surprisingly, despite active recent work on prediction markets, there has not yet been any investigation into more general SRMs. To...

Long Term Memory and the Densest K-Subgraph Problem

Robert Legenstein, Wolfgang Maass, Christos H. Papadimitriou & Santosh S. Vempala
In a recent experiment, a cell in the human medial temporal lobe (MTL) encoding one sensory stimulus starts to also respond to a second stimulus following a combined experience associating the two. We develop a theoretical model predicting that an assembly of cells with exceptionally high synaptic intraconnectivity can emerge, in response to a particular sensory experience, to encode and abstract that experience. We also show that two such assemblies are modified to increase their...

Further Limitations of the Known Approaches for Matrix Multiplication

Josh Alman & Virginia Vassilevska Williams
We consider the techniques behind the current best algorithms for matrix multiplication. Our results are threefold. (1) We provide a unifying framework, showing that all known matrix multiplication running times since 1986 can be achieved from a single very natural tensor - the structural tensor T_q of addition modulo an integer q. (2) We show that if one applies a generalization of the known techniques (arbitrary zeroing out of tensor powers to obtain independent matrix...

Matrix Completion and Related Problems via Strong Duality

Maria-Florina Balcan, Yingyu Liang, David P. Woodruff & Hongyang Zhang
This work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and its dual have the same optimum. This has been well understood for convex optimization, but little was known for non-convex problems. We propose a novel analytical framework and show that under certain dual conditions, the optimal solution of the matrix factorization program is the same as its bi-dual and thus the global optimality of...

Resource Types

  • Text
  • Software

Publication Year

  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006

Registration Year

  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009