Monday, September 10, 2018

Lenore Blum interview

I've just read this, and do not have any specific comments, but I thought this interview with Lenore Blum on her recently announced resignation from CMU would be something of interest to the larger community.  (Thanks to Margo Seltzer for forwarding it to me.) 

Monday, July 23, 2018

Symposium on Simplicity in Algorithms, Submission Server

A reminder that the deadline for SOSA 2019 is August 16.  The submission server is live and running (and we already have some submissions!).  The easychair link is https://easychair.org/conferences/?conf=sosa2019 , and general information can be found at https://simplicityinalgorithms.com/ .


Friday, June 22, 2018

STOC Lunch Sign-ups, and Reminder


Just a reminder that next week is the 50th STOC in Los Angeles!  You can still come and register on site, so please come -- the program is STOC-full of good stuff.  Especially all you Californians -- no excuse not to be there.

An innovation introduced at last year's STOC was the junior/senior lunch meet-up.  Senior people sign up to meet with junior people over lunch at a day of their choosing, and then (three) junior people (undergrad/grad/postdoc) can sign up to go to lunch with the senior person.  The goal is to increase chances for junior people to get to network with more senior people, something that we hard heard was lacking previously.  (Everyone buys their own lunch.)  You can find the on-line sign-up sheet here.  Please go on and sign up as soon as you can!


Tuesday, May 29, 2018

Sympoisum on Simplicity in Algorithms, 2019

Jeremy Fineman and I are co-chairing the 2019 Symposium on Simplicity in Algorithms, the second year of this new endeavor.  It's nicely co-located with SODA, and the submission deadline is August 16.

This symposium arose of an apparent need to have a home for results that were focused on simplicity -- specifically, a place where you could introduce a simpler algorithm or a simpler analysis of an existing algorithm for a problem.  I think we're still in the stage for testing that need, but it would be nice to make this a permanent addition to our conferences, and like ALENEX and ANALCO, it's a great fit as a co-located SODA event.  

Please spread the word, and submit your papers -- we look forward to reading them.  More call information is available here.  

STOC 2018, Early Reg Deadline

Just a reminder that the early registration for STOC 2018 is June 1.  Besides wanting that early registration discount price, you really want to also make your hotel reservation -- the conference hotel special rate is (only) available through June 1.  I was looking this morning, and as the web page warns, hotels in LA that week are going to be expensive -- there's an award show in town that will be filling the hotels.

So please register today.  (Or tomorrow.  But by Thursday for sure.)


Monday, May 07, 2018

SIGACT-Related Stuff

Some SIGACT related-stuff of import:

First, there's an election going on!!!  If you're an ACM/SIGACT member, you've probably gotten an e-mail about this, and it's probably gone into some folder that you probably never look at.  Please check your e-mail for a subject like "ACM SIG 2018 Election".  I believe the deadline is the first week or June or so.  Please vote!  (Bios and related materials for people running can be found here.)

Second, the Knuth Prize call is out.  (It should be on the SIGACT web page shortly, but the main info is cut and pasted below.)  July 1 deadline is perhaps the most important part.

Third, keep in mind the early registration/hotel deadline for STOC (which runs June 25-29 in Los Angeles) is coming up, June 1.  It will be another "theory fest", so expect some great keynote speakers and invited talks, workshops and tutorials, poster sessions, and other great events.  If you went to STOC last year in Montreal, you know the "theory fest" is a different creature than previous STOCs, and that you don't want to miss it.  Also, it's the 50th STOC, so there will be some events specifically for that.  STOC is the theory conference you really want to go to -- sign up and make sure to get the early registration fee.

Knuth info below:


Nomination Procedure. Anyone in the Theoretical Computer Science com-
munity may nominate a candidate. To do so, please send nominations to
 knuth.prize.2018@gmail.com by  July 1st, 2018. The nomination should
state the nominee’s name, summarize his or her contributions in one or two
pages, provide a CV for the nominee or a pointer to the nominees webpage, and
give telephone, postal, and email contact information for the nominator. Any
supporting letters from other members of the community (up to a limit of 5)
should be included in the package that the nominator sends to the Commit-
tee chair. Supporting letters should contain substantial information not in the
nomination. Others may endorse the nomination simply by adding their names
to the nomination letter. If you have nominated a candidate in past years, you
can re-nominate the candidate by sending a message to that effect to the above
address. (You may revise the nominating materials if you so desire).

 Criteria for Selection. The winner will be selected by a Prize Committee

consisting of six people appointed by the SIGACT and TCMF Chairs, see below
for the composition of the committee. All nominations will be considered by
the Committee, including those submitted in previous years, but nomination is
not a requirement to receive the Prize. Note that the Knuth prize is awarded
to a single individual each year. Nominations of groups of researchers will not
be considered.

In selecting the Knuth-Prize winner, the Committee will pay particular at-
tention to a sustained record of high-impact, seminal contributions to the foun-
dations of computer science. The selection may also be based partly on ed-
ucational accomplishments and contributions such as fundamental textbooks
and high-quality students. The award is not given for service to the theoretical
computer science community, but service might be included in the citation for
 a winner if appropriate. The current prize committee consists of Avrim Blum
(TTIC), Allan Borodin (U. Toronto), Alan Frieze (CMU), Shafi Goldwasser (UC
Berkeley), Noam Nisan (Hebrew U.), and Shang-Hua Teng (USC, chair).

Sunday, April 15, 2018

New Papers/Code for MIC and MINE

Several years ago, I worked on a project where the goal was to try to come up with an "equitable" version of a measure of dependence;  the idea was you could take a large multi-dimensional data set, score the dependence for each pair of variables, rank the pairs by their score, and then look at the top-scoring paris to try to determine the most interesting relationship to follow up on in further work.  We were motivated by the need for data exploration tools for multi-dimensional data sets.

