Fun Word Challenge - Animal, Transportation, Food, Furniture
Test your word-building skills by filling in letters to create words related to animals, transportation, food, and furniture. Score points based on how well the letters match the category. Challenge yourself with varying levels of difficulty and see how high you can score!
Uploaded on Sep 28, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Find! Fill out letters on the right, to satisfy as much of the constraints on the left. animal verb transportation food furniture verb
Find! When the letters form a word in a category, get 1 point per letter. b animal b a t verb a transportation food furniture t verb Score: 3
Find! When the letters form a word in a category, get 1 point per letter. b animal b a t c a b verb transportation c a b food furniture t verb Score: 6
Find! When the letters form a word in a category, get 1 point per letter. b animal b a t c a b verb transportation c a b food furniture t verb Score: 6
Find! When the letters partially match a word in a category, get 1 point per match. b animal b a t c a b e t verb transportation c a b food furniture b e d verb Score: 8
Find! When the letters partially match a word in a category, get 1 point per match. b animal b a t c a b e t y verb transportation c a b food furniture b e d verb c r y Score: 10
Find! When the letters partially match a word in a category, get 1 point per match. b animal b a t c a b e t y verb ? a y transportation c a b food furniture b e d verb c r y Score: 10
Find! When the letters partially match a word in a category, get 1 point per match. b animal b a t c a b e t y verb ? a y transportation c a b food ? e y furniture b e d verb c r y Score: 10
Find! When the letters partially match a word in a category, get 1 point per match. b p c a b e t y animal b a t verb p a y transportation c a b food p e a furniture b e d verb c r y Score: 15
Find! Your turn: How much can you score? animal verb transportation food furniture verb Score:
Find! To get the total score, sum up the points from all the categories. b p c a b e t y animal b a t verb p a y transportation c a b food p e a furniture b e d verb c r y Score: 15
Find! Perfect score! c s c a r o t y animal c a t verb s a y transportation c a r food s o y furniture c o t verb c r y Score: 18
Given a projection game so that perfect score is achievable, Projection games can you score 1% ?
Given a projection game so that perfect score is achievable. Can you get a perfect score ?
Given a projection game so that perfect score is achievable. Can you score 99% ?
Given a projection game so that perfect score is achievable. Can you score 75% ?
Given a projection game so that perfect score is achievable. Can you score 50% ?
Observations: 1. If there are X edges, can always score 1/X.
Observations: 1. If there are X edges, can always score 1/X. 2. If each constraint is on X locations, can score 1/X.
Observations: 1. If there are X edges, can always score 1/X. 2. If each constraint is on X locations, can score 1/X. 3. If each location is in X constraints, can score 1/X.
Observations: 1. If there are X edges, can always score 1/X. 2. If each constraint is on X locations, can score 1/X. 3. If each location is in X constraints, can score 1/X. 4. If all categories are of size X, can score 1/X. All 3 letter words under food
Observations: 1. If there are X edges, can always score 1/X. 2. If each constraint is on X locations, can score 1/X. 3. If each location is in X constraints, can score 1/X. 4. If all categories are of size X, can score 1/X. 5. If the alphabet is of size X, can score 1/X.
Given a projection game with large categories, alphabet and degrees, so perfect score is achievable. Can you score 1% ?
Projection Games Theorem (M-Raz 08): There exists >0 such that for all = (n) 1/n , there exist k=poly(1/ ), D=poly(1/ ), so given a projection game of size n, alphabet size k and degrees D, where perfect score is achievable, NP-hard to score even percent. More than that Almost as hard as exact 3SAT.
From Trivial To Super-Hard In A Flash! [H stad 97, M-Raz 08] Assuming that exact SAT takes exponential time time 2 (n) exponential Exponential hardness Sharp threshold nO(1) polynomial approx t 1
Max-3SAT Max-3LIN The best hardness of approximation results we know are based on projection games Max-CSP Set-Cover Independent Set Clique Densest Subgraph Closest Vector Problem Directed Sparsest Cut Directed Multi-cut K-Spanner ..
Probabilistic Checking of Proofs (PCP) [FGLSS 91] Conjecture: 1 + 1 = 2 Proof: 1. x;x=y (x=z y=z) 2. x;x=y (x=z y=z) x+0=y (x+0=z y=z) 3. x+0=y (x+0=z y=z)
Probabilistic Checking of Proofs (PCP) [FGLSS 91] w w i t Conjecture: A + B = C p p i s w i n Proof: 1. x;x=y (x=z y=z) i i t i n i 2. x;x=y (x=z y=z) x+0=y (x+0=z y=z) t 3. x+0=y (x+0=z y=z) n
Probabilistic Checking of Proofs (PCP) [FGLSS 91] Conjecture: A + B = C Proof: 1. x;x=y (x=z y=z) 2. x;x=y (x=z y=z) x+0=y (x+0=z y=z) False! 3. x+0=y (x+0=z y=z) Score
Probabilistic Checking of Proofs (PCP) [FGLSS 91] w w i t Conjecture: A + B = C p p i s w i n Proof: 1. x;x=y (x=z y=z) i i t i n i 2. x;x=y (x=z y=z) x+0=y (x+0=z y=z) t 3. x+0=y (x+0=z y=z) n Observe: The PCP Thm induces a new format for proofs; can be tested by checking one implication!
What Goes Into PCPs? Algebra Combinatorics expanders,.. polynomials over finite fields.. Analysis Fourier, isoperimetry..
Favorite Open Problems Projection Games Conjecture: Projection games NP-hard even when all categories are of size poly(1/ ). Unique Games Conjecture: Projection games NP-hard even when in each category all possible words differ in all their letters; best score is (1- ) fraction of maximum.
