8,466 Works

Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits

Ruiwen Chen, Rahul Santhanam & Srikanth Srinivasan
We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is epsilon_d > 0 such that Parity has correlation at most 1/n^{Omega(1)} with depth-d threshold circuits which have at most n^{1+epsilon_d} wires, and the Generalized Andreev Function has correlation at most 1/2^{n^{Omega(1)}} with depth-d threshold circuits which have at most n^{1+epsilon_d} wires. Previously, only worst-case lower...

Semantic Data Management (Dagstuhl Seminar 12171)

Grigoris Antoniou, Oscar Corcho, Karl Aberer, Elena Simperl & Rudi Studer
This report documents the program and the outcomes of Dagstuhl Seminar 12171 "Semantic Data Management". The purpose of the seminar was to have a fruitful exchange of ideas between the semantic web, database systems and information retrieval communities, organised across four main themes: scalability, provenance, dynamicity and search. Relevant key questions cutting across all of these themes were: (i) how can existing DB and IR solutions be adapted to manage semantic data; and (ii) are...

Contracts in the Wild: A Study of Java Programs (Artifact)

Jens Dietrich, David J. Pearce, Kamil Jezek & Premek Brada
This artefact contains a dataset of open-source programs obtained from the Maven Central Repository and scripts that first extract contracts from these programs and then perform several analyses on the contracts extracted. The extraction and analysis is fully automated and directly produces the tables presented in the accompanying paper. The results show how contracts are used in real-world program, and how their usage changes between versions and within inheritance hierarchies.

Domain-Aware Session Types

Luís Caires, Jorge A. Pérez, Frank Pfenning & Bernardo Toninho
We develop a generalization of existing Curry-Howard interpretations of (binary) session types by relying on an extension of linear logic with features from hybrid logic, in particular modal worlds that indicate domains. These worlds govern domain migration, subject to a parametric accessibility relation familiar from the Kripke semantics of modal logic. The result is an expressive new typed process framework for domain-aware, message-passing concurrency. Its logical foundations ensure that well-typed processes enjoy session fidelity, global...

Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling

Deeparnab Chakrabarty & Sanjeev Khanna
Given a non-negative real matrix A, the matrix scaling problem is to determine if it is possible to scale the rows and columns so that each row and each column sums to a specified target value for it. The matrix scaling problem arises in many algorithmic applications, perhaps most notably as a preconditioning step in solving linear system of equations. One of the most natural and by now classical approach to matrix scaling is the...

Pruning 2-Connected Graphs

Chandra Chekuri & Nitish Korula
Given an edge-weighted undirected graph $G$ with a specified set of terminals, let the \emph{density} of any subgraph be the ratio of its weight/cost to the number of terminals it contains. If $G$ is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of $G$? We answer this question in the affirmative by giving an algorithm to \emph{prune} $G$ and find such subgraphs of any desired size, at the cost of only...

Towards the Usefulness of User-Generated Content to Understand Traffic Events (Short Paper)

Rahul Deb Das & Ross S. Purves
This paper explores the usefulness of Twitter data to detect traffic events and their geographical locations in India through machine learning and NLP. We develop a classification module that can identify tweets relevant for traffic authorities with 0.80 recall accuracy using a Naive Bayes classifier. The proposed model also handles vernacular geographical aspects while retrieving place information from unstructured texts using a multi-layered georeferencing module. This work shows Mumbai has a wide spread use of...

Definable Operations On Weakly Recognizable Sets of Trees

Jacques Duparc, Alessandro Facchini & Filip Murlak
Alternating automata on infinite trees induce operations on languages which do not preserve natural equivalence relations, like having the same Mostowski--Rabin index, the same Borel rank, or being continuously reducible to each other (Wadge equivalence). In order to prevent this, alternation needs to be restricted to the choice of direction in the tree. For weak alternating automata with restricted alternation a small set of computable operations generates all definable operations, which implies that the Wadge...

