Thursday, January 17, 2019

The Cost of Privacy

Billboard at 2019 CES

Computer scientists tend to obsess about privacy and we've had a privacy/security debate for decades now. But now machine learning has really given us a whole new spin on what privacy protects and takes away.

I take an open approach and basically allow Google to know everything about my life. Google knows where I've been--sometimes my Pixel asks me which store in a shopping center I visited and I give up that info. Google knows who I communicate with, what websites I visit, what music and movies I listen to and watch, all my photos, what temperature makes me comfortable and so on.

What do I get? A Google ecosystem that knows me sometimes better than I know myself. Google works best when it learns and integrates. I get asked to download maps for trips Google knows I'm about to take. I have Google assistant throughout my house, in my phone, in my car and it tailor answers and sometimes even the questions that I need answers to. If anything I wish there was further integration, like Google Voice should ring my office phone only when I'm in the office.

Georgia Tech now forces us to use Microsoft Exchange for email. Outlook is not a bad email program but its capabilities, especially for search, does not work as well and think of all that unused knowledge.

I trust Google to keep my information safe, with a random password and 2-factor encryption and even if someone would manage to break in they would find I'm a pretty boring person with an unhealthy obsession of opera (the musical form not the browser).

Doesn't work for everyone and companies should make it easy to keep your info secure. But I say go use your machine learning on me and find ways to make my life easier and more fun, and sure send me some targeted ads as payment. The Internets will find a way to discover you anyway, might as well take advantage. 

Tuesday, January 15, 2019

do we ever only care about the decision problem? I know of only one case of that

(I had been thinking of this for a post then Lance's post on search versus decision inspired me to write up these thoughts.)

When teaching NP-completeness we often say

The problem we really care about is, for example, given a weighted graph and two vertices s and t, find the optimal way to go from s to t while hitting every node. But its cleaner mathematically to look at the decision problem:

{ (G,s,t,C) : there is a Ham Path from s to t that costs \le C }

The search and decision are poly time equivalent, so its fine to just look at the decision. Indeed- if our interest in in lower bounds then clearly if Decision is hard then Find is Hard.

But here are some questions about search vs decision in general, not just with regard to P vs NP.

1) Is there ever a case where the real world actually cares about the decision version? I can think of just one- given a number is it PRIME is used in Crypto. The real world does not need the witness that its prime (or similar).  They  just want a prime.  Any other cases?

2) How far apart can search and decision be? NP-decision and NP-search they are poly equivalent. In other domains can they be very far apart? For example, is FINDING a k-clique or k-ind set in a graph on 2^{2k} vertices require roughly n^k steps (go through all k-sets) or can we do much better? I suspect this is unknown but would be delighted if a commenter tells me otherwise.

Wednesday, January 09, 2019

Search versus Decision

Shockingly I've never done a post on search versus decision, one of the more interesting dualities in complexity. In short: Decision: Is there a needle in the haystack? Search: Find the needle.

In Satisfiability, or any other NP-complete problem, the two problems are essentially equivalent. If you can decided SAT you can find a solution (good homework problem) or even the best solution. Often people mix up the two, where people say finding the shortest Traveling Salesman Tour is NP-complete, usually without getting into too much trouble.

Decision is always at least as easy as search: If you have a solution you know there is one. What about the other direction? We can't actually prove search is hard without separating P and NP, but we have our conjectures.

Sometimes both are easy. We can easily find the maximum weighted matching.

Sometimes decision is easy and search is supposedly hard: Composite Numbers. The search version is factoring.

Sometimes decision is trivial (i.e. they always exist) and search is still hard. Nash Equilibria. Ramsey Graphs.

Often we ask whether search reduces to decision? If you have some oracle (magic black box) that answered decision questions, can you solve the search problem efficiently? SAT has this property, as does Matching (for trivial reasons). Nash Equilibrium and Composite Numbers likely don't.

Graph Isomorphism does, i.e., given an oracle for graph isomorphism you can find the isomorphism (another good homework problem).

There's also an interesting non-adaptive version. Given a SAT formula can you find an assignment with questions to a SAT oracle that all have to be asked at the same time?

Here we get a probable yes. If the formula has one solution you can find it by asking for each bit of the solution. Randomly you can reduce SAT to several formulas, one of which is likely to have a single assignment that is also an assignment of the original formula. With standard hardness assumptions you can eliminate the randomness.

