Ran Zmigrod

VLDB 2026 Research / reviewers in the wild / expert

dblp:222/4309 · DBLP profile ↗

← Back

11ranked-venue papers

7as first author

6since 2021 · last 2023

—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Artificial intelligence and machine learning · 10 · 6 first-author · 6 since 2021Theory of computation · 1 · 1 first-author

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Artificial intelligence 5 papers		Information extraction and text analysis · 64% Trustworthy machine learning · 26% Deep learning architectures and training · 8%
Theoretical computer science 4 papers		Graph algorithms and graph theory · 50% Automata and formal languages · 38% Distributed computing theory · 11%

Topics — the 14 heaviest of 14, each with the papers that count most for it

Topic	Weight	Papers	Last	Evidence papers
Natural language and speech › Information extraction and text analysis syntactic parsing	1.6	3	2023	Efficient Semiring-Weighted Earley Parsing · ACL (1) 2023 Efficient Sampling of Dependency Structure · EMNLP (1) 2021 Please Mind the Root: Decoding Arborescences for Dependency Parsing · EMNLP (1) 2020
Graph algorithms and graph theory graph algorithms	1.4	3	2021	Efficient Sampling of Dependency Structure · EMNLP (1) 2021 On Finding the K-best Non-projective Dependency Trees · ACL/IJCNLP (1) 2021 Please Mind the Root: Decoding Arborescences for Dependency Parsing · EMNLP (1) 2020
Natural language and speech › Information extraction and text analysis › syntactic parsing dependency parsing	0.9	2	2021	Efficient Sampling of Dependency Structure · EMNLP (1) 2021 Please Mind the Root: Decoding Arborescences for Dependency Parsing · EMNLP (1) 2020
Automata and formal languages › parsing context-free grammar parsing	0.7	1	2023	Efficient Semiring-Weighted Earley Parsing · ACL (1) 2023
Automata and formal languages parsing algorithms	0.7	1	2023	Efficient Semiring-Weighted Earley Parsing · ACL (1) 2023
Graph algorithms and graph theory › spanning tree random spanning tree	0.5	1	2021	Efficient Sampling of Dependency Structure · EMNLP (1) 2021
Machine learning › Trustworthy machine learning information-theoretic probing	0.4	1	2020	Information-Theoretic Probing for Linguistic Structure · ACL 2020
Natural language and speech › Information extraction and text analysis linguistic probing	0.4	1	2020	Information-Theoretic Probing for Linguistic Structure · ACL 2020
Distributed computing theory › distributed graph algorithms spanning tree construction	0.4	1	2020	Please Mind the Root: Decoding Arborescences for Dependency Parsing · EMNLP (1) 2020
Machine learning › Trustworthy machine learning counterfactual data augmentation	0.4	1	2019	Counterfactual Data Augmentation for Mitigating Gender Stereotypes in Languages with Rich Morphology · ACL (1) 2019
Machine learning › Deep learning architectures and training data augmentation	0.4	1	2019	Counterfactual Data Augmentation for Mitigating Gender Stereotypes in Languages with Rich Morphology · ACL (1) 2019
Machine learning › Trustworthy machine learning fairness	0.4	1	2019	Counterfactual Data Augmentation for Mitigating Gender Stereotypes in Languages with Rich Morphology · ACL (1) 2019
Automata and formal languages parsing	0.1	1	2021	On Finding the K-best Non-projective Dependency Trees · ACL/IJCNLP (1) 2021
Natural language and speech › Machine translation morphologically rich languages	0.1	1	2019	Counterfactual Data Augmentation for Mitigating Gender Stereotypes in Languages with Rich Morphology · ACL (1) 2019

Methods — techniques the papers use, named apart from their topics

semiring weighting · 1.3deduction system · 1.3wilson's algorithm · 1.0colbourn's algorithm · 1.0gabow-tarjan algorithm · 0.9arborescence decoding · 0.9mutual information estimation · 0.4counterfactual data augmentation · 0.4

