research
∙
08/15/2023
Simple online learning with consistency oracle
We consider online learning in the model where a learning algorithm can ...
share
research
∙
04/05/2023
Inapproximability of sufficient reasons for decision trees
In this note, we establish the hardness of approximation of the problem ...
research
∙
03/22/2023
Three iterations of (d-1)-WL test distinguish non isometric clouds of d-dimensional points
The Weisfeiler–Lehman (WL) test is a fundamental iterative algorithm for...
research
∙
02/06/2023
Find a witness or shatter: the landscape of computable PAC learning
This paper contributes to the study of CPAC learnability – a computable ...
research
∙
08/17/2022
Constant-Depth Sorting Networks
In this paper, we address sorting networks that are constructed from com...
research
∙
08/04/2022
Infinite Separation between General and Chromatic Memory
In this note, we answer a question from [Alexander Kozachinskiy. State C...
research
∙
05/10/2022
Energy Games over Totally Ordered Groups
Kopczyński (ICALP 2006) conjectured that prefix-independent half-positio...
research
∙
01/23/2022
State Complexity of Chromatic Memory in Infinite-Duration Games
A major open problem in the area of infinite-duration games is to charac...
research
∙
10/24/2021
New Bounds for the Flock-of-Birds Problem
In this paper, we continue a line of work on obtaining succinct populati...
research
∙
04/28/2021
One-to-Two-Player Lifting for Mildly Growing Memory
We investigate so-called "one-to-two-player lifting" theorems for infini...
research
∙
12/16/2020
Continuous Positional Payoffs
What payoffs are positional for (deterministic) two-player antagonistic ...
research
∙
07/16/2020
Polyhedral value iteration for discounted games and energy games
We present a deterministic algorithm, solving discounted games with n no...
research
∙
02/18/2020
Multiparty Karchmer-Wigderson Games and Threshold Circuits
We suggest a generalization of Karchmer-Wigderson communication games to...
research
∙
02/19/2019
Lower bounds on separation automata for Parity Games
Several recently developed quasi-polynomial time algorithms for Parity G...
research
∙
02/12/2018
From expanders to hitting distributions and simulation theorems
Recently, Chattopadhyay et al. [chattopadhyay 2017 simulation] proved th...
research
∙
02/12/2018
Raz-McKenzie simulation: new gadget and unimprovability of Thickness Lemma
Assume that we have an outer function f:{0, 1}^n →{0, 1} and a gadget fu...
research
∙
02/11/2018
