research
∙
08/08/2023
On the approximability of the burning number
The burning number of a graph G is the smallest number b such that the v...
share
research
∙
10/28/2022
Parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances
We introduce stronger notions for approximate single-source shortest-pat...
research
∙
03/17/2022
Optimal schemes for combinatorial query problems with integer feedback
A query game is a pair of a set Q of queries and a set ℱ of functions, o...
research
∙
11/11/2020
Mastermind with a Linear Number of Queries
Since the 60's Mastermind has been studied for the combinatorial and inf...
research
∙
02/12/2020
An Optimal Decentralized (Δ+ 1)-Coloring Algorithm
Consider the following simple coloring algorithm for a graph on n vertic...
research
∙
07/12/2019
Navigating an Infinite Space with Unreliable Movements
We consider a search problem on a 2-dimensional infinite grid with a sin...
research
∙
02/11/2019
Optimal Kronecker-Sum Approximation of Real Time Recurrent Learning
One of the central goals of Recurrent Neural Networks (RNNs) is to learn...
research
∙
09/18/2018
Optimal strategies for patrolling fences
A classical multi-agent fence patrolling problem asks: What is the maxim...
research
∙
08/03/2018
When Does Hillclimbing Fail on Monotone Functions: An entropy compression argument
Hillclimbing is an essential part of any optimization algorithm. An impo...
research
∙
03/02/2018
The "No Justice in the Universe" phenomenon: why honesty of effort may not be rewarded in tournaments
In 2000 Allen Schwenk, using a well-known mathematical model of matchpla...
research
∙
01/22/2018