Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Adversarial and Online Algorithms
View through CrossRef
<p><b>In this thesis we explore a variety of online and adversarial algorithms. We primarily explore the following online and adversarial algorithms; the perfect code game, adversarial online colouring, the chain decomposition game, and strongly online graphs.</b></p>
<p>The perfect code game is a new adversarial game played on graphs in which players take turns constructing perfect codes. We provide definitions for perfect codes and the perfect code game, along with some motivation from coding theory. We will prove upper bounds for both cycle and path graphs. We also prove an upper bound for graphs of bounded pathwidth. Finally, we explore the perfect code game in graphs of bounded degree.</p>
<p>We will create a new game called the adversarial online colouring game, this game takes elements from both online and adversarial algorithms. We will begin with some discussion and a definition of adversarial online colouring. We will then prove several results related to graph degree. We conclude with a proof that the adversarial online colouring game on trees is determined only by the number of colours and the number of vertices (assuming that both players have a chance at winning).</p>
<p>The chain decomposition game is another adversarial game, but this time played on partial orders. We introduce the chain decomposition game and demonstrate two results relating to upper and lower bounds for the game. We also prove a result on the online adversarial version of the game.</p>
<p>We introduce strongly online graphs and graph colouring as a new algorithmic parameterization to online graph colouring. A strongly online graph is an online graph where at each stage ???? we can see a ball of increasing radius about each vertex. We will prove several bounds (upper and lower) on the online chromatic number of strongly online graphs. For example, we show that every strongly online graph can be coloured in twice its chromatic number. We prove that every strongly online graph with even pathwidth ???? can be online coloured with 2???? + 1 colours. Then, after introducing a natural notion of strongly online pathwidth, we prove that there is a strongly online graph with no finite strongly online path decomposition.</p>
Title: Adversarial and Online Algorithms
Description:
<p><b>In this thesis we explore a variety of online and adversarial algorithms.
We primarily explore the following online and adversarial algorithms; the perfect code game, adversarial online colouring, the chain decomposition game, and strongly online graphs.
</b></p>
<p>The perfect code game is a new adversarial game played on graphs in which players take turns constructing perfect codes.
We provide definitions for perfect codes and the perfect code game, along with some motivation from coding theory.
We will prove upper bounds for both cycle and path graphs.
We also prove an upper bound for graphs of bounded pathwidth.
Finally, we explore the perfect code game in graphs of bounded degree.
</p>
<p>We will create a new game called the adversarial online colouring game, this game takes elements from both online and adversarial algorithms.
We will begin with some discussion and a definition of adversarial online colouring.
We will then prove several results related to graph degree.
We conclude with a proof that the adversarial online colouring game on trees is determined only by the number of colours and the number of vertices (assuming that both players have a chance at winning).
</p>
<p>The chain decomposition game is another adversarial game, but this time played on partial orders.
We introduce the chain decomposition game and demonstrate two results relating to upper and lower bounds for the game.
We also prove a result on the online adversarial version of the game.
</p>
<p>We introduce strongly online graphs and graph colouring as a new algorithmic parameterization to online graph colouring.
A strongly online graph is an online graph where at each stage ???? we can see a ball of increasing radius about each vertex.
We will prove several bounds (upper and lower) on the online chromatic number of strongly online graphs.
For example, we show that every strongly online graph can be coloured in twice its chromatic number.
We prove that every strongly online graph with even pathwidth ???? can be online coloured with 2???? + 1 colours.
Then, after introducing a natural notion of strongly online pathwidth, we prove that there is a strongly online graph with no finite strongly online path decomposition.
</p>.
Related Results
ProDef-MDS: A Proactive Defense Mechanism Protecting Malware Detection Systems from Adversarial Attacks
ProDef-MDS: A Proactive Defense Mechanism Protecting Malware Detection Systems from Adversarial Attacks
Malware threatens cybersecurity by enabling data theft, unauthorized access, and extortion. Traditional malware detection systems (MDS) struggle with the increasing volume and comp...
Improving Diversity and Quality of Adversarial Examples in Adversarial Transformation Network
Improving Diversity and Quality of Adversarial Examples in Adversarial Transformation Network
Abstract
This paper proposes a method to mitigate two major issues of Adversarial Transformation Networks (ATN) including the low diversity and the low quality of adversari...
Efficient Defense Against First Order Adversarial Attacks on Convolutional Neural Networks
Efficient Defense Against First Order Adversarial Attacks on Convolutional Neural Networks
Machine learning models, especially neural networks, are vulnerable to adversarial attacks, where inputs are purposefully altered to induce incorrect predictions. These adversarial...
An enhanced ensemble defense framework for boosting adversarial robustness of intrusion detection systems
An enhanced ensemble defense framework for boosting adversarial robustness of intrusion detection systems
Abstract
Machine learning (ML) and deep neural networks (DNN) have emerged as powerful tools for enhancing intrusion detection systems (IDS) in cybersecurity. However, re...
Testing the waters: An investigation of the impact of hot tubbing on experts from referral through testimony
Testing the waters: An investigation of the impact of hot tubbing on experts from referral through testimony
Objective: The present research examined whether concurrent expert testimony, or hot tubbing, is able to reduce adversarial allegiance compared to traditional adversarial expert te...
Improving Intrusion Detection Systems' Resilience to Adversarial Attacks through Feature Engineering and Hybrid Metaheuristic Algorithms
Improving Intrusion Detection Systems' Resilience to Adversarial Attacks through Feature Engineering and Hybrid Metaheuristic Algorithms
Abstract
Intrusion Detection Systems (IDS) are essential for securing computer networks against malicious activities. However, the rise of adversarial attacks serio...
Adversarial Training and Robustness in Machine Learning Frameworks
Adversarial Training and Robustness in Machine Learning Frameworks
In the realm of machine learning, ensuring robustness against adversarial attacks is increasingly crucial. Adversarial training has emerged as a prominent strategy to fortify model...
Adversarial Robustness Improvement for Deep Neural Networks
Adversarial Robustness Improvement for Deep Neural Networks
Abstract
Deep neural networks (DNNs) are key components for the implementation of autonomy in systems that operate in highly complex and unpredictable environments (self-dr...