Skip to content

ACM Great Results

December 27, 2018


A Puck-ish take on promised technological advances

Wikimedia Commons source

Knecht Ruprecht accompanies Santa Claus in Germany. He brings gifts to good children but lumps of coal to naughty ones. He is regarded more generally as the German counterpart to England’s Robin Goodfellow, aka. Puck. The Simpsons’ dog “Santa’s Little Helper” is named “Knecht Ruprecht” in the show’s German edition.

Today we do a nice-or-naughty riff on technological gifts suggested by yesterday’s ACM TechNews mailing.

The ACM mailings highlight the achievements of the whole field: from quantum to everything else. We thought it might be fun to be a bit puckish ourselves and deliver some “coal” to ACM. The stories can be sometimes a bit much. We hope that all involved are in good spirits and accept the “coal” as a holiday-inspired gift—with some echo of the general discussion about naughty-or-nice effects of tech advances.

Our Versions of the Stories

Here are some that could be reported in the near future. The originals are here.

{\bullet } Real-Time Readouts of Thinking in Faculty.
Mighty News
December 19, 2018
Researchers from a university consortium have developed an open source system delivering fast, precise neural decoding and real-time readouts of where CS faculty think they are. The neural decoding software decrypts hippocampal spatiotemporal patterns detected from tetrode recordings without requiring spike sorting, an error-prone computational process. Implementing this software on a graphical processing unit (GPU) chip demonstrated a 20- to 50-fold upgrade in decoding and analysis speed over conventional multicore central processing unit (CPU) chips. This builds on work previous done on rats as reported by ACM previously. The lab director says that the CS faculty work presented many challenges beyond that required for rats. The applications—she says—are immense. Faculty currently cannot always tell where they are, and the new system could help them get to classes on time.

{\bullet } A Robotic Hand Able To Type At Desktop Keyboard At 20 Words Per Minute.
New Yolk Times
December 19, 2018
Researchers at Can’t-Abridge University have for the first time taught a robotic hand to type on a normal keyboard. The researchers claim that their system can type at rates in excess of 20 words per minute. They say, “this could change the way that computers interact with others.” The system, which now weighs about 500 pounds, could be reduced in size and cost in the future. That the robot sometimes destroys the keys by hitting them too hard continues to be a challenge.

{\bullet } How AI Spotted Every Solar Panel in the U.S.
Pretty Big Solar NewsHour
December 19, 2018
Engineers at the University of St. Anford have located every solar panel in the contiguous U.S. via a network built around a deep learning computer model called Inception. The network completed this task in less than a month, ascertaining that regions with more sun exposure had greater solar panel adoption than areas with less average sunlight. DeepSolar also learned that adoption was higher in locations of increasing average household income. Unbelievable—who would have guessed this?

{\bullet } An Amoeba Just Found an Entirely New Way to Write Articles.
ScienceAlarm
December 21, 2018
Researchers at Knockout University in Japan gave an assistant professorship to a “true slime mold” amoeba, and found as the papers-per-year target increased from four to eight, the single-celled organism only needed a linear amount of more time to generate minimum publishable units. This is part of an ongoing project on using lower-level organisms to do research. The project previously used graduate students. The leader of the multiple institution project said that using amoebae could reduce the costs of writing up research by up to 50%. He also said that the amoeba sometimes made various grammar errors, but that the project was attempting to fix this issue.

{\bullet } A Quantum Computer Just Found an Entirely Old Way to Visit Cities.
ScienceAllure
December 21, 2018
Researchers at TKO University in Japan gave the Traveling Salesman Problem (TPS) to a vast array of noisy astronomical scale quantum (NASQ) processors, and found that as the cities increased from four to eight, the system only needed a linear amount of more time to determine a single reasonable route. This was fresh off its success at factoring numbers higher than 291,311 = 523*557 that it didn’t even know it was factoring. TPS is an optimization problem requiring a computer to look at a list of cities and determine the shortest route in which each city is visited exactly once. The team said their results “may lead to the development of quantum algorithms for problems on as many as ten cities.”

