To join the email distribution list of the cs colloquia, please visit the list subscription page.
Computer Science events calendar in HTTP ICS format for of Google calendars, and for Outlook.
Academic Calendar at Technion site.
Alternation In One-Counter Nets
One-Counter Nets (OCNs) are finite-state automata equipped with a counter that is not allowed to become negative, but cannot be tested for zero. The counter can naturally be viewed as a resource that is accumulated and consumed along a run. Motivated by branching extensions of Vector Addition Systems, we introduce and study Alternating One-Counter Nets (AOCNs), in which a universal transition distributes the available counter among several continuations, all of which are required to accept.
When several branches later reach the same state, there are different natural ways to interpret their counter values. We study two such semantics: in the SUM semantics the arriving resources are aggregated, whereas in the MIN semantics only the smallest counter value is retained. The latter captures the intuition that the different universal branches must each be able to survive independently.
We study the basic language-theoretic and algorithmic properties of AOCNs under these semantics. We show that both semantics are closed under union and intersection but not under complementation, and establish decidability results for the emptiness and universality problems. Finally, we investigate the relative expressive power of the SUM and MIN semantics. While their precise relationship remains open, we present examples and partial results that illustrate the substantially different behavior of the two semantics and the difficulties involved in separating them.
Stable Multi-Principal ContractsContract theory studies how a principal can incentivize an agent to take costly actions. We study a multi-principal extension in which several strategic principals simultaneously offer linear contracts to a single agent, who then chooses a subset of principals to work for. In addition to incentivizing the agent, the contracts must form an equilibrium: no principal should benefit from unilaterally changing their contract. We study the computational problem of finding a stable outcome that maximizes the principals' total utility. In the symmetric setting, where all principals share the same reward function, we give polynomial-time algorithms for broad classes of reward functions, while showing NP-hardness and approximation hardness for submodular rewards. In the non-symmetric setting, the problem becomes NP-hard even for additive rewards, although we identify structured special cases that remain efficiently solvable.
The Effects of Discounting on Computational ModelsQuantitative finite-state systems, such as quantitative automata and graph games, are typically time-symmetric. We investigate the consequences of introducing geometric decay into these systems, through the lenses of discounted-sum automata (NDAs) and Robin Hood bidding games.
NDAs are nondeterministic finite automata equipped with transition weights, where the value of a run is the discounted sum of its weights, and the value of a word is the minimum value over all its accepting runs. The determinization problem asks whether, given an NDA, there exists a deterministic discounted-sum automaton (DDA) that assigns the exact same value to every word. We prove that the determinization problem for NDAs with integral discounting factors is decidable. Specifically, we provide an EXPSPACE algorithm to decide determinizability alongside an explicit construction for the equivalent DDA, and we establish a PSPACE-hardness lower bound for the problem.
As for graph games, we focus on Bidding Games, where players are allocated monetary budgets and bid in auctions to determine movement along the graph. We enrich this model with a wealth-redistribution phase before each turn, which discounts the difference between the players’ budgets. For reachability objectives, we prove the existence of a threshold function - the exact initial budget required for the reachability player to guarantee a win.
We place the associated computational problem in NP. We also reveal that, unlike traditional models, a Robin Hood game may become undetermined exactly at the threshold. For Büchi objectives, we provide a computable candidate for a threshold.
A Local Counting Approach for Distributed Induced Path DetectionA well-known application of the celebrated color-coding technique is fast detection of paths in a distributed setting with limited bandwidth, by propagating a signal along colorful paths [Even et al., DISC 2017]. However, since vertices of the same color are indistinguishable by this procedure, it cannot detect induced paths, as they appear the same as cycles.
We present a distributed local-counting technique that allows us to design fast algorithms for detecting induced paths, improving upon the state of the art in several aspects (time complexity, detection variant, and more).
The following observation illustrates our key technical ingredient: For each edge, count the number of signals, over all permutations of the random coloring, that terminate at that edge. An induced path contributes one to that count, while a cycle contributes two. Refining and generalizing this idea lets us distinguish induced 4-paths from other 4-vertex subgraphs in constant time and yields fast algorithms for detecting paths of lengths 5 and 6.