Is the same true for graph isomorphism? I think that's still open.

Sunday, January 06, 2019

When is a kilogram not a kilogram?

A long long time ago the standards for meter's, kilograms, etc was an actual physical object.

Those days are long gone of course. For example, the meter is defined is the length of the path traveled by light in 1/299,792,458 th of a second. Why such an odd number (can fractions be odd?)? Because they retrofitted it to what that the meter is.  Rather than go to France and compare my stick to the one under a glass case I can just measure the speed of light. Oh. That sounds hard!

It matters a bit since the weight of what was the standard kilogram did increase over time, though of course not by much. When did the measurements for stuff STOP being based on physical objects and was all done based on constants of the universe?

The answer surprised me:

On Nov 16, 2018 (yes, you read that light) they decided that by May 20, 2019, the Kilogram will be defined in terms of Plank's constant. I have not been able to find out how they will use Plank, maybe they don't know yet (they do and its known -- see the first comment) .With that, there are no more standards based on physical objects. Read about it here.

Why did it take so long? I honestly don't know and I am tossing that question out to my readers. You can leave serious or funny answers, and best if I can't tell which is which!

Thursday, January 03, 2019

Today is Thirdsday! Enjoy it while you can!

Fellow Blogger James Propp has come up with a new Math holiday:


The day is Jan 3 (1-3 in America, though 3-1 in ... Everywhere else?) but only when Jan 3 is a Thursday.

It is a day where we celebrate the magic of the number 1/3.

0) For other math days to celebrate see here

1/3) James Propp's blog about Thirdsday on Monday Dec 31. Really ???   : here

2/3) Evelyn Lamb blogged about Thirdsday on Tuesday Jan 1. Really ??? : here

3/3) Ben Orlin blogged about Thirsdsday on Wedensday Jan 2. Really??? here

(Added ON Thirdsday: Matt Foreman has a video about Thirdsday: here and a blog post here)

 How come I'm the only one blogged  about Thirdsday on Thursday Jan 3 ??? (Added later- not quite true anymore, Matt Foreman also waited until Thirdsday to post on Thirdsday).
I asked Jim Propp about this. He said that he want to help prepare teachers and other eduators for the excitment of Thirdsday! If they already know the wonders of 1/3 they can prepare and lecture on it! Kudos to him! I assume that Evelyn and Ben are similar! Kudos to them! And Ben blogged ON Thirdsday so Kudos to him!

2) Darling asked me `is it a real day like Pi-Day?'  Is Pi-Day real? Is any Holiday real? All holidays are made up until they are accepted and become real. The distinction between real holidays and  made up holidays  is ... nonexistent.  One can talk of accepted and not-accepted holidays.  How long did Pi-day take to be accepted? This is prob not a well defined question.

3) James Propp's and Evelyn Lamb's  blog has many math properties of 1/3.  One educational property: I think it is the first number that students see that is an infinite decimal. My favorite unbiased use of 1/3: The Cantor Set: Uncountable subset of [0,1] that has measure 0. Really!!! My favorite biased use: its important in Muffin Math. If m>s and you want to divide and distribute m muffins to s students, there is always a way to do this with smallest piece at least 1/3. (Usually you can do better but this is sometimes the best you can do.)

4) When will the next Thirdsday come?

2019: Jan 3 is a Thursday, so YES

2020: Jan 3 is a Friday, so NO

2021: Jan 3 is a Sunday (why no Saturday? Leap year. Great- it will come sooner!)  so NO

2022: Jan 3 is a Monday, so NO

2023: Jan 3 is a Tuesday  so NO

2024: Jan 3 is a Wednesday  so NO

2025: Jan 3 is a Friday. WHAT! Why no Thirdsday?  Darn leap year! So NO.

2026: Jan 3 is a Saturday, so NO

2027: Jan 3 is a Sunday so NO

2028: Jan 3 is a Monday so NO

2029: Jan 3 is a Wedensday (Why no Tuesday? Leap year), so NO

2030: Jan 3 is a Thursday (Leap Year helped!), so YES FINALLY!

(Exercise: find a formula: if 2019 was the first Thirdsday, find the year for TD(i), the ith Thirdsday.)

So enjoy Thirdsday in 2019 when spellcheck still flags it.

In 2030 it will be an accepted holiday and spellcheck will think it's fine.