7,826 Works

AI for the Social Good (Dagstuhl Seminar 19082)

Claudia Clopath, Ruben De Winne, Mohammad Emtiyaz Khan & Tom Schaul
Artificial intelligence (AI) and machine learning (ML) have made impressive progress in the last few years. Long-standing challenges like Go have fallen and the technology has entered daily use via the vision, speech or translation capabilities in billions of smartphones. The pace of research progress shows no signs of slowing down, and demand for talent is unprecedented. AI for Social Good in general is trying to ensure that the social good does not become an...

Beyond-Planar Graphs: Combinatorics, Models and Algorithms (Dagstuhl Seaminar 19092)

Seok-Hee Hong, Michael Kaufmann, János Pach & Csaba D. Tóth
This report documents the program and the outcomes of Dagstuhl Seminar 19092 "Beyond-Planar Graphs: Combinatorics, Models and Algorithms" which brought together 36 researchers in the areas of graph theory, combinatorics, computational geometry, and graph drawing. This seminar continued the work initiated in Dagstuhl Seminar 16452 "Beyond-Planar Graphs: Algorithmics and Combinatorics" and focused on the exploration of structural properties and the development of algorithms for so-called beyond-planar graphs, i.e., non-planar graphs that admit a drawing with...

Specification Formalisms for Modern Cyber-Physical Systems (Dagstuhl Seminar 19071)

Jyotirmoy V. Deshmukh, Oded Maler & Dejan Nickovic
This report documents the program and the outcomes of Dagstuhl Seminar 19071 "Specification Formalisms for Modern Cyber-Physical Systems." Specifications play a major role in evaluating behaviors of modern cyber-physical systems (CPS). There is currently no specification language that allows joint description of safety, performance, security, privacy, and reliability aspects of CPS applications. The Dagstuhl seminar brought together researchers and practitioners from formal methods, control theory, machine learning and robotics to discuss the state-of-the-art and open...

The Role of Non-monotonic Reasoning in Future Development of Artificial Intelligence (Dagstuhl Perspectives Workshop 19072)

Anthony Hunter, Gabriele Kern-Isberner, Thomas Meyer & Renata Wassermann
This report documents the program and the outcomes of Dagstuhl Perspectives Workshop 19072 "The Role of Non-monotonic Reasoning in Future Development of Artificial Intelligence". The workshop brought together researchers both from core topics and peripheral areas of non-monotonic reasoning (NMR), but also attracted researchers from other scientific domains in which recent developments have shown an increased relevance of NMR topics. The overall goal of this workshop was to reshape NMR as a core methodology for...

Verification and Synthesis of Human-Robot Interaction (Dagstuhl Seminar 19081)

Rachid Alami, Kerstin I. Eder, Guy Hoffman & Hadas Kress-Gazit
This report documents the program and the outcomes of Dagstuhl Seminar 19081 "Verification and Synthesis of Human-Robot Interaction". This seminar brought together researchers from two distinct communities - Formal Methods for Robotics, and Human-Robot Interaction - to discuss the path towards creating safe and verifiable autonomous systems that are compatible with humans.

Visual Analytics of Multilayer Networks Across Disciplines (Dagstuhl Seminar 19061)

Mikko Kivelä, Fintan McGee, Guy Melançon, Nathalie Henry Riche & Tatiana Von Landesberger
This report documents the program and the outcomes of Dagstuhl Seminar 19061 "Visual Analytics of Multilayer Networks Across Disciplines". Networks, used to understand systems, often contain multiple types of nodes and/or edges. They are often flattened to a single network, even though real-world systems are more accurately modelled as a set of interacting networks, or layers, with different node and edge types. These are so-called multilayer networks. These networks are studied by researchers both in...

Bringing CP, SAT and SMT together: Next Challenges in Constraint Solving (Dagstuhl Seminar 19062)

Sébastien Bardin, Nikolaj Bjørner & Cristian Cadar
This report documents the program and the outcomes of Dagstuhl Seminar 19062 "Bringing CP, SAT and SMT together: Next Challenges in Constraint Solving", whose main goals were to bring together leading researchers in the different subfields of automated reasoning and constraint solving, foster greater communication between these communities and exchange ideas about new research directions. Constraint solving is at the heart of several key technologies, including program analysis, testing, formal methods, compilers, security analysis, optimization,...

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

