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. 

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.

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.

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!

Today is Thirdsday! Enjoy it while you can!

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

Thirsdsday!

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.

Complexity Year in Review 2018

Result of the year goes to

Oracle Separation of BQP and PH by Ran Raz and Avishay Tal

which we wrote about in June. This work solves one of the original open questions in quantum complexity using tools from both quantum and classical circuit complexity. How often do we see oracle results with popular articles in Quanta (ignore the hyperbolic title), The Hindu and CACM?

Runner up goes to the solution of the 2-to-2 Games Conjecture by Subhash Khot, Dor Minzer and Muli Safra early in 2018. Boaz Barak gave a nice two post overview.

In last year's review we talked about the magical breakthroughs of machine learning. This year we seemed to have moved beyond the magic to where machine learning has become a thing. We see the immense value of data and continue to struggle with the ethical challenges of collecting and acting on data, dominance of the big tech companies, training all these students who want to gain expertise in the area and trying to understand why ML works as well as it does. 

The big X-factor is China. Will competition with China spur science literacy and funding in the US like the cold war with the Soviets did? Or will isolation with China limit scientific collaboration like the cold war with the Soviets did? 

The big tech surprise was the rise of electric scooters. Georgia Tech has embraced them and it is a quick way to get around campus.

Some of the other questions I asked last year didn't have interesting answers: What will the Internet look like post-net neutrality? (too early to tell) How will the new tax code play out? (too early to tell) Where will Amazon put HQ2? (New York and DC--only surprise was picking two cities) What can quantum computers with 50 qbits accomplish? (still a good question) Will bitcoin move to $300K or 30 cents? (it dropped but still has real value)

Thanks to our guest posters Vijay Vazirani, Samir Khuller and Robert Kleinberg, and anonymous.

We remember Jean Bourgain, George H. W. Bush, Babak Farzad, Stephen Hawking, Ker-I Ko and Stan Lee.

We end the year with craziness, the stock market is going through wild gyrations, we have a partial government shutdown including all of NSF and an uncertain political landscape with different parties leading the two houses of congress. We're still in the midst of a technological revolution and governments around the world try to figure how to regulate it. I find it hard to predict 2019 but it will not be quiet.

Ker-I Ko (1950-2018)

A few weeks ago as Bill and I prepared for our upcoming year in review post, we noted that we hadn't lost any theoretical computer scientists this year, at least none that we were aware of. Unfortunately we didn't make it through all of 2018 unscathed.

Computational complexity theorist Ker-I Ko passed away peacefully from lung failure on December 13. Ker-I Ko spent most of his career at Stonybrook where he had recently retired to take on a professorship at National Chiao Tung University in Taiwan.

I had only had a few brief meetings with Ko but I knew his work quite well. In his best known work, Ko, in a solo paper, created an infinite series of oracles A₁, A₂, … such that relative to A_k, the polynomial-time hierarchy collapses to exactly the kth level, that is Σ_k-1 ≠ Σ_k = Σ_k+1 = PH. Ko wielded the switching lemma like a scalpel, pulling part the k-1st and kth levels while leaving enough room to encode the k+1st level. He actually gives two sets of oracles, one which collapses PH to PSPACE while collapsing the hierarchy to the kth level and one that separates PH from PSPACE. Even his oracle showing P=NP≠PSPACE wasn't trivial and I used it as an example of a hard to settle complexity question.

Ko, with Tim Long and Ding-Zhu Du, showed that if P ≠ UP if and only if there exist two sets that were one-to-one length-increasing polynomial-time reducible to each other but not polynomial-time isomorphic. This paper played a large role in helping us understand the isomorphism conjecture.

Ko, with Pekka Orponen, Uwe Schöning and Osamu Watanabe, used Kolmogorov complexity to measure the complexity of an instance of a problem. The instance complexity of x in a set A is the smallest program that will correctly answer whether x is in A, and will not give an incorrect answer for any other y in A, though it can answer "I don't know" for y ≠ x.

Ko also had several papers on complexity of real-valued functions and wrote several textbooks and manuscripts. A big loss for all of us in the complexity world.

Guest post: Join SIGACT!

This is a guest post by Samir Khuller and Robert Kleinberg.

Dear friends,

As our research community continues to grow and thrive, SIGACT membership has not grown apace. We respectfully urge you to join SIGACT! Membership is very cheap (and does not require ACM membership) – only $15 a year – and by joining you will be lending your support to the many activities that SIGACT undertakes on behalf of the theoretical computer science research community. These include:

• sponsoring STOC and other theory conferences such as SPAA and PODC, as well as co-sponsoring SODA;
• awards such as the Knuth, Gödel, and Kanellakis Prizes, the SIGACT Distinguished Service Award, and the best student paper awards at STOC and SODA;
• supporting the Women in Theory workshop;
• representing the theoretical computer science community to the ACM and beyond.

In addition to these community benefits, membership comes with individual benefits including voting rights in SIGACT elections, reduced rate for membership in EATCS, reduced conference registration rates at SIGACT-sponsored conferences, access to SIGACT News and announcements sent on the SIGACT email list.

SIG membership does not automatically renew when you renew your ACM membership, and we suspect this may be one reason for the decline in SIGACT membership. So the next time you renew your ACM membership, remember to also join SIGACT or renew your SIG membership! Better yet, why wait? If you’re not a SIGACT member, join right now- you can use this link: here

Please do your part to nurture this important resource for our community.

Respectfully,

The SIGACT Executive Committee