Bridging the Gap Between General-Purpose and Domain-Specific Compilers with Synthesis

Alvin Cheung, Shoaib Kamil & Armando Solar-Lezama
This paper describes a new approach to program optimization that allows general purpose code to benefit from the optimization power of domain-specific compilers. The key to this approach is a synthesis-based technique to raise the level of abstraction of general-purpose code to enable aggressive domain-specific optimizations. We have been implementing this approach in an extensible system called Herd. The system is designed around a collection of parameterized kernel translators. Each kernel translator is associated with...

Petri Net Reachability Graphs: Decidability Status of FO Properties

Philippe Darondeau, Stéphane Demri, Roland Meyer & Christophe Morvan
We investigate the decidability and complexity status of model-checking problems on unlabelled reachability graphs of Petri nets by considering first-order, modal and pattern-based languages without labels on transitions or atomic propositions on markings. We consider several parameters to separate decidable problems from undecidable ones. Not only are we able to provide precise borders and a systematic analysis, but we also demonstrate the robustness of our proof techniques.

Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure

Tobias Heuer & Sebastian Schlag
We present an improved coarsening process for multilevel hypergraph partitioning that incorporates global information about the community structure. Community detection is performed via modularity maximization on a bipartite graph representation. The approach is made suitable for different classes of hypergraphs by defining weights for the graph edges that express structural properties of the hypergraph. We integrate our approach into a leading multilevel hypergraph partitioner with strong local search algorithms and perform extensive experiments on a...

On Partial Covering For Geometric Set Systems

Tanmay Inamdar & Kasturi Varadarajan
We study a generalization of the Set Cover problem called the Partial Set Cover in the context of geometric set systems. The input to this problem is a set system (X, R), where X is a set of elements and R is a collection of subsets of X, and an integer k <= |X|. Each set in R has a non-negative weight associated with it. The goal is to cover at least k elements of...

Edit Distance between Unrooted Trees in Cubic Time

Bartlomiej Dudek & Pawel Gawrychowski
Edit distance between trees is a natural generalization of the classical edit distance between strings, in which the allowed elementary operations are contraction, uncontraction and relabeling of an edge. Demaine et al. [ACM Trans. on Algorithms, 6(1), 2009] showed how to compute the edit distance between rooted trees on n nodes in O(n^3) time. However, generalizing their method to unrooted trees seems quite problematic, and the most efficient known solution remains to be the previous...

Towards Empathic Neurofeedback for Interactive Storytelling

Marc Cavazza, Gabor Aranyi, Fred Charles, Julie Porteous, Stephen Gilroy, Ilana Klovatch, Gilan Jackont, Eyal Soreq, Nimrod Jakob Keynan, Avihay Cohen, Gal Raz & Talma Hendler
Interactive Narrative is a form of digital entertainment based on AI techniques which support narrative generation and user interaction. Despite recent progress in the field, there is still a lack of unified models integrating narrative generation, user response and interaction. This paper addresses this issue by revisiting existing Interactive Narrative paradigms, granting explicit status to users' disposition towards story characters. We introduce a novel Brain-Computer Interface (BCI) design, which attempts to capture empathy for the...

Sharing Distributed Knowledge on the Web (Invited Talk)

Serge Abiteboul
To share information, we propose to see the Web as a knowledge base consisting of distributed logical facts and rules. Our objective is to help Web users finding information, as well as controlling their own, using automated reasoning over this knowledge base towards improving the quality of service and of data. For this, we introduce Webdamlog, a Datalog-style language with rule delegation. We mention the implementation of a system to support this language as well...

A Formalization of Forcing and the Unprovability of the Continuum Hypothesis

Jesse Michael Han & Floris Van Doorn
We describe a formalization of forcing using Boolean-valued models in the Lean 3 theorem prover, including the fundamental theorem of forcing and a deep embedding of first-order logic with a Boolean-valued soundness theorem. As an application of our framework, we specialize our construction to the Boolean algebra of regular opens of the Cantor space 2^{omega_2 x omega} and formally verify the failure of the continuum hypothesis in the resulting model.