Modified from source

{\bullet} Programming Proteins to Pair Precisely.
C++ News
December 19, 2018
The std::pair construct in C++ is a common annoyance because human programmers frequently forget its implicit presence when iterating over maps or inserting into sets. This necessitates the re-typing of millions of lines of source code per annum. Absent the development of a robotic hand able to type at a desktop keyboard at 20 words per minute, software companies can improve productivity by optimizing the nutritional intake of programmers. Nanosoft has partnered with CodeURIKA to provide protein-rich drinks worldwide, after a study of electronic sweatshops found that proteins minimize both syntactic and semantic bugs better over the long term than sugars and PEDs.

{\bullet} Room for Improvement? New Hotelier Tests an Algorithmic System.
Wallbanger Street Journal
December 19, 2018
The Lite House hotelier is experimenting with an algorithmic pricing system to set different room rates for guests who arrive in self-driving cars. Once customers book for the first time at a standard rate, they fill out a questionnaire of 200 questions to specify how often they will need the car, how frequently they visit the hotel bar, and other details. The hotelier then activates a key to drive the car into an appropriate space. The optimized use of vertical space and savings from not hiring car valets will enable conference participants who are not staying at the hotel to park there at a rate low enough to include in the conference registration fee. A spokesman said, “Most of the big hotel operating companies are not focused on their conference guests,” while Lite House’s algorithmic rate-setting “is next-generation.”

{\bullet} Companies Use VR to Train Employees for Difficult Customers.
ESPN Technology Review
December 20, 2018.
Major corporations like Wallstore, ChippedPot, and Horizon are using virtual reality (VR) to prepare employees for potentially difficult situations on the job. For example, Horizon has more than 1,600 stores in the U.S. whose front-line employees participate in a digital scenario in which a customer asks to use the bathroom. In a “Harry Potter-Style Photos for Muggles” twist, researchers have developed software that can animate the central character in a photograph while leaving the rest of the image untouched. Its skeleton can then be animated to create the sense of movement, solving the problem of pose estimation for a limited set of circumstances in which bathroom requests occur.

{\bullet} New Attack Intercepts Keystrokes Via Digital Watches.
TubeNet
December 19, 2018
A team of researchers from Burning Man University has developed a new side-channel attack that exploits the heat generated by people wearing Orange Digital Watches while working on their PCs. Heat amplifies the watches’ ability to detect keystrokes from both hands. Videos known to generate large amounts of heat include comic videos and videos on carpet cleaning. The attack becomes more adept at guessing correct keys as the user gets hotter, as it amasses more key presses from graphic libraries.


There are some other items, including one particularly chilling, that we chose not to parody.

Open Problems

Will the next year’s advances in AI and other areas of tech be anything like we imagine? Will they bring humanity more gifts than lumps of coal?

