# Questions tagged [adversary]

The tag has no usage guidance.

9 questions
Filter by
Sorted by
Tagged with
4 views

### Deterministic online caching algorithm competitive ratio lower bound proof

I don't understand the adversary based proof in CLRS for proving lower bound of Ω (k) on competitive ratio of any deterministic online caching algorithm given that ...
• 13
90 views

### Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$ [closed]

Given sorted $0\leq x_1 \leq x_2 \leq ... \leq x_n$ and $y_1 \geq y_2 \geq ... \geq y_n \geq 0$ non negative integers accessible through oracles, with the additional constraints $x_{i+1}-x_i \leq 1$ ...
• 613
1 vote
309 views

### Adversary argument and proving a lower bound of an algorithm. How does it work?

I need to understand how adversary argument works to prove the lower bound of an algorithm. For now, I am looking to prove that a "certain" algorithm that takes in input array requires omega(...
• 111
1 vote
72 views

### Hardness result for online matching

Currently studying the following paper: "Fair Allocation in Online Markets" - Gollapudi and Panigrahi 2014 In which they present Theorem 2 as a hardness result for online maxmin matchings (...
72 views

### Coming up with an adversary strategy for a clique of maximum size

I’m having trouble coming up with a good adversary strategy for this problem: Input: a graph G Output: the maximum size of any clique in G Where the algorithm asks each time, “are vertices x and y ...
233 views

### What is a sorting algorithm that is robust to a faulty comparison?

I want to sort a list of n items with a comparison sort. However, one of the comparisons made by the algorithm will be flipped from what it's supposed to be. ...
• 532
25 views

### Looking for references for real-world scenarios of data-poisoning attack on labels while doing supervised learning

Consider the following mathematical model of training a neural net : Suppose $f_{w} : \mathbb{R}^n \rightarrow \mathbb{R}$ is a neural net whose weights are $w$. Suppose during the training the ...
• 493
216 views

### Having a better complexity / adversary argument for finding if a finite automata accepts a palindrome

Let $A$ be a DFA over a finite alphabet $\Sigma$. Find an algorithm that indicates if $A$ accepts a palindrome and give the complexity of this algorithm. Here is my solution: If we denote $^t A$ ...
• 63
1 vote