Scaling Research Training

There is a lot of need in the Industry for engineers who know the art (edited to craft)of research (pursue and find the right literature and algorithms, understand prior art, adopt and modify for a specific context with domain awareness, interpret results,  dive deeper into the unique insights), or researchers who can apply this art with engineering finesse. I wondered yesterday in a meeting if our technological lessons from COVID times have helped us identify a way to train many more in the ways of research, more than what we produce as PhDs in universities (the MS programs seem to train advanced engineers more than padawan researchers).

Postdoctoral openings at Amazon

Amazon Advertising opens applications for early career scientists. The new program, which offers full-time two-year positions, is aimed at recent PhD graduates who want to innovate, publish, and have their work impact millions of customers. The application deadline is May 14.

John Conway

I managed to join a zoom meeting yesterday to honor John Conway. Peter Winkler paid tribute with a story about the brick-stacking puzzle (was interesting to hear "skintle" in context of puzzles). Roger Penrose paid tribute with tilings but also an old classic,  Morley's Trisector Theorem. Others like Don Knuth appeared in the pre-meeting chat room, but I could not stay for the entire 3 hrs+ homage. Thanks to everyone!  JHC, RIP.  I was reminded that we are the math, friends and puzzles we leave behind.

Friends Ada and Phillip have created a short hardware tribute to JHC, video embedded below. Ada and Phillip, thanks for repurposing your NYC manufacturing line to produce face shields and PPEs.  Loved the blog on the scientist who discovered the first coronavirus and the handsanitizer made in Detroit.

Amazon Scholars Program

Amazon has an interesting way to have scholars  (professors, experts) work flexibly with Amazon. Check with the program here. Obviously online advertising is of great interest too, including ML/AI, game theory, optimization, etc. 

Amazon Research Awards

Amazon has a program for research awards. Check out the process. The focus areas include online advertising for the first time and this should be interesting to researchers in mechanism design, optimization, game theory and multiagent systems, among other things. There is also a lot of interest in machine learning methods in general, and theory in the context of these focus areas. The deadline is Sept 15, 2018. Looking forward to submissions. 

Kearns in News

Morgan Stanley hires Michael Kearns as their AI expert and here is their announcement.

As an aside, financial institutions are/have been  dipping into the ML/AI pool. I am curious to see what the battle of the GAN armies from different finance players (for modeling risks, strategies, trading) produces as the eventual market. 

Optimization notes

• Looking through lecture notes on convex optimization by Nisheeth Vishnoi. 
• Celebration of Vijay Vazirani's 60th birthday, schedule looks great.
• The winners of the 2018 ACM SIGecom Test of Time Award are: 
• Varian, Hal R. "Position auctions." international Journal of industrial Organization 25.6 (2007): 1163-1178. 
• Edelman, Benjamin, Michael Ostrovsky, and Michael Schwarz. "Internet advertising and the generalized second-price auction: Selling billions of dollars worth of keywords." American economic review 97.1 (2007): 242-259. 
• Aggarwal, Gagan, Ashish Goel, and Rajeev Motwani. "Truthful auctions for pricing search keywords." Proceedings of the 7th ACM conference on Electronic commerce. ACM, 2006.

Theory of New CS

I am helping NSF CISE by serving on the Advisory Committee which has some great folks. As you break for holidays and spend time with friends, family and your feral self during the break, I hope you get to think about how NSF can help us develop the theory of CS further.

• All of CS has for decades believed in algorithmic intelligence, formulating optimization problems, designing optimal, heuristic solutions, studying  their performance via math or experiments, exploring what can not be done via system building or proving lower bounds and hardness, etc. Now the focus is on using artificial intelligence across systems and sciences. So we need to develop the foundations for such a thinking. 
• CS Systems are converging, with hardware and software used a lot more interchangeably. There are programmable network switches, popular gadgets from phones to Echo that are not just computers, and computing resources that are increasingly concentrated in data centers, etc. So, different systems areas find themselves treading into each others' arena organically. 

That is the world of new CS. Finally, folks high up typically think of "missions" (land on moon, self-driving cars, robotic warehouses, virtual assistants), while researchers think of areas, problems, techniques/methods. Does it help when CS disciplines, theory included, think of missions?

Please email me with thoughts. 

Positions in eg. Data Intelligence/UBC/CA

