Publications of Ardalan Khazraei

2021 [ nach oben ]

Khazraei, Ardalan; Kötzing, Timo; Seidel, Karen Towards a Map for Incremental Learning in the Limit from Positive and Negative InformationComputability in Europe (CiE) 2021: 273–284
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In order to model an efficient learning paradigm, iterative learning algorithms access data one by one, updating the current hypothesis without regress to past data. Prior research investigating the impact of additional requirements on iterative learners left many questions open, especially in learning from informant, where the input is binary labeled.
@inproceedings{khazraei2021towards, abstract = {In order to model an efficient learning paradigm, iterative learning algorithms access data one by one, updating the current hypothesis without regress to past data. Prior research investigating the impact of additional requirements on iterative learners left many questions open, especially in learning from informant, where the input is binary labeled.}, author = {Khazraei, Ardalan and Kötzing, Timo and Seidel, Karen}, booktitle = {Computability in Europe (CiE)}, keywords = {ardalankhazraei cie karenseidel timokoetzing year2021}, pages = {273-284}, title = {Towards a Map for Incremental Learning in the Limit from Positive and Negative Information}, year = 2021 }

2020 [ nach oben ]

Feldmann, Michael; Khazraei, Ardalan; Scheideler, Christian Time- and Space-Optimal Clock Synchronization in the Beeping ModelSymposium Parallelism in Algorithms and Architectures (SPAA) 2020: 223–233
[ Abstract ] [ BibTeX ] [ DOI ]
 
We consider the clock synchronization problem in the (discrete) beeping model: Given a network of \(n\) nodes with each node having a clock value \(\delta(v) \in\) \(\{ 0,\ldots , T-1\}\), the goal is to synchronize the clock values of all nodes such that they have the same value in any round. As is standard in clock synchronization, we assume arbitrary activations for all nodes, i.e., the nodes start their protocol at an arbitrary round (not limited to \(\{0,\ldots,T-1\}\)). We give an asymptotically optimal algorithm that runs in \( 4D + \lfloor D/\lfloor T/4 \rfloor \rfloor \cdot\ \)\((T \mod 4) = O(D)\) rounds, where \(D\) is the diameter of the network. Once all nodes are in sync, they beep at the same round every \(T\) rounds. The algorithm drastically improves on the \(O(T D)\)-bound of [Alistarh et al. 2013] (where \(T\) is required to be at least \(4n\), so the bound is no better than \(O(nD)\)). Our algorithm is very simple as nodes only have to maintain \(3\) bits in addition to the \(\lceil \log T \rceil\) bits needed to maintain the clock. Furthermore we investigate the complexity of self-stabilizing solutions for the clock synchronization problem: We first show lower bounds of \(\Omega(\max\{T,n\})\) rounds on the runtime and \(\Omega(\log(\max\{T,n\}))\) bits of memory required for any such protocol. Afterwards we present a protocol that runs in \(O(\max\{T,n\})\) rounds using at most \(O(\log(\max\{T,n\}))\) bits at each node, which is asymptotically optimal with regards to both, runtime and memory requirements.
@inproceedings{feldmann2020spaceoptimal, abstract = {We consider the clock synchronization problem in the (discrete) beeping model: Given a network of \(n\) nodes with each node having a clock value \(\delta(v) \in\) \(\{ 0,\ldots , T-1\}\), the goal is to synchronize the clock values of all nodes such that they have the same value in any round. As is standard in clock synchronization, we assume arbitrary activations for all nodes, i.e., the nodes start their protocol at an arbitrary round (not limited to \(\{0,\ldots,T-1\}\)). We give an asymptotically optimal algorithm that runs in \( 4D + \lfloor D/\lfloor T/4 \rfloor \rfloor \cdot\ \)\((T \mod 4) = O(D)\) rounds, where \(D\) is the diameter of the network. Once all nodes are in sync, they beep at the same round every \(T\) rounds. The algorithm drastically improves on the \(O(T D)\)-bound of [Alistarh et al. 2013] (where \(T\) is required to be at least \(4n\), so the bound is no better than \(O(nD)\)). Our algorithm is very simple as nodes only have to maintain \(3\) bits in addition to the \(\lceil \log T \rceil\) bits needed to maintain the clock. Furthermore we investigate the complexity of self-stabilizing solutions for the clock synchronization problem: We first show lower bounds of \(\Omega(\max\{T,n\})\) rounds on the runtime and \(\Omega(\log(\max\{T,n\}))\) bits of memory required for any such protocol. Afterwards we present a protocol that runs in \(O(\max\{T,n\})\) rounds using at most \(O(\log(\max\{T,n\}))\) bits at each node, which is asymptotically optimal with regards to both, runtime and memory requirements.}, author = {Feldmann, Michael and Khazraei, Ardalan and Scheideler, Christian}, booktitle = {Symposium Parallelism in Algorithms and Architectures (SPAA)}, keywords = {sys:relevantfor:ae ardalankhazraei christianscheideler michaelfeldmann spaa year2020}, pages = {223-233}, title = {Time- and Space-Optimal Clock Synchronization in the Beeping Model}, year = 2020 }