A Concurrent Logical Relation

Lars Birkedal, Filip Sieczkowski & Jacob Thamsborg
We present a logical relation for showing the correctness of program transformations based on a new type-and-effect system for a concurrent extension of an ML-like language with higher-order functions, higher-order store and dynamic memory allocation. We show how to use our model to verify a number of interesting program transformations that rely on effect annotations. In particular, we prove a Parallelization Theorem, which expresses when it is sound to run two expressions in parallel instead...

Improved Algorithm for Dynamic b-Matching

Sayan Bhattacharya, Manoj Gupta & Divyarthi Mohan
Recently there has been extensive work on maintaining (approximate) maximum matchings in dynamic graphs. We consider a generalisation of this problem known as the maximum b-matching: Every node v has a positive integral capacity b_v, and the goal is to maintain an (approximate) maximum-cardinality subset of edges that contains at most b_v edges incident on every node v. The maximum matching problem is a special case of this problem where b_v = 1 for every...

Why Classificatory Information of Geographic Regions Is Quantum Information (Vision Paper)

Thomas Bittner
This paper gives an information - theoretic argument in support of the claim that there is geographic quantum information. Quantum information is information in the sense of Shannon's information theory, that, in addition, satisfies two characteristic postulates. The paper aims to show that if the density of information (bits per unit of space) that is possible for classificatory geographic qualities is limited, then it follows that the two characteristic postulates of quantum information are satisfied...

Visualization of CHR through Source-to-Source Transformation

Slim Abdennadher & Nada Sharaf
In this paper, we propose an extension of Constraint Handling Rules (CHR) with different visualization features. One feature is to visualize the execution of rules applied on a list of constraints. The second feature is to represent some of the CHR constraints as objects and visualize the effect of CHR rules on them. To avoid changing the compiler, our implementation is based on source-to-source transformation.

The Alternating Stock Size Problem and the Gasoline Puzzle

Alantha Newman, Heiko Röglin & Johanna Seif

Random Resolution Refutations

Pavel Pudlák & Neil Thapen
We study the random resolution refutation system definedin [Buss et al. 2014]. This attempts to capture the notion of a resolution refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the other hand, if P does not equal NP, then random resolution cannot be polynomially simulated by any proof system in which correctness of proofs is...

Randomization in Parameterized Complexity (Dagstuhl Seminar 17041)

Marek Cygan, Fedor V. Fomin, Danny Hermelin & Magnus Wahlström
Dagstuhl Seminar 17041 "Randomization in Parameterized Complexity" took place from January 22nd to January 27th 2017 with the objective to bridge the gap between randomization and parameterized complexity theory. This report documents the talks held during the seminar as well as the open questions arised in the discussion sessions.

Knowledge Spaces and the Completeness of Learning Strategies

Stefano Berardi & Ugo De'Liguoro
We propose a theory of learning aimed to formalize some ideas underlying Coquand's game semantics and Krivine's realizability of classical logic. We introduce a notion of knowledge state together with a new topology, capturing finite positive and negative information that guides a learning strategy. We use a leading example to illustrate how non-constructive proofs lead to continuous and effective learning strategies over knowledge spaces, and prove that our learning semantics is sound and complete w.r.t....

Extending the Path Analysis Technique to Obtain a Soft WCET

Paul Keim, Amanda Noyes, Andrew Ferguson, Joshua Neal & Christopher Healy
This paper discusses an efficient approach to statically compute a WCET that is "soft" rather than "hard". The goal of most timing analysis is to determine a guaranteed WCET; however this execution time may be far above the actual distribution of observed execution times. A WCET estimate that bounds the execution time 99% of the time may be more useful for a designer in a soft real-time environment. This paper discusses an approach to measure...

Registration Year

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

Resource Types

  • Text
  • Software