UBC CS has positions: Postdoc in data understanding/intelligence with Prof. Rachel Pottinger (Applications or questions should be sent via email to [email protected]), 3 assistant professors in any area (http://bit.ly/2mNcNdR ) and a tenure-track teaching position (http://bit.ly/2zToVPs ). Vancouver is beautiful, the faculty is strong, and Rachel is an excellent mentor. 

Amazon Docs, Theory Research kindles some fire.

I read through whitepapers to keep me updated on how companies see themselves and their products, in a technical arena.

I was checking out AWS whitepapers, where among docs that limn the core strategic view of Amazon Web Services and their products, is a research paper, theory research on random cut forest, anomaly detection, and streaming algorithms!

Here is the paper by Nina, Sudipto and others, remarkably nestled within core whitepapers for the entire AWS universe. This research must have kindled some fire, deep within Amazon.  

Planar Matching in NC

There are problems that I carry in my bones, even if I am not actively working on them. Every once in a while you are working on something that reminds you of these problems and try to renew the attack, other times they simply simmer in your psyche.

One such problem is perfect matching in NC. I teach the Mulmuley, Vazirani, Vazirani result that perfect matching is in RNC, and even recently went back to the open problem of producing a NC solution when I was looking at some MapReduce variants.

Vijay and Nina have an arXiv paper showing planar graph perfect matching is in NC and I am looking forward to reading it. 

Sunsetting ICORE

When friends remember me, I am happy to go to distant lands. I managed to travel to Israel to give a talk at the ICORE day.  I-CORE is Israeli Center for Research Excellence program, and the day marked the end of the funding period. Israel has great talent, so any money the govt puts in finds great use; in  this case, it seems to have filled a severe need, providing much-needed support for postdocs.

I talked about Heavy Hitters (HHs), a bit of the classical Count-Min stuff but also much less sculpted stuff like high dimensional HHs, H-influence and other topics. I find HHs interesting because it is not top k, it is a distinct concept, and a concept that represents what is (often the only thing) possible within resource constraints. Robi asked a great question, if this can be formalized.

There were many good talks. I managed to catch a bit of the talks by Rotem Oshman, Michael Shapira, Shahar Dobzinski, and others. I also managed to catch Yuval Ishai and Eylon Yagev talk secure multiparty computing and complexity theory resp in Hebrew. Finally, Bernard Haeupler gave an excellent  talk on using shortcuts to break natural bottlenecks with message passing algorithms. This talk introduced the audience to principled theory methods (was happy to see Leighton-Maggs-Rao O(Congestion+Dilation) result reenter the psyche) to attack worst case performance of message passing algorithms.

ps: Thanks to Moni for mentioning Mossel's paradox with dice/6 over dinner, he said there was an elegant solution, and my neurons stayed awake figuring it out.

AI + Marketing Workshop

We are running a workshop, trying to bring together the AI and Marketing Sciences communities.  AI community of course includes algorithms, optimization and game theory; Marketing Sciences of course includes online advertising, auctions and other topics. But the goal is to bring in more than these topics, and try to forge a common venue, getting each of these (sub)communities to stretch a bit to meet others.

The workshop is collocated with AAAI 2018, and the deadline is Oct 29, 2017.

 Organizers

• Hung Bui (Adobe Research) 
• Pradeep Chintagunta (University of Chicago)
• S Muthukrishnan (Rutgers University) 
• Tuomas Sandholm (CMU)
• Atanu Sinha (Adobe Research and Emeritus, University of Colorado)
• Georgios Theocharous (Adobe Research)

Data Science and Social Good

Bloomberg folks organize a day of activities on Data for Good, Sept 24, 2017, FYI. 

(Sublinear) Time Meets Space

Maybe this post should be called "property testing meets streaming". For more than a decade now we have managed to put together meetings that had both property testing folks (with methods running in time sublinear in input size) and streaming folks (with methods using space sublinear in input size), and in many of these meetings, researchers debate the nuances and results of these communities (the usual: algorithms vs complexity, for each vs for all, yaada yaada yaada). Obviously each community has learned from the other, but there were not many results that formally related the underlying concerns.

Recently, Christian, Pan, Morteza and I showed: ".. for bounded degree graphs, any property that is constant-query testable in the adjacency list model can be tested with constant space in a single-pass in random order streams." This is a human-sized hop towards establishing formal connections.  Hope more hops and leaps will ensue. 

Heavy Hitters Continued

Recently I revisited the classical heavy hitters problem on streams (I think I can call it "classical", I remember the meeting where we chose to call overwhelmingly large items as heavy hitters, in the shadow of the baseball scandals in early 2000's)  but now looked at the high dimensional version, where each stream item is a d dimensional vector.  

There is a d^2 space bound that is inherent, and we manage to circumvent it, by using graphical model (in our case, Naive Bayes) on the dimensions. This is in general a fruitful direction, I think, using a dependency model on dimensions to half-circle around lower bounds we get with high dimensional analyses.  Our paper is in arXiv, joint work with Brano and Hoa. 

This work was motivated by collaboration with Adobe that needs to analyze high  dimensional web/ad analytics data. That is covered in the Ad Exchanger article, as part of the coverage of the university funding program that Anil Kamath spearheads at Adobe (and does a superb job of eliciting very specific projects but drawn from a wide set of areas).

Artificially Intelligent Assistants, KDD Panel. What happened.

Andrew Tomkins and I cohosted the KDD 2017 panel on AI Assistants.  The panelists were Usama Fayyad, Larry Heck, Deepak Agarwal and Bing Liu, representing the spectrum from entreprenueral to academic including corporate research, in many cases individually.

• For AI assistant technology today, talk about either a current success story, or a shortcoming in the market.   (Success story for "head", goal oriented bot: Siri, Alexa, Cortana, Google Assistant, DuerOS (Baidu), or Wechat bot Xiaoice  for chit-chat) Need:  The need by a broad set of companies for AI assistants is a given/assumed → broad engagement/interest by many companies to build/leverage AI assistant technology. 
• "Help me plan a trip” versus “Connect me to my travel agent.”  Does user talk with one “butler” agent versus many specialized agents?  Follow-on:  What critical standards are required to enable assistants to operate effectively across multiple sensory domains?  How are we doing at developing these standards?
• What implications will artificially intelligent assistants have for teens?  How about in the workplace?  Follow-on:  what are the expectations for task-focused versus chit-chat assistants?
• How should a user be able to empower AI assistants to operate on the user’s behalf?
1. “I’m sorry, Joe’s not available right now.”
2. “I booked the show you wanted.  It’s 7:30 tonight.”
3. “I found a great date for you this Saturday night.  Dress nice.”
4. BTW, I bought you a house.
•  What are research bottlenecks? (Dialogue understanding and large scale availability of suitable data, information elicitation methods, classical AI open issues like common sense reasoning, etc.) 
• What role should assistants take in your life?
1. Servant: does as you say
2. Friend: emotional support
3. Mentor/therapist: provides guidance
4. Psychological role: assistant as id, ego, super-ego
5. Deity: superhuman being with power over your fortunes, lead a way even if we dont see the rationale or even punish.