6 papers
Robin Hood Reachability Bidding Games
Shaull Almagor, Guy Avni, Neta Dafni
Two-player graph games are a fundamental model for reasoning about the interaction of agents. These games are played between two players who move a token along a graph. In bidding…
Quantitative Semantics for Jumping Automata
Shaull Almagor, Neta Dafni, Ishai Salgado
Jumping automata are finite automata that read their input in a non-sequential manner, by allowing a reading head to ``jump'' between positions on the input, consuming a permutatio…
Determinization of Integral Discounted-Sum Automata is Decidable
Shaull Almagor, Neta Dafni
Nondeterministic Discounted-Sum Automata (NDAs) are nondeterministic finite automata equipped with a discounting factor , and whose transitions are labelled by weights. The va…
Uniqueness for 2-Intersecting Families of Permutations and Perfect Matchings
Gilad Chase, Neta Dafni, Yuval Filmus +1
We give a characterization of the largest -intersecting families of permutations of and of perfect matchings of the complete graph for all …
Complexity Measures on the Symmetric Group and Beyond
Neta Dafni, Yuval Filmus, Noam Lifshitz +2
We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decisi…
Fast Deterministic Algorithms for Highly-Dynamic Networks
Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov +2
This paper provides an algorithmic framework for obtaining fast distributed algorithms for a highly-dynamic setting, in which *arbitrarily many* edge changes may occur in each roun…