Year	Publication	Venue	Position
2023	Efficient Semiring-Weighted Earley Parsing abstract This paper provides a reference description, in the form of a deduction system, of Earley's (1970) context-free parsing algorithm with various speed-ups.Our presentation includes a known worst-case runtime improvement from Earley's O N 3 \|G\|\|R\| , which is unworkable for the large grammars that arise in natural language processing, to O N 3 \|G\| , which matches the runtime of CKY on a binarized version of the grammar G.Here N is the length of the sentence, \|R\| is the number of productions in G, and \|G\| is the total length of those productions.We also provide a version that achieves runtime of O N 3 \|M\| with \|M\| ≤ \|G\| when the grammar is represented compactly as a single finite-state automaton M (this is partly novel).We carefully treat the generalization to semiring-weighted deduction, preprocessing the grammar like Stolcke (1995) to eliminate deduction cycles, and further generalize Stolcke's method to compute the weights of sentence prefixes.We also provide implementation details for efficient execution, ensuring that on a preprocessed grammar, the semiring-weighted versions of our methods have the same asymptotic runtime and space requirements as the unweighted methods, including sub-cubic runtime on some grammars.https://github.com/rycolab/ earleys Andreas Opedal, Ran Zmigrod, Tim Vieira, Ryan Cotterell, Jason Eisner	ACL (1)	2
2022	UniMorph 4.0: Universal Morphology abstract The Universal Morphology (UniMorph) project is a collaborative effort providing broad-coverage instantiated normalized morphological inflection tables for hundreds of diverse world languages. The project comprises two major thrusts: a language-independent feature schema for rich morphological annotation, and a type-level resource of annotated data in diverse languages realizing that schema. This paper presents the expansions and improvements on several fronts that were made in the last couple of years (since McCarthy et al. (2020)). Collaborative efforts by numerous linguists have added 66 new languages, including 24 endangered languages. We have implemented several improvements to the extraction pipeline to tackle some issues, e.g., missing gender and macrons information. We have amended the schema to use a hierarchical structure that is needed for morphological phenomena like multiple-argument agreement and case stacking, while adding some missing morphological features to make the schema more inclusive. In light of the last UniMorph release, we also augmented the database with morpheme segmentation for 16 languages. Lastly, this new release makes a push towards inclusion of derivational morphology in UniMorph by enriching the data and annotation schema with instances representing derivational processes from MorphyNet. Khuyagbaatar Batsuren, Omer Goldman, Salam Khalifa, Nizar Habash, Witold Kieras, Gábor Bella, Brian Leonard, Garrett Nicolai, Kyle Gorman, Yustinus Ghanggo Ate, Maria Ryskina, Sabrina J. Mielke, Elena Budianskaya, Charbel El-Khaissi, Tiago Pimentel, Michael Gasser, William Lane 0002, Mohit Raj, Matt Coler, Jaime Rafael Montoya Samame, Delio Siticonatzi Camaiteri, Esaú Zumaeta Rojas, Didier López Francis, Arturo Oncevay, Juan López Bautista, Gema Celeste Silva Villegas, Lucas Torroba Hennigen, Adam Ek, David Guriel, Peter Dirix, Jean-Philippe Bernardy, Andrey Scherbakov, Aziyana Bayyr-ool, Antonios Anastasopoulos, Roberto Zariquiey, Karina Sheifer, Sofya Ganieva, Hilaria Cruz, Ritván Karahóga, Stella Markantonatou, George Pavlidis, Matvey Plugaryov, Elena Klyachko, Ali Salehi, Candy Angulo, Jatayu Baxi, Andrew Krizhanovsky, Natalia Krizhanovskaya, Elizabeth Salesky, Clara Vania, Sardana Ivanova, Jennifer C. White, Rowan Hall Maudslay, Josef Valvoda, Ran Zmigrod, Paula Czarnowska, Irene Nikkarinen, Aelita Salchak, Brijesh Bhatt, Christopher Straughn, Zoey Liu, Jonathan Washington, Yuval Pinter, Duygu Ataman, Marcin Wolinski, Totok Suhardijanto, Anna Yablonskaya, Niklas Stoehr, Hossep Dolatian, Zahroh Nuriah, Shyam Ratan, Francis M. Tyers, Edoardo Maria Ponti, Grant Aiton, Aryaman Arora, Richard J. Hatcher, Ritesh Kumar 0002, Jeremiah Young, Daria Rodionova, Anastasia Yemelina, Taras Andrushko, Igor Marchenko, Polina Mashkovtseva, Alexandra Serova, Emily Tucker Prud'hommeaux, Maria Nepomniashchaya, Fausto Giunchiglia, Eleanor Chodroff, Mans Hulden, Miikka Silfverberg, Arya McCarthy, David Yarowsky, Ryan Cotterell, Reut Tsarfaty, Ekaterina Vylomova	LREC	55
2022	Exact Paired-Permutation Testing for Structured Test Statistics abstract Significance testing-especially the pairedpermutation test-has played a vital role in developing NLP systems to provide confidence that the difference in performance between two systems (i.e., the test statistic) is not due to luck.However, practitioners rely on Monte Carlo approximation to perform this test due to a lack of a suitable exact algorithm.In this paper, we provide an efficient exact algorithm for the paired-permutation test for a family of structured test statistics.Our algorithm runs in O(GN (log GN )(log N )) time where N is the dataset size and G is the range of the test statistic.We found that our exact algorithm was 10x faster than the Monte Carlo approximation with 20000 samples on a common dataset. Ran Zmigrod, Tim Vieira, Ryan Cotterell	NAACL-HLT	1
2021	On Finding the K-best Non-projective Dependency Trees abstract Ran Zmigrod, Tim Vieira, Ryan Cotterell. 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. Ran Zmigrod, Tim Vieira, Ryan Cotterell	ACL/IJCNLP (1)	1
2021	Efficient Sampling of Dependency Structure abstract Probabilistic distributions over spanning trees in directed graphs are a fundamental model of dependency structure in natural language processing, syntactic dependency trees.In NLP, dependency trees often have an additional root constraint: only one edge may emanate from the root.However, no sampling algorithm has been presented in the literature to account for this additional constraint.In this paper, we adapt two spanning tree sampling algorithms to sample dependency trees from a graph subject to the root constraint.Wilson (1996)'s sampling algorithm has a running time of O(H) where H is the mean hitting time of the graph.Colbourn et al. (1996)'s sampling algorithm has a running time of O(N 3 ), which is often greater than the mean hitting time of a directed graph.Additionally, we build upon Colbourn's algorithm and present a novel extension that can sample K trees without replacement in O(KN 3 + K 2 N ) time.To the best of our knowledge, no algorithm has been given for sampling spanning trees without replacement from a directed graph. 1 Ran Zmigrod, Tim Vieira, Ryan Cotterell	EMNLP (1)	1
2021	Efficient Computation of Expectations under Spanning Tree Distributions abstract Abstract We give a general framework for inference in spanning tree models. We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms. These algorithms are easy to implement with or without automatic differentiation software. We motivate the development of our framework with several cautionary tales of previous research, which has developed numerous inefficient algorithms for computing expectations and their gradients. We demonstrate how our framework efficiently computes several quantities with known algorithms, including the expected attachment score, entropy, and generalized expectation criteria. As a bonus, we give algorithms for quantities that are missing in the literature, including the KL divergence. In all cases, our approach matches the efficiency of existing algorithms and, in several cases, reduces the runtime complexity by a factor of the sentence length. We validate the implementation of our framework through runtime experiments. We find our algorithms are up to 15 and 9 times faster than previous algorithms for computing the Shannon entropy and the gradient of the generalized expectation objective, respectively. Ran Zmigrod, Tim Vieira, Ryan Cotterell	Trans. Assoc. Comput. Linguistics	1
2020	Information-Theoretic Probing for Linguistic Structure abstract The success of neural networks on a diverse set of NLP tasks has led researchers to question how much these networks actually "know" about natural language.Probes are a natural way of assessing this.When probing, a researcher chooses a linguistic task and trains a supervised model to predict annotations in that linguistic task from the network's learned representations.If the probe does well, the researcher may conclude that the representations encode knowledge related to the task.A commonly held belief is that using simpler models as probes is better; the logic is that simpler models will identify linguistic structure, but not learn the task itself.We propose an information-theoretic operationalization of probing as estimating mutual information that contradicts this received wisdom: one should always select the highest performing probe one can, even if it is more complex, since it will result in a tighter estimate, and thus reveal more of the linguistic information inherent in the representation.The experimental portion of our paper focuses on empirically estimating the mutual information between a linguistic property and BERT, comparing these estimates to several baselines.We evaluate on a set of ten typologically diverse languages often underrepresented in NLP research-plus Englishtotalling eleven languages.Our implementation is available in https://github.com/ rycolab/info-theoretic-probing. Tiago Pimentel, Josef Valvoda, Rowan Hall Maudslay, Ran Zmigrod, Adina Williams, Ryan Cotterell	ACL	4
2020	Please Mind the Root: Decoding Arborescences for Dependency Parsing abstract The connection between dependency trees and spanning trees is exploited by the NLP community to train and to decode graph-based dependency parsers.However, the NLP literature has missed an important difference between the two structures: only one edge may emanate from the root in a dependency tree.We analyzed the output of state-of-the-art parsers on many languages from the Universal Dependency Treebank: although these parsers are often able to learn that trees which violate the constraint should be assigned lower probabilities, their ability to do so unsurprisingly degrades as the size of the training set decreases.In fact, the worst constraint-violation rate we observe is 24%.Prior work has proposed an inefficient algorithm to enforce the constraint, which adds a factor of n to the decoding runtime.We adapt an algorithm due to Gabow and Tarjan (1984) to dependency parsing, which satisfies the constraint without compromising the original runtime. 1 Ran Zmigrod, Tim Vieira, Ryan Cotterell	EMNLP (1)	1
2020	A Relaxation of Üresin and Dubois' Asynchronous Fixed-Point Theory in Agda abstract Abstract Üresin and Dubois’ paper “Parallel Asynchronous Algorithms for Discrete Data” shows how a class of synchronous iterative algorithms may be transformed into asynchronous iterative algorithms. They then prove that the correctness of the resulting asynchronous algorithm can be guaranteed by reasoning about the synchronous algorithm alone. These results have been used to prove the correctness of various distributed algorithms, including in the fields of routing, numerical analysis and peer-to-peer protocols. In this paper we demonstrate several ways in which the assumptions that underlie this theory may be relaxed. Amongst others, we (i) expand the set of schedules for which the asynchronous iterative algorithm is known to converge and (ii) weaken the conditions that users must prove to hold to guarantee convergence. Furthermore, we demonstrate that two of the auxiliary results in the original paper are incorrect, and explicitly construct a counter-example. Finally, we also relax the alternative convergence conditions proposed by Gurney based on ultrametrics. Many of these relaxations and errors were uncovered after formalising the work in the proof assistant Agda. This paper describes the Agda code and the library that has resulted from this work. It is hoped that the library will be of use to others wishing to formally verify the correctness of asynchronous iterative algorithms. Matthew L. Daggitt, Ran Zmigrod, Timothy G. Griffin	J. Autom. Reason.	2
2019	Counterfactual Data Augmentation for Mitigating Gender Stereotypes in Languages with Rich Morphology abstract Gender stereotypes are manifest in most of the world's languages and are consequently propagated or amplified by NLP systems.Although research has focused on mitigating gender stereotypes in English, the approaches that are commonly employed produce ungrammatical sentences in morphologically rich languages.We present a novel approach for converting between masculine-inflected and feminineinflected sentences in such languages.For Spanish and Hebrew, our approach achieves F 1 scores of 82% and 73% at the level of tags and accuracies of 90% and 87% at the level of forms.By evaluating our approach using four different languages, we show that, on average, it reduces gender stereotyping by a factor of 2.5 without any sacrifice to grammaticality. Ran Zmigrod, Sabrina J. Mielke, Hanna M. Wallach, Ryan Cotterell	ACL (1)	1
2018	An Agda Formalization of Üresin and Dubois' Asynchronous Fixed-Point Theory abstract In this paper we describe an Agda-based formalization of results from Üresin & Dubois’ “Parallel Asynchronous Algorithms for Discrete Data.” That paper investigates a large class of iterative algorithms that can be transformed into asynchronous processes. In their model each node asynchronously performs partial computations and communicates results to other nodes using unreliable channels. Üresin & Dubois provide sufficient conditions on iterative algorithms that guarantee convergence to unique fixed points for the associated asynchronous iterations. Proving such sufficient conditions for an iterative algorithm is often dramatically simpler than reasoning directly about an asynchronous implementation. These results are used extensively in the literature of distributed computation, making formal verification worthwhile. Our Agda library provides users with a collection of sufficient conditions, some of which mildly relax assumptions made in the original paper. Our primary application has been in reasoning about the correctness of network routing protocols. To do so we have derived a new sufficient condition based on the ultrametric theory of Alexander Gurney. This was needed to model the complex policy-rich routing protocol that maintains global connectivity in the internet. Additionally we highlight and discuss two propositions from Üresin & Dubois, which during the course of the formalisation, turned out to be false. Ran Zmigrod, Matthew L. Daggitt, Timothy G. Griffin	ITP	1