Lijie Chen, Dylan M. McKay, Cody D. Murray & R. Ryan Williams
A frontier open problem in circuit complexity is to prove P^{NP} is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P_{/poly}. Previously, for several classes containing P^{NP}, including NP^{NP}, ZPP^{NP}, and S_2 P, such lower bounds have been proved via Karp-Lipton-style Theorems: to prove C is not in SIZE[n^k] for all k, we show that C subset P_{/poly} implies a "collapse" D = C for some...

Imperfect Gaps in Gap-ETH and PCPs

Mitali Bafna & Nikhil Vyas
We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a way to transform a PCP with imperfect completeness to one with perfect completeness, when the initial gap is a constant. We show that PCP_{c,s}[r,q] subseteq PCP_{1,s'}[r+O(1),q+O(r)] for c-s=Omega(1) which in turn implies that one can convert imperfect completeness to perfect in linear-sized PCPs for NP with a O(log n) additive loss in the query complexity q. We show our...

A Fine-Grained Analogue of Schaefer's Theorem in P: Dichotomy of Exists^k-Forall-Quantified First-Order Graph Properties

Karl Bringmann, Nick Fischer & Marvin Künnemann
An important class of problems in logics and database theory is given by fixing a first-order property psi over a relational structure, and considering the model-checking problem for psi. Recently, Gao, Impagliazzo, Kolokolova, and Williams (SODA 2017) identified this class as fundamental for the theory of fine-grained complexity in P, by showing that the (Sparse) Orthogonal Vectors problem is complete for this class under fine-grained reductions. This raises the question whether fine-grained complexity can yield...

Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions

Xin Li
The recent line of study on randomness extractors has been a great success, resulting in exciting new techniques, new connections, and breakthroughs to long standing open problems in several seemingly different topics. These include seeded non-malleable extractors, privacy amplification protocols with an active adversary, independent source extractors (and explicit Ramsey graphs), and non-malleable codes in the split state model. Previously, the best constructions are given in [Xin Li, 2017]: seeded non-malleable extractors with seed length...

Hardness Magnification near State-Of-The-Art Lower Bounds

Igor Carboni Oliveira, Ján Pich & Rahul Santhanam
This work continues the development of hardness magnification. The latter proposes a new strategy for showing strong complexity lower bounds by reducing them to a refined analysis of weaker models, where combinatorial techniques might be successful. We consider gap versions of the meta-computational problems MKtP and MCSP, where one needs to distinguish instances (strings or truth-tables) of complexity <= s_1(N) from instances of complexity >= s_2(N), and N = 2^n denotes the input length. In...

Optimal Separation and Strong Direct Sum for Randomized Query Complexity

Eric Blais & Joshua Brody
We establish two results regarding the query complexity of bounded-error randomized algorithms. Bounded-error separation theorem. There exists a total function f : {0,1}^n -> {0,1} whose epsilon-error randomized query complexity satisfies overline{R}_epsilon(f) = Omega(R(f) * log 1/epsilon). Strong direct sum theorem. For every function f and every k >= 2, the randomized query complexity of computing k instances of f simultaneously satisfies overline{R}_epsilon(f^k) = Theta(k * overline{R}_{epsilon/k}(f)). As a consequence of our two main results,...

Barriers for Fast Matrix Multiplication from Irreversibility

Matthias Christandl, Péter Vrana & Jeroen Zuiddam
Determining the asymptotic algebraic complexity of matrix multiplication, succinctly represented by the matrix multiplication exponent omega, is a central problem in algebraic complexity theory. The best upper bounds on omega, leading to the state-of-the-art omega <= 2.37.., have been obtained via the laser method of Strassen and its generalization by Coppersmith and Winograd. Recent barrier results show limitations for these and related approaches to improve the upper bound on omega. We introduce a new and...

Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision

Matthew Coudron & William Slofstra
We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is NP-complete to decide whether the classical value of a non-local game is 1 or 1- epsilon, promised that one of the two is the case. Furthermore, as long as epsilon is small enough, this result does not depend on the gap epsilon. In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that...

Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs

Albert Atserias & Tuomas Hakoniemi
We show that if a system of degree-k polynomial constraints on n Boolean variables has a Sums-of-Squares (SOS) proof of unsatisfiability with at most s many monomials, then it also has one whose degree is of the order of the square root of n log s plus k. A similar statement holds for the more general Positivstellensatz (PS) proofs. This establishes size-degree trade-offs for SOS and PS that match their analogues for weaker proof systems...

Time-Space Lower Bounds for Two-Pass Learning

Sumegha Garg, Ran Raz & Avishay Tal
A line of recent works showed that for a large class of learning problems, any learning algorithm requires either super-linear memory size or a super-polynomial number of samples [Raz, 2016; Kol et al., 2017; Raz, 2017; Moshkovitz and Moshkovitz, 2018; Beame et al., 2018; Garg et al., 2018]. For example, any algorithm for learning parities of size n requires either a memory of size Omega(n^{2}) or an exponential number of samples [Raz, 2016]. All these...

Parity Helps to Compute Majority

Igor Carboni Oliveira, Rahul Santhanam & Srikanth Srinivasan
We study the complexity of computing symmetric and threshold functions by constant-depth circuits with Parity gates, also known as AC^0[oplus] circuits. Razborov [Alexander A. Razborov, 1987] and Smolensky [Roman Smolensky, 1987; Roman Smolensky, 1993] showed that Majority requires depth-d AC^0[oplus] circuits of size 2^{Omega(n^{1/2(d-1)})}. By using a divide-and-conquer approach, it is easy to show that Majority can be computed with depth-d AC^0[oplus] circuits of size 2^{O~(n^{1/(d-1)})}. This gap between upper and lower bounds has stood...

Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion

Matthew Coudron & Aram W. Harrow
In this work we consider the role of entanglement assistance in quantum communication protocols, focusing, in particular, on whether the type of shared entangled state can affect the quantum communication complexity of a function. This question is interesting because in some other settings in quantum information, such as non-local games, or tasks that involve quantum communication between players and referee, or simulating bipartite unitaries or communication channels, maximally entangled states are known to be less...

Average-Case Quantum Advantage with Shallow Circuits

François Le Gall
Recently Bravyi, Gosset and König (Science 2018) proved an unconditional separation between the computational powers of small-depth quantum and classical circuits for a relation. In this paper we show a similar separation in the average-case setting that gives stronger evidence of the superiority of small-depth quantum computation: we construct a computational task that can be solved on all inputs by a quantum circuit of constant depth with bounded-fanin gates (a "shallow" quantum circuit) and show...

Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity

Lijie Chen & R. Ryan Williams
We considerably sharpen the known connections between circuit-analysis algorithms and circuit lower bounds, show intriguing equivalences between the analysis of weak circuits and (apparently difficult) circuits, and provide strong new lower bounds for approximately computing Boolean functions with depth-two neural networks and related models. - We develop approaches to proving THR o THR lower bounds (a notorious open problem), by connecting algorithmic analysis of THR o THR to the provably weaker circuit classes THR o...

Fourier and Circulant Matrices Are Not Rigid

Zeev Dvir & Allen Liu
The concept of matrix rigidity was first introduced by Valiant in [Friedman, 1993]. Roughly speaking, a matrix is rigid if its rank cannot be reduced significantly by changing a small number of entries. There has been extensive interest in rigid matrices as Valiant showed in [Friedman, 1993] that rigidity can be used to prove arithmetic circuit lower bounds. In a surprising result, Alman and Williams showed that the (real valued) Hadamard matrix, which was conjectured...

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

Susanna F. De Rezende, Jakob Nordström, Or Meir & Robert Robere
We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatz refutation of the pebbling formula over G in size t+1 and degree s (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree...

Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Dean Doron, Pooya Hatami & William M. Hoza
We give an explicit pseudorandom generator (PRG) for read-once AC^0, i.e., constant-depth read-once formulas over the basis {wedge, vee, neg} with unbounded fan-in. The seed length of our PRG is O~(log(n/epsilon)). Previously, PRGs with near-optimal seed length were known only for the depth-2 case [Gopalan et al., 2012]. For a constant depth d > 2, the best prior PRG is a recent construction by Forbes and Kelley with seed length O~(log^2 n + log n...

Counting Basic-Irreducible Factors Mod p^k in Deterministic Poly-Time and p-Adic Applications

Ashish Dwivedi, Rajat Mittal & Nitin Saxena
Finding an irreducible factor, of a polynomial f(x) modulo a prime p, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that counts the number of irreducible factors of f mod p. We can ask the same question modulo prime-powers p^k. The irreducible factors of f mod p^k blow up exponentially in number; making it hard to describe them. Can we count those irreducible factors mod p^k that...

Registration Year

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

Resource Types

  • Text
  • Software