1,736,089 research outputs found
On Rich 2-to-1 Games
Full text linkWe propose a variant of the 2-to-1 Games Conjecture that we call the Rich 2-to-1 Games Conjecture and show that it is equivalent to the Unique Games Conjecture. We are motivated by two considerations. Firstly, in light of the recent proof of the 2-to-1 Games Conjecture [Subhash Khot et al., 2017; Irit Dinur et al., 2018; Irit Dinur et al., 2018; Subhash Khot et al., 2018], we hope to understand how one might make further progress towards a proof of the Unique Games Conjecture. Secondly, the new variant along with perfect completeness in addition, might imply hardness of approximation results that necessarily require perfect completeness and (hence) are not implied by the Unique Games Conjecture
Animalia Humorosum: Aesop's animal fables made more believable with a modern twist
No full textThere is much that is unusual about this 8½” square booklet of 28 pages followed by two pages of advertisements for other books by Óla. For starters, the pages are purple with light-colored typeface and cutout colored characters in partial-page illustrations. The T of C uses superscript to indicate page numbers for the twelve fables. That same page clarifies that Ólafia L. Óla is a pseudonym for V. Subhash. In TH, the hare, not the tortoise, challenges to a race upon no provocation. The author turns this tale into the more usual “Rabbit Races the Hedgehog,” famous among Grimm’s fairytales. Every one of the species looks the same to the superficial hare. In LM, after the mouse frees the lion, the hungry lion eats the mouse. “Steer clear of known dangers.” DW is told just as in the tradition. “Better die on your feet than live on your knees.” In TB, the second traveler takes off his socks; the smell of them revolts the bear, who departs. What did the bear whisper to him? “Tell that fellow that trees offer no safety because bears are good climbers.” The ox makes up a snake friend to worry the dog out of his manger. A passing hunter saves the shepherd boy attacked by a real wolf. The mice do manage to get a bell around the cat’s neck by having it ready around their hole when the cat pokes in its head. Two foxes jump for grapes. One reacts according to the tradition. The other says the effort has been stupid. “We are foxes. We don’t eat grapes. Let’s go and catch some rabbits.” One of two crows suggests the traditional pebble approach. The other says that will take too much time and too many pebbles and will dirty the water. He manages to knock over the pitcher and they can drink both from the water spilled and the water still in the overturned pitcher. The owner of the golden goose eventually stops reading his mail, misses paying taxes, loses his property, and has to give up the goose as compensation for the unpaid taxes. The wolf escapes the lambskin and never comes back. The crow removes the doughnut from his mouth and tells the fox to move along.Ólafia L. Óla (V. Subhash
Preimage Attacks on CellHash, SubHash and Strengthened Versions of CellHash and SubHash
Full text linkCellHash \cite{DaGoVa91} and SubHash \cite{DaGoVa92} were suggested
by J. Daemen, R. Govaerts and J. Vandewalle in 1991 and 1992.
SubHash is an improved version from CellHash. They have 257-bit
internal state and 256-bit hash output. In this paper, we show a
preimage attack on CellHash (SubHash) with the complexity
and the memory for any (with the
complexity about and the memory size ). Even
though we modify them in a famous way, we show that we can find a
preimage on the modified CellHash (the modified SubHash) with the
complexity and the memory size (with the
complexity about and the memory size )
Preimage Attacks on CellHash, SubHash and Strengthened Versions of CellHash and SubHash
No full textAbstract. CellHash [3] and SubHash [4] were suggested by J. Daemen
Recommended from our members
UG-Hardness to NP-Hardness by Losing Half
Full text linkThe 2-to-2 Games Theorem of [Subhash Khot et al., 2017; Dinur et al., 2018; Dinur et al., 2018; Dinur et al., 2018] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least (1/2-epsilon) fraction of the constraints vs. no assignment satisfying more than epsilon fraction of the constraints, for every constant epsilon>0. We show that the reduction can be transformed in a non-trivial way to give a stronger guarantee in the completeness case: For at least (1/2-epsilon) fraction of the vertices on one side, all the constraints associated with them in the Unique Games instance can be satisfied.
We use this guarantee to convert the known UG-hardness results to NP-hardness. We show:
1) Tight inapproximability of approximating independent sets in degree d graphs within a factor of Omega(d/(log^2 d)), where d is a constant.
2) NP-hardness of approximate the Maximum Acyclic Subgraph problem within a factor of 2/3+epsilon, improving the previous ratio of 14/15+epsilon by Austrin et al. [Austrin et al., 2015].
3) For any predicate P^{-1}(1) subseteq [q]^k supporting a balanced pairwise independent distribution, given a P-CSP instance with value at least 1/2-epsilon, it is NP-hard to satisfy more than (|P^{-1}(1)|/(q^k))+epsilon fraction of constraints
Evolved Infantry Subhash Mukhopadhyay/ বিবর্তিত পদাতিক সুভাষ মুখোপাধ্যায়
No full textWhen the present moves towards the future, leaving the past as a witness, it changes itself and reaches its end. In this change, even if the external structure changes, the ideological infrastructure remains intact. Then we do not call it change, but evolution. However, this evolution is not only an evolution of spatial geography and temporal dimensions; it is also an evolution of the mind and mood of the evolved person. Subhash Mukherjee is no exception of this thinking. He is a real example of such evolution. Not only in his political philosophy of life, but also in his literary-centered meditations, poet Subhash Mukhopadhyay did not follow a set path. He changed his opinion, but remained steadfast in his goal. He moved away from leftism ideology and joined hands
with Gandhism. That is true. However, he did not abandon communism. Evolution is the law of the ideological universe. But we must see to it that, that evolved consciousness does not hurt the collective convictions. Subhash Mukhopadhyay is a skilled thinker-artist in this work.
Therefore, in the article under discussion, the primary intention of the author will be to create an outline of evolution in terms of Subhash Mukhopadhyay’s criticism of life, social consciousness, political thought, poetic thought, poetic justice, linguistic thought, aesthetic sense etc. It is to be noted that more examples will be provided from the poet\u27s various poems to authenticate the logical tradition of the discussion. However, for the purpose of presenting the subject matter of the article, various literary forms such as novels, letters or songs will also be used in addition to the poet\u27s poems. And by the end of the article, following these steps, we will reach the evolved consciousness of poet Subhash Mukhopadhyay
Recommended from our members
The work of Subhash Khot
No full textSubhash Khot, the winner of the 2014 Nevanlinna Prize, has brought new clarity to the study of approximation algorithms for NP-hard problems, and opened new avenues of research. Several of these concern his Unique Games Conjecture, which has led to optimal inapproximability results that exactly characterize the approximability of the problem
- …