After a large number of years, we've updated the site http://www.exploredata.net/ , with some (finally) recently published papers, and new versions of the code that are faster, more accurate, and can do additional tasks (what we call TIC as well as MIC).  Our technical information subpage has links to papers, including the relatively recent papers in JMLR and the Annals of Applied Statistics.  Our MINE-Application page contains links to our new version of the code, as well as links to other versions (such as minepy, a library that has APIs in python and Matlab). 

The incentive for all this was, in part, one of the co-authors, Yakir Reshef, finishing up his PhD thesis.  Congratulations Yakir!


Wednesday, April 11, 2018

Sublinear Algorithms Workshop

I was asked to post to announce the workshop/bootcamp on Sublinear Algorithms, June 10-13 at MIT.  I plan to be there and possibly talk about some new work. 

From the web page (which you should go to to register, if you plan to attend!):

Synopsis

As big data is getting bigger, there is a need for analyzing data with sublinear constraints -- that is, for algorithms which require only sublinear time, space, measurements and/or samples. The goal of this workshop is to bring together experts in various areas of Computer Science, Electrical Engineering, Statistics and Mathematics to discuss recent work and exciting new challenges. It is hoped that the multidisciplinary nature of the workshop will highlight common goals and themes, as well as to facilitate an interchange of technical ideas that may be of use more widely than previously thought. The workshop will be preceded by a one day bootcamp on June 10, with the goal of presenting the basic techniques, definitions and goals in several of the communities.

Monday, March 26, 2018

An Ad-Hoc Committee on Sexual Harassment and Related Issues


The following is from Yuval Rabani, regarding a joint initiative we are moving forward with to establish policies, procedures, and institutions to deal with harassment and related ethical issues.  You may see the post on other theory-related blogs as well. 

------------

Recently, many theoreticians have become aware of issues, stories, and rumors concerning sexual harassment within our community, in other CS communities, and more broadly in science.

A number of initiatives, most notably the mushrooming codes of conduct at theory conferences, are already being put into practice.

In consultation among some of the main organizations running theory venues (IEEE TCMF/FOCS, ACM SIGACT/STOC+JACM, EATCS/ICALP, SIAM/SODA+SICOMP) we’ve decided to appoint a joint committee to discuss and propose coordinated policies, procedures, and institutions to deal with harassment and related ethical issues which cut across organizational boundaries. Sandy Irani will chair the committee. Its charter is stated as follows:

"We are setting an ad-hoc committee to draft a proposal for joint ToC measures to combat discrimination, harassment, bullying, and retaliation, and all matters of ethics that might relate to that. Proposed measures may include, but are not restricted to, coordinating policies and guidelines, and setting community-wide institutions for reporting and oversight. The primary goal should be a determination to deter and root out such behavior in the theory community. The issues of false reporting and due process should be taken into account. The committee is expected to conduct the necessary research on existing practices. The committee will submit a report to the appointing organizations by September 30, 2018.”

If you wish an organization be included in the loop, please contact me. If you wish to convey to the committee ideas and thoughts, please contact Sandy or other members as they’ll be announced.

In the meantime, while we are waiting for the committee’s more thoughtful suggestions, here are a couple of simple and potentially effective steps, off the top of my head:

1. If you are harassing someone, please stop.
2. If you are not harassing anyone, please don’t start.

I will gladly contribute to a lively open discussion and react to comments, especially if they occasionally reach my awareness by relaying their existence to my email feed. (Regrettably, I don’t spend all my waking hours monitoring theory blogs.)

Thursday, March 22, 2018

Swedish Summer School

I was asked to post the following notice for the upcoming Swedish Summer School for (theoretical) computer scientists.  I gave some lectures for it a couple of summers back, and really enjoyed it.  Maybe the students did also. 

A warning that Djuronaset is not in the city of Stockholm, but a bit over an hour away from downtown Stockholm by bus.  While not in the city, it's a beautiful area for walks, and the facilities are very nice.  (In particular, they have wonderful saunas in the hotel that should be used daily.)

----------------------------------

The 5th Swedish Summer School in Computer Science (http://s3cs.eecs.kth.se/) will be held August 5-11, 2018, in the beautiful Stockholm archipelago at Djuronaset (http://djuronaset.com/en/). The school runs for a full week Monday-Friday in early August when Sweden is at its loveliest, with arrival on Sunday evening and departure Saturdaymorning.

We will celebrate our 5th anniversary by going significantly out of our comfort zone and learn about quantum computation. Ronald de Wolf (https://homepages.cwi.nl/~rdewolf/) will give a series of lectures accessible to people who do not know quantum from before. The idea is that this will help all those of us who routinely skip intimidating quantum talks at workshops and conference to overcome our deepest fears and learn enough so that during the next conference we can confidently go to the quantum sessions and actually understand some of what is going on (and maybe even ask a smart question or two).

Another reason for being scared about quantum is that the crypto systems we know and love might no longer be safe. But fear not: Oded Regev (https://cims.nyu.edu/~regev/) will give lectures on lattices and cryptography, explaining, among other things, how to survive in a post-quantum world. Other exciting topics that Oded will touch upon are the Learning with errors (LWE) problem and fully homomorphic encryption.

The summer school is primarily intended for PhD students, but postdocs and bright MSc students are also warmly welcome (and also faculty, subject to availability of slots).

The application deadline is April 20, 2018. Please see http://s3cs.eecs.kth.se/ for more information including instructions for how to apply. Any questions can be directed to s3cs-2018@kth.se.