In this task, you are given the abstract of a research paper. Your task is to generate a summary of this abstract. Your summary should not be very short, but it's better if it's not more than 30 words.

Input: Consider Input: Synthesizing user-intended programs from a small number of input-output exam-
 ples is a challenging problem with several important applications like spreadsheet
 manipulation, data wrangling and code refactoring. Existing synthesis systems
 either completely rely on deductive logic techniques that are extensively hand-
 engineered or on purely statistical models that need massive amounts of data, and in
 general fail to provide real-time synthesis on challenging benchmarks. In this work,
 we propose Neural Guided Deductive Search (NGDS), a hybrid synthesis technique
 that combines the best of both symbolic logic techniques and statistical models.
 Thus, it produces programs that satisfy the provided specifications by construction
 and generalize well on unseen examples, similar to data-driven systems. Our
 technique effectively utilizes the deductive search framework to reduce the learning
 problem of the neural component to a simple supervised learning setup. Further,
 this allows us to both train on sparingly available real-world data and still leverage
 powerful recurrent neural network encoders. We demonstrate the effectiveness
 of our method by evaluating on real-world customer scenarios by synthesizing
 accurate programs with up to 12× speed-up compared to state-of-the-art systems.

Output: We integrate symbolic (deductive) and statistical (neural-based) methods to enable real-time program synthesis with almost perfect generalization from 1 input-output example.


Input: Consider Input: Sequential decision problems for real-world applications often need to be solved in real-time, requiring algorithms to perform well with a restricted computational budget. Width-based lookaheads have shown state-of-the-art performance in classical planning problems as well as over the Atari games with tight budgets. In this work we investigate width-based lookaheads over Stochastic Shortest paths (SSP). We analyse why width-based algorithms perform poorly over SSP problems, and overcome these pitfalls proposing a method to estimate costs-to-go. We formalize width-based lookaheads as an instance of the rollout algorithm, give a definition of width for SSP problems and explain its sample complexity. Our experimental results over a variety of SSP benchmarks show the algorithm to outperform other state-of-the-art rollout algorithms such as UCT and RTDP.

Output: We propose a new Monte Carlo Tree Search / rollout algorithm that relies on width-based search to construct a lookahead.


Input: Consider Input: Invariant and equivariant networks have been successfully used for learning images, sets, point clouds, and graphs. A basic challenge in developing such networks is finding the maximal collection of invariant and equivariant \emph{linear} layers. Although this question is answered for the first three examples (for popular transformations, at-least), a full characterization of invariant and equivariant linear layers for graphs is not known. 

 In this paper we provide a characterization of all permutation invariant and equivariant linear layers for (hyper-)graph data, and show that their dimension, in case of edge-value graph data, is $2$ and $15$, respectively. More generally, for graph data defined on $k$-tuples of nodes, the dimension is the $k$-th and $2k$-th Bell numbers. Orthogonal bases for the layers are computed, including generalization to multi-graph data. The constant number of basis elements and their characteristics allow successfully applying the networks to different size graphs. From the theoretical point of view, our results generalize and unify recent advancement in equivariant deep learning. In particular, we show that our model is capable of approximating any message passing neural network.

 Applying these new linear layers in a simple deep neural network framework is shown to achieve comparable results to state-of-the-art and to have better expressivity than previous invariant and equivariant bases.



Output: The paper provides a full characterization of permutation invariant and equivariant linear layers for graph data.