1 citations · 1 across the 16 of their papers we have counts for
6 papers · 1 filter
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…