Emmanouil Antonios Platanios, Adam Pauls, Subhro Roy, Yuchen Zhang, Alexander Kyte, Alan Guo, Sam Thomson, Jayant Krishnamurthy, Jason Wolfe, Jacob Andreas, Dan Klein. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

We describe an approach to task-oriented dialogue in which dialogue state is represented as a dataflow graph. A dialogue agent maps each user utterance to a program that extends this graph. Programs include metacomputation operators for reference and revision that reuse dataflow fragments from previous turns. Our graph-based state enables the expression and manipulation of complex user intents, and explicit metacomputation makes these intents easier for learned models to predict. We introduce a new dataset, SMCalFlow, featuring complex dialogues about events, weather, places, and people. Experiments show that dataflow graphs and metacomputation substantially improve representability and predictability in these natural dialogues. Additional experiments on the MultiWOZ dataset show that our dataflow representation enables an otherwise off-the-shelf sequence-to-sequence model to match the best existing task-specific state tracking model. The SMCalFlow dataset, code for replicating experiments, and a public leaderboard are available at https://www.microsoft.com/en-us/research/project/dataflow-based-dialogue-semantic-machines .

We present a general framework for constructing high-rate error correcting codes that are locally correctable (and hence locally decodable if linear) with a sublinear number of queries, based on lifting codes with respect to functions on the coordinates. Our approach generalizes the lifting of affine-invariant codes (of Guo, Kopparty, and Sudan) and its generalization automorphic lifting (alluded to in the work of Ben-Sasson et al., but distinct from their degree lifting), which lifts algebraic geometry codes with respect to a group of automorphisms of the code. Our notion of lifting is a natural alternative to the degree lifting of Ben-Sasson et al. and it carries two advantages. First, it overcomes the rate barrier inherent in degree lifting. Second, it requires no special properties (e.g. linearity and invariance) of the base code, and requires a very little structure on the set of functions on the coordinates of the code. As an application, we construct new explicit families of locally correctable codes by lifting algebraic geometry codes. Like the multiplicity codes of Kopparty, Saraf, Yekhanin, and the affine-lifted codes of Guo, Kopparty, and Sudan, our codes of block length N can achieve N∈query complexity and 1 - α rate for any given ∈, α > 0, while correcting a constant fraction of errors, in contrast to the Reed-Muller codes and the degree-lifted AG codes of Ben-Sasson et al., which face a rate barrier of ∈O(1/∈). However, like the degree-lifted AG codes, our codes are over an alphabet significantly smaller than that obtained by Reed-Muller codes, affine-lifted codes, and multiplicity codes.

Lifted Reed-Solomon codes are a natural affine-invariant family of error-correcting codes, which generalize Reed-Muller codes. They were known to have efficient local-testing and local-decoding algorithms (comparable with the known algorithms for Reed-Muller codes), but with significantly better rate. We give efficient algorithms for list decoding and local list decoding of lifted codes. Our algorithms are based on a new technical lemma, which says that the codewords of lifted codes are low degree polynomials when viewed as univariate polynomials over a big field (even though they may be very high degree when viewed as multivariate polynomials over a small field).

A local tester for a code probabilistically views a small set of coordinates of a given word and based on this local view accepts code words with probability one while rejecting words far from the code with constant probability. A local tester for a code is said to be "robust" if the local views of the tester are far from acceptable views when the word being tested is far from the code. Robust testability of codes play a fundamental role in constructions of probabilistically checkable proofs where robustness is a critical element in composition. In this work we consider a broad class of codes, called lifted codes, that include codes formed by low-degree polynomials, and show that an almost natural test, extending a low-degree test proposed by Raz and Safra (STOC 1997), is robust. Our result is clean and general -- the robustness of the test depends only on the distance of the code being lifted, and is positive whenever the distance is positive. We use our result to get the first robust low-degree test that works when the degree of the polynomial being tested is more than half the field size. Our results also show that the high-rate codes of Guo et al. (ITCS 2013) are robustly locally testable with sub linear query complexity. Guo et al. Also show several other interesting classes of locally testable codes that can be derived from lifting and our result shows all such codes have robust testers, at the cost of a quadratic blow up in the query complexity of the tester. Of technical interest is an intriguing relationship between tensor product codes and lifted codes that we explore and exploit.

We investigate the minimum distance of the error correcting code formed by the homomorphisms between two finite groups $G$ and $H$. We prove some general structural results on how the distance behaves with respect to natural group operations, such as passing to subgroups and quotients, and taking products. Our main result is a general formula for the distance when $G$ is solvable or $H$ is nilpotent, in terms of the normal subgroup structure of $G$ as well as the prime divisors of $|G|$ and $|H|$. In particular, we show that in the above case, the distance is independent of the subgroup structure of $H$. We complement this by showing that, in general, the distance depends on the subgroup structure $G$.

In this work we explore error-correcting codes derived from the "lifting" of "affine-invariant" codes. Affine-invariant codes are simply linear codes whose coordinates are a vector space over a field and which are invariant under affine-transformations of the coordinate space. Lifting takes codes defined over a vector space of small dimension and lifts them to higher dimensions by requiring their restriction to every subspace of the original dimension to be a codeword of the code being lifted. While the operation is of interest on its own, this work focusses on new ranges of parameters that can be obtained by such codes, in the context of local correction and testing. In particular we present four interesting ranges of parameters that can be achieved by such lifts, all of which are new in the context of affine-invariance and some may be new even in general. The main highlight is a construction of high-rate codes with sublinear time decoding. The only prior construction of such codes is due to Kopparty, Saraf and Yekhanin [33]. All our codes are extremely simple, being just lifts of various parity check codes (codes with one symbol of redundancy), and in the final case, the lift of a Reed-Solomon code.