Skip to main content

Questions tagged [adversary]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers

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 ...
jam's user avatar
  • 13
3 votes
0 answers

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$ ...
AspiringMat's user avatar
1 vote
0 answers

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(...
Osama Naeem's user avatar
1 vote
0 answers

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 (...
user143196's user avatar
2 votes
1 answer

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 ...
user avatar
4 votes
3 answers

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. ...
chausies's user avatar
  • 532
0 votes
0 answers

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 ...
gradstudent's user avatar
2 votes
2 answers

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$ ...
dzhqjk's user avatar
  • 63
1 vote
1 answer

lower bound proof with adversary argument

We have to run a song on a Walkman, for that we need 2 full batteries. Let's say we have a mixed set of 30 batteries (15 are empty and and 15 are full) and then only way to test if the battery is full ...
Mohbenay's user avatar
  • 319