Held, Stephan; Khazraei, Ardalan An Improved Approximation Algorithm for the Uniform Cost-Distance Steiner Tree ProblemWorkshop on Approximation and Online Algorithms (WAOA) 2020: 189–203
[ Abstract ] [ BibTeX ] [ URL ]
 
The cost-distance Steiner tree problem asks for a Steiner tree in a graph that minimizes the total cost plus a weighted sum of path delays from the root to the sinks. We present an improved approximation for the uniform cost-distance Steiner tree problem, where the delay of a path corresponds to the sum of edge costs along that path. Previous approaches deploy a bicriteria approximation algorithm for the length-bounded variant that does not take the actual delay weights into account. Our algorithm modifies a similar algorithm for the single-sink buy-at-bulk problem by Guha et al. [2009], allowing a better approximation factor for our problem. In contrast to the bicriteria algorithms it considers delay weights explicitly. Thereby, we achieve an approximation factor of (1+ \(\beta\) ), where \(\beta\) is the approximation factor for the Steiner tree problem. This improves the previously best known approximation factor for the uniform cost-distance Steiner tree problem from 2:87 to 2:39. This algorithm can be extended to the problem where the ratio of edge costs to edge delays throughout the graph is bounded from above and below. In particular, this shows that a previous inapproximability result (Chuzhoy et al. [2008]) requires large variations between edge delays and costs. Finally, we present an important application of our new algorithm in chip design. The cost-distance Steiner tree problem occurs as a Lagrangean subproblem when optimizing millions of Steiner trees with mutually depending path length bounds. We show how to quickly approximate a continuous relaxation of this problem with our new algorithm.
@inproceedings{held2020improved, abstract = {The cost-distance Steiner tree problem asks for a Steiner tree in a graph that minimizes the total cost plus a weighted sum of path delays from the root to the sinks. We present an improved approximation for the uniform cost-distance Steiner tree problem, where the delay of a path corresponds to the sum of edge costs along that path. Previous approaches deploy a bicriteria approximation algorithm for the length-bounded variant that does not take the actual delay weights into account. Our algorithm modifies a similar algorithm for the single-sink buy-at-bulk problem by Guha et al. [2009], allowing a better approximation factor for our problem. In contrast to the bicriteria algorithms it considers delay weights explicitly. Thereby, we achieve an approximation factor of (1+ \(\beta\) ), where \(\beta\) is the approximation factor for the Steiner tree problem. This improves the previously best known approximation factor for the uniform cost-distance Steiner tree problem from 2:87 to 2:39. This algorithm can be extended to the problem where the ratio of edge costs to edge delays throughout the graph is bounded from above and below. In particular, this shows that a previous inapproximability result (Chuzhoy et al. [2008]) requires large variations between edge delays and costs. Finally, we present an important application of our new algorithm in chip design. The cost-distance Steiner tree problem occurs as a Lagrangean subproblem when optimizing millions of Steiner trees with mutually depending path length bounds. We show how to quickly approximate a continuous relaxation of this problem with our new algorithm.}, author = {Held, Stephan and Khazraei, Ardalan}, booktitle = {Workshop on Approximation and Online Algorithms (WAOA)}, keywords = {ardalankhazraei stephanheld waoa year2020}, pages = {189-203}, title = {An Improved Approximation Algorithm for the Uniform Cost-Distance Steiner Tree Problem}, year = 2020 }

Khazraei, Ardalan; Kötzing, Timo; Seidel, Karen Learning Half-Spaces and other Concept Classes in the Limit with Iterative LearnersCoRR 2020
ArXiv preprint
[ Abstract ] [ BibTeX ] [ URL ] [ Download ]
 
In order to model an efficient learning paradigm, iterative learning algorithms access data one by one, updating the current hypothesis without regress to past data. Past research on iterative learning analyzed for example many important additional requirements and their impact on iterative learners. In this paper, our results are twofold. First, we analyze the relative learning power of various settings of iterative learning, including learning from text and from informant, as well as various further restrictions, for example we show that strongly non-U-shaped learning is restrictive for iterative learning from informant. Second, we investigate the learnability of the concept class of half-spaces and provide a constructive iterative algorithm to learn the set of half-spaces from informant.
@article{khazraeikoetzingseidel2020ItInfExhalfspaces, abstract = {In order to model an efficient learning paradigm, iterative learning algorithms access data one by one, updating the current hypothesis without regress to past data. Past research on iterative learning analyzed for example many important additional requirements and their impact on iterative learners. In this paper, our results are twofold. First, we analyze the relative learning power of various settings of iterative learning, including learning from text and from informant, as well as various further restrictions, for example we show that strongly non-U-shaped learning is restrictive for iterative learning from informant. Second, we investigate the learnability of the concept class of half-spaces and provide a constructive iterative algorithm to learn the set of half-spaces from informant.}, author = {Khazraei, Ardalan and Kötzing, Timo and Seidel, Karen}, journal = {CoRR}, keywords = {ardalankhazraei arxiv karenseidel timokoetzing year2020}, note = {ArXiv preprint}, title = {Learning Half-Spaces and other Concept Classes in the Limit with Iterative Learners}, volume = {arXiv:2010.03227}, year = 2020 }