Advertisements
5 Comments leave one →
  1. December 28, 2018 1:47 pm

    funny yet jaded/ brutal at the same time. maybe more apropriate for april 1? look we live in an age of scientific wonders and we should have some appreciation/ gratitude for that. but yeah sometimes its “future shock” or “more of the same” or “scientists discovering the obvious” or “so what/ whatever”. there are some great new passionate critiques of technology by modern age philosophers, am seeing them more lately, maybe will try to blog a survey. it looks like technology+science cant really tackle the really big problems it seems, somewhat powerless against it for miscellaneous reasons.

    have you ever heard of the ig noble awards? very similar/ hilarious at times. wonder how many are in computer science these days? https://www.improbable.com/ig/winners/

    here is a link on latest developments in cyberspace survey 2018 and yeah it makes one somewhat similarly dizzy at times. oh it has a bunch of scientific/ psychology studies included also. how about the one about social media (expressly designed by everyone from Zuckerberg down to lift peoples moods)… ending up making people depressed?

    https://vzn1.wordpress.com/2018/12/27/cybersecurity-2018-trends-zeitgeist-top-headlines-links/

  2. December 28, 2018 3:15 pm

    Is this proof complexity proof correct?

    P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? A precise statement of the P versus NP problem was introduced independently by Stephen Cook and Leonid Levin. Since that date, all efforts to find a proof for this problem have failed. Given a positive integer x and a collection S of positive integers, MAXIMUM is the problem of deciding whether x is the maximum of S. We prove this problem is complete for P. Another problem is SUCCINCT-MAXIMUM. SUCCINCT-MAXIMUM contains the instances of MAXIMUM that can be represented by an exponentially more succinct way. We show this succinct version of MAXIMUM must not be in P. Under the assumption of P = NP, we prove the membership of SUCCINCT-MAXIMUM in P is also hold. In this way, we demonstrate the complexity class P is not equal to NP by the reduction ad absurdum rule. Another major complexity classes are LOGSPACE and NLOGSPACE. Whether LOGSPACE = NLOGSPACE is another fundamental question that it is as important as it is unresolved. We show the problem MAXIMUM can be solved in logarithmic space. Consequently, we demonstrate the complexity class LOGSPACE is equal to P and thus, LOGSPACE is equal to NLOGSPACE.

    https://www.academia.edu/38039040/LOGSPACE_vs_NLOGSPACE_and_P_vs_NP

  3. December 28, 2018 3:18 pm

    You could discussed here:

    Thanks

  4. January 2, 2019 10:12 am

    Best wishes for this new year.

    Here I comment a mistake that I committed in 2015 which is now fixed in this new paper

    https://www.academia.edu/38039040/LOGSPACE_vs_NLOGSPACE_and_P_vs_NP

    that I submitted to Academia preprint site on December 25th of 2018…

    Here is the story:

    In the year 2015, I submitted a paper to a journal of the ACM.

    In that paper, I proposed a succinct version of a problem in P which is in coNP.

    Unfortunately, this paper was rejected because I assumed that a succinct version of a problem in P is out of P, but they told we can only assume that on the basis of a P-complete problem.

    Here I send you the email of the decision:

    “Ref.: Ms. No. TOCT-D-15-00033On exponentially more succinct instances of a language in PACM Transactions on Computation Theory

    Dear Mr. Vega,

    Reviewers’ comments on your work have now been received. You will see that they are advising against publication of your work. Therefore I must reject it.

    Note that, according to the ToCT policy of which I know you are aware, you may not submit another paper to ToCT, JACM, or ACM Transactions on Algorithms that purports to resolve the P versus NP question or related long-standing questions in complexity theory, until Nov. 17, 2017.

    For your guidance, I append the reviewers’ comments below.

    Thank you for giving us the opportunity to consider your work.

    Yours sincerely

    Eric AllenderEditor-in-ChiefACM Transactions on Computation Theory

    Reviewers’ comments:

    This is a paper that claims to prove that P is not equal to NP.

    Like all previous such attempts, this proof also is incomplete, and I do not see how it can be repaired.

    The main error occurs on page 3, where the language SUCCINCT-ALL-3HALT is introduced, and it is claimed that the language is not in P. This language is essentially this:{(M,w) such that, for all strings x that lexicographically precede w, it holds that M accepts x in time at most |x|^3}.

    The author is correct in saying that this is (in essence) a succinct version of a problem in P, but he incorrectly asserts that therefore the language is not in P. A succinct version of a problem that is *complete* for P (under restrictive-enough reducibilities) indeed can be shown not to lie in, because it will be complete for EXP. However, working with a problem that is *complete* for P would mean that it would be difficult (or perhaps impossible) to show that the succinct version is in coNP, which is the other property that the author requires. (It does in fact hold that SUCCINCT-ALL-3HALT is in coNP.)

    Certainly there are instances of problems in P whose succinct versions are also in P. Thus the 3-line proof of Theorem 3.3 is completely inadequate, and I see no way for this proof to be repaired. The paper should be rejected.”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s