1 citations · 1 across the 16 of their papers we have counts for
26 papers
More of the same? Are scientific papers losing originality?
Ilan Doron-Arad, Elchanan Mossel
Scientific output is growing rapidly, but it is unclear whether the expanding literature remains original or is increasingly repeating itself. Originality has many dimensions. One…
Tight Approximation Results for Matroid Optimization with a Linear Constraint
Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler
We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions , and a threshold…
A Tight Information-Theoretic Lower Bound for Randomized Online Set Cover
Ilan Doron-Arad, Joseph, Naor
Online set cover is a fundamental problem in online algorithms, admitting a deterministic -competitive algorithm, where is the number of sets and is the nu…
Stochastic Autoregressive Learning
Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
Motivated by LLMs, which generate outputs by iteratively sampling from next-token distributions, we introduce a PAC-learning model for binary stochastic autoregressive learning. Th…
Incremental Dominating Set
Ilan Doron Arad, Jonathan Gal, Seffi Naor
Dominating Set is a fundamental problem in graph theory: given a graph, find a minimum-weight subset of vertices such that every vertex is either selected or adjacent to a selected…
Genetic Algorithms with Optimization Guided Operators
Anna Brandenberger, Ilan Doron-Arad, Elchanan Mossel
Recent work in ML applies genetic algorithms at inference time to iteratively improve solutions to optimization problems. The basic mutation and recombination operators involved ar…
A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning
Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
Autoregressive generation lies at the heart of the mechanism of large language models. It can be viewed as the repeated application of a next-token generator: starting from an inpu…
Why ReLU? A Bit-Model Dichotomy for Deep Network Training
Ilan Doron-Arad, Elchanan Mossel
Theoretical analyses of Empirical Risk Minimization (ERM) are standardly framed within the Real-RAM model of computation. In this setting, training even simple neural networks is k…
Online Realizable Regression and Applications for ReLU Networks
Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
Realizable online regression can behave very differently from online classification. Even without any margin or stochastic assumptions, realizability may enforce horizon-free (fini…
An Algorithm-to-Contract Framework without Demand Queries
Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler +1
Consider costly and time-consuming tasks that add up to the success of a project, and must be fitted into a given time-frame. This is an instance of the classic budgeted maximizati…
On the Hardness of Training Deep Neural Networks Discretely
Ilan Doron-Arad
We study neural network training (NNT): optimizing a neural network's parameters to minimize the training loss over a given dataset. NNT has been studied extensively under theoreti…
You (Almost) Can't Beat Brute Force for 3-Matroid Intersection
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
The -matroid intersection (-MI) problem asks if given matroids share a common basis. Already for , notable canonical NP-complete special cases are -…
Fine Grained Lower Bounds for Multidimensional Knapsack
Ilan Doron-Arad, Ariel Kulik, Pasin Manurangsi
We study the -dimensional knapsack problem. We are given a set of items, each with a -dimensional cost vector and a profit, along with a -dimensional budget vector. The go…
Unsplittable Flow on a Short Path
Ilan Doron-Arad, Fabrizio Grandoni, Ariel Kulik
In the Unsplittable Flow on a Path problem UFP, we are given a path graph with edge capacities and a collection of tasks. Each task is characterized by a demand, a profit, and a su…
Non-Linear Paging
Ilan Doron-Arad, Joseph, Naor
We formulate and study non-linear paging - a broad model of online paging where the size of subsets of pages is determined by a monotone non-linear set function of the pages. This…
Approximations and Hardness of Packing Partially Ordered Items
Ilan Doron-Arad, Guy Kortsarz, Joseph Naor +2
Motivated by applications in production planning and storage allocation in hierarchical databases, we initiate the study of covering partially ordered items (CPO). Given a capacity…
An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
In [Math. Oper. Res., 2011], Fleischer et al. introduced a powerful technique for solving the generic class of separable assignment problems (SAP), in which a set of items of given…
Tight Bounds for Budgeted Maximum Weight Independent Set in Bipartite and Perfect Graphs
Ilan Doron-Arad, Hadas Shachnai
We consider the classic budgeted maximum weight independent set (BMWIS) problem. The input is a graph , a weight function , a cost f…
Budgeted Matroid Maximization: a Parameterized Viewpoint
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We study budgeted variants of well known maximization problems with multiple matroid constraints. Given an -matchoid $\cm$ on a ground set , a profit function $p:E \righta…
Lower Bounds for Matroid Optimization Problems with a Linear Constraint
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We study a family of matroid optimization problems with a linear constraint (MOL). In these problems, we seek a subset of elements which optimizes (i.e., maximizes or minimizes) a…
An FPTAS for Budgeted Laminar Matroid Independent Set
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We study the budgeted laminar matroid independent set problem. The input is a ground set, where each element has a cost and a non-negative profit, along with a laminar matroid over…
Approximating Bin Packing with Conflict Graphs via Maximization Techniques
Ilan Doron-Arad, Hadas Shachnai
We give a comprehensive study of bin packing with conflicts (BPC). The input is a set of items, sizes , and a conflict graph . The goal is to…
An EPTAS for Budgeted Matching and Budgeted Matroid Intersection
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We study the budgeted versions of the well known matching and matroid intersection problems. While both problems admit a polynomial-time approximation scheme (PTAS) [Berger et al.…
Bin Packing with Partition Matroid can be Approximated within Bins
Ilan Doron-Arad, Ariel Kulik, Hadas Shachnai
We consider the Bin Packing problem with a partition matroid constraint. The input is a set of items of sizes in , and a partition matroid over the items. The goal is to pac…