The Curious Case of Algorithms

I finished reading “The Golden Ticket: P, NP and The Search for The Impossible” some time back. It is a very nice book that introduces one to complexity theory. Essentially, it describes, without too much of Mathematics, what kinds of problems can be solved and what other kinds will take forever to solve. However, if these – the forever to solve ones– were to get solved one day, what would be the impact. P  refers to the problems that can be solved quickly using computers to get the best solution. On the other hand NP refers to problems whose best solution cannot be found quickly using computers. I have deliberately simplified things for your understanding. This field is vastly complex!

The word “quickly” is used here with reference to a time span which is acceptable to the seeker of the solution. It could be a few seconds, or a few weeks.  Going by the nature of humans, any solution (best or otherwise) that might be delivered in months or years will probably be unacceptable. The search of any solution is accomplished using algorithms. It is these algorithms that can either give us a solution “quickly” or might take ages to finish their task. It is believed that if we could find algorithms that could solve any problem in the class of NP problems, we could solve many challenges facing us. These problems can be found in varied fields like biology, cancer research, mathematics, computer science, economics etc. However, some of the modern day systems which we feel very secure and safe about will lose these strengths if an NP problem is solved. This is because they rely on the fact that NP problems are extremely hard to solve quickly. For instance, your secure online bank transaction won’t be secure anymore. The public-key cryptography, on which it relies, would be broken by then.

Another technologically interesting aspect of algorithms is their ability to provide information based on someone’s taste in color, clothes, books, music etc. In fact, it is this type of algorithms which is used by eBay, Amazon etc. to recommend to users items for purchase. They track their actions: which items they click on, which items they buy etc. to create an “algorithmic profile” of users. While all this sounds interesting and potentially time saving for someone who knows what to buy, this also has a negative side effect. As a regular user of such platforms, you end up getting information that is tailored to your existing taste. Therefore, you cannot easily get information that is not relevant to your taste. Effectively, your ability to explore ( if you are also someone who likes to explore) becomes limited. Of course there are ways to overcome this, simplest of them being not to sign in when performing a search!! You can argue that many prefer automatic sign-ins to save time and the need to remember passwords. True, but then you have to decide whether you want to work/live like a frog in a well or like a whale exploring an ocean! 🙂

Technology Innovation and Unemployment

Automation has increased productivity in many areas. If you look at the assembly line or shop floor of a car manufacturer, you will see automation in its full might. Though you will still find a certain number of workers, their number is far less compared to pre-automation days. You may have also come across call center staff who deal with queries related to insurance, bank related tasks etc. Most of these queries are routine in nature and it is the same kind of information that the staff has to provide to the callers. There is recent news that companies like IPsoft are providing artificial intelligence based virtual call center staff to handle such queries. This is expected to reduce the number of people required in BPOs and call centers. 

An aprocryphal tale is about a conversation between Henry Ford II and Walter Reuther. The former was the head of Ford Motor Company while the latter controlled its union. When Ford asked Reuther how he would make robots pay union dues, Reuther asked in return if Ford could make his robots buy cars. Ford got the point that any increase in productivity has to be met with an increase in the number of consumers. Ford raised the salary of his staff so that they could afford to buy cars. 

Do you think that an increasing rate of technological innovation can lead to rise in unemployment? If you believe in this, you probably believe in Luddite Fallacy. I would rather suggest to be open to debates on this issue. This issue is far from resolved and new insights keep coming now and then. Two opposing views on this issue can be found here and here published in The Economist and Forbes respectively.

Given the fact that many engineers work on systems which are meant to increase productivity, provide better services, it is only relevant to have a look at an aspect of economics and social change that they are seldom concerned with. It is not so much about questioning what they do rather it is more about understanding the mysterious ways in which the world moves!

On Diffusion of Innovations

Diffusion of Innovations is a remarkable book by Everett M. Rogers. It is also a field of study and research where questions related to the diffusion of innovations through different groups of people and cultures are studied. This theory seeks to explain how innovations spread, how they are adopted or rejected, their social impact and the rate at which these processes occur over a period of time. This book has plenty of examples of innovations that diffused and those that did not. Notable examples include the idea of water boiling that the public health service in Peru wanted to promote in a Peruvian village and failed in doing so; non-diffusion of the Dvorak keyboard; the relatively successful STOP AIDS campaign in San Francisco in the mid-1980s etc. Note that the use of the term innovation  is not restricted to technological innovations only. According to Rogers, “An  innovation is an idea, practice, or object that is perceived as new by an individual or other unit of adoption“.

Technologists and engineers generally think that a new idea will sell itself, that advantageous innovations will be quickly adopted. However, this is seldom the case and the adoption, in general, is slow. This is a fact that is of relevance to many start ups. There are social and cultural aspects of innovation that have a big influence on its adoption. Influencing the adopters involves not only relevant marketing but also addressing social, cultural and economic issues. Of course the range of issues to be addressed depends on the innovation that we are trying to sell or promote.

It would come as a surprise to many that Everett M. Rogers was not from business or engineering background. He was a scholar in  communications and sociology!

Complementary to Google Search

When we look for information, almost all  of us invariably turn to Google. There is no doubt that Google and its services, especially its search engine, have helped many of us who look for both new and old pieces of information often. However, is it always the best in terms of returning results that are relevant to the search query? Not necessarily. By relevant, I mean the intention of the user who typed in the search query.  Given the fact that the Google page rank algorithm, among other things, assesses the importance of a page/resource based on the number of pages/resources linking to it and their importance as well, the search result tends to tilt in favor of  those resource which most people are talking about. Therefore the search result can include Wikipedia references, journal and magazine articles, Youtube videos etc. This means that there may not be a uniformly decreasing order of depth of information available in the search results. It may also mean that the quality and expanse of information available in the search results could vary widely. For instance, a news report that shows up higher on the list of search results could be discussing the outbreak of a particular disease and its economic and social impacts. It may not be discussing the medical science behind the disease itself. Of course one can try combinations of phrases as well as Google custom search to narrow down the results. This also means that if you are searching for something that is discussed rarely, you will have to sift through a lot of results. However, there is another way of looking for targeted information: use of field specific search engines. For example,  FindZebra  is a search engine for rare/orphan diseases. This is currently a research project at Technical University of Denmark  and it seeks to help doctors looking for information on such diseases for the purpose of medical diagnosis (an example of very targeted information). It indexes only the most relevant databases for this purpose.  Its comparison with Google search and Google custom search can be found here. Archives, like this one,  in different fields also serve the same purpose. It  will be better to see the two search approaches as complimentary to each other. While field specific search engines/archives can be very precise, Google search can provide a wider set of results where different perspectives and analyses may emanate on the same subject but from  people with different backgrounds.

How much and what do you read as a researcher?

What do you read as a researcher? Most of us read only that which is relevant (or we think is relevant) to our research. But is that all that is should be read? I know that many of us do read novels of different kinds of which fiction is more common.

However, as far as reading for research is concerned, most of us read within our specific domain and especially focusing on those works that are closely related to our own. We browse through conference proceedings and journals a lot. Some of us venture into reading patents and online newsletters published like EE Times  etc. Nevertheless we tend to stick to a rather narrow range of topics. We measure the utility of reading something for research against the value that it might bring, in our opinion, to our research. While this is not at all a bad way of doing research, we run the risk of training ourselves to read, think and argue about only a very narrow set of topics even within our own broader research discipline. It is a byproduct that has its negative consequences. It becomes difficult to think beyond what we are most comfortable with and it makes an expert in a very narrow field. We run the risk of not being able to relate our work with the bigger picture and processes. We run the risk of not being able to think at the system level or looking at the same thing from a different perspective. For instance, a mobile phone is a device that has both software and hardware. A software guy will describe it from software perspective while the hardware guy from hardware. Someone who can understand both, even if not every detail, can help merge the two perspectives which is very important for product design!

Oscar Wilde has said, “It is what you read when you don’t have to that determines what you will be when you can’t help it“. It applies not only to life but also to research. Reading about human factors, user interfaces, intellectual property, regulatory practices etc. helps us in seeing same things from different perspectives. It is a great way to exercise our brains.

At the same time,if you are more adventurous , reading about topics in sociology, psychology, economics, politics etc. helps you develop critical thinking abilities borrowed from different domains. An example is here. And if you can see through all of this, you might even be able to solve a problem in your domain by reading about something exciting in another domain.

Value of Scientific Work

We, researchers and non-researchers alike, often come across this question: what is the value of scientific work? Is it about publishing papers that expound upon novel ideas? Is it about work that can be commercialized? Is theoretical scientific work more valuable than practical scientific work? Are hands on abilities more valuable than critical thinking? These are perplexing questions with no straight forward answer. Probably, the best way to think of these is to understand that there is space in this world for all. Different approaches have their pros and cons. I think that it is even better to answer them in some context rather than after untying them from any context.

I have seen graduate students, especially PhD students, grappling with the value of their work in the beginning and then towards the end of their PhD. Many find their work of not much value compared to work that translates into something tangible, something that you can touch or see or hear; something that people can use; something that makes them feel that they have created something that did not exist.

Nevertheless, the use of an idea and the idea itself are two different things. They each deserve their own attention. It is also possible that a use case for an idea may not be realized in the immediate future once the idea was formulated. It may take time for the use case to appear and it may not be the same person who developed the idea. For instance, the inventor of laser would have probably never imagined that one day it would be used in laser pointers which we often use during presentations.

I think that when we question ourselves in this way, we need to go back in time and see what the savants of the field have said about these. One great piece is titled “The Value of Science” by Richard P.  Feynman, Physics Nobel Laureate (1965) and both a researcher and a teacher par excellence.  It is so rare to find an excellent researcher who is also an excellent teacher these days. The following paragraph from his public speech will probably be of immense interest to young researchers:

“I would now like to turn to a third value that science has.  It is a little less direct, but not much.  The scientist has a lot of experience with ignorance and doubt and uncertainty, and this experience is of very great importance, I think. …………….  We have found it of paramount importance that in order to progress we must recognize our ignorance and leave room for doubt.  Scientific knowledge is a body of statements of varying degrees of certainty – some most unsure, some nearly sure, but none absolutely certain.”

For a funny and amusing reflection on the different kinds of researchers today ;), see this by Daniel Lemire, a  computer scientist with a big following.

The Internet of Things

When I first attended a presentation on “The Internet of Things”, I was not very excited. It turned out to be nothing more than a glorified description of sensor networks. Though this phrase was first used in 1999 as reported in an article in RFID journal, it has been interpreted in many different ways by different people. Trying to find a way through that maze of descriptions is really difficult. However, after reading a lot about it and based on my own understanding of embedded systems, sensor networks and systems engineering, I would like to share what it means for a non-technical audience. I find it best to explain through examples. Take the case of a smart home. You can control the appliances in your home while driving your car as there is a communication network that links you up with them while you are driving. Your smartphone connects you to the internet where you can shop, play games together with your friends and download apps that make your phone more versatile. It syncs with your email accounts and any sync enabled application, helps you make payments on the go (mobile banking), provide access to your data anywhere through cloud based tools like dropbox etc.. The GPS on your phone helps you find your way in a city by showing you on a city map that has been downloaded on to your phone using a wi-fi or similar data connection. You can drive almost safely even in a city new for you! These examples demonstrate an interaction between humans, electronic devices which may have sensors, mechanical devices and the traditional internet. By traditional internet I mean the internet which was seen initially  as just a repository of information and which has now grown to include processing engines like  those which facilitate “voice enabled search and SMS” on your smartphones, storage and compute space for cloud applications (like Amazon’s EC service) etc. Thus the “Internet of Things” is nothing but a network where human actions, electrical and mechanical devices and the internet come together to interact in a meaningful way. The scope of this interaction can be as varied and wide as possible depending on the intended result.

Software, Patents, Innovation, Ideas: A Curious Mix

Filing a patent is a big thing these days, especially in the academia. It has been there for quite a long time in the industry though. Earlier, it would suffice to publish in top quality journals or conferences, but now patents are the real icing on the cake. Filing a patent is a costly process and it is far more costlier to prosecute it till its allowed lifetime after it has been granted. One needs not only really deep pockets to engage in patent litigation but also an elaborate infrastructure to find out instances of patent infringement.

While a lot of the patents in earlier days would describe an invention/innovation in terms of its parts that make it work with detailed diagrams of parts etc., a lot of patents these days are filed based just on ideas. It is ideas which are getting patented and this is something that many people are concerned about, especially in the software industry. History shows us that similar ideas have been developed by different people independent of each other at different times and it is no different in modern times. Do we really have to patent ideas? Are they patentable? Don’t they stifle flights of fancy and imagination which have helped people in coming up with brilliant inventions and technologies? Where is the tradeoff between protecting intellectual property and protecting flights of imagination? I think that protecting both of these are important.  However, the dimension of “time” that patents add to an idea/invention can have an impact as one man’s flight of imagination at time “x” prohibits another man’s flight, even if independent, at  time “y” where x > y. It is a curious mix and definitely an important issue to be discussed and debated. You might be interested in reading ” The Patent, Used as a Sword” published by the International Herald Tribune.

Weizmann Institute of Science: People-Driven not Number-Driven

Prof. Daniel Zajfman , President of Israel’s Weizmann Institute of Science delivered a lecture on “How Can a Small Institute for Scientific Research in a Small Country have a Global Impact?” in NTU today. It was a pleasure listening to his ideas of scientific pursuit, academic governance, state of education, research etc. He emphasized a lot on his policy of being “people-driven” in a research or an academic institution. This is in contrast to many other places which are “number driven” as he himself stated. Numbers which are derived from world rankings, amount of grant money, number of citations etc. The model that Weizmann follows puts its people and their ideas first. He was particular about these people being given the freedom to pursue their ideas. According to him, it is important to let his brilliant scientists choose what they think is the next most important thing in research instead of they being dictated by other agencies and other people. And he showed that his model or the model at Weizmann also works and it works extremely well. He showed that research commercialization can be a by product of independent research pursuit instead of research commercialization dictating research. The world has a place for different kinds of models of academic governance and models that are borne out of the culture and the human capital of a place or a country are the ones that can benefit that country/region the most in the long run and will probably contribute to the global advancement of knowledge on a larger scale. This is what he probably meant when he said that he was not in favor of exporting research institutions to other places (for instance a Weizmann campus in Singapore) though he was all for international collaboration. It is good to see that there still exist such places which operate in a different way and have protected their autonomy and freedom from the “market-driven” culture that is slowly permeating different fields in higher education.  It is difficult to argue which one is better because it is extremely complicated but it is good to see that there is space for all and that not everybody has begun to think alike.

Can a computer do envy-free divison?

We have all studied division. In the world of simple mathematics, 8 divided by 2 is always 4.  But what about dividing a cake into 2 equal pieces? A computer program can always divide 8 by 2 and give 4 as answer, but can a computer program divide a cake into 2 equal pieces? Let us make it a bit more complicated. Say the cake has to be divided between persons A and B and in such a way that neither of them feels that the other person got more. This means that neither A or B will envy the share received by the other. So here the notion of equal division has to be understood in the context of the result leading to an envy-free solution. This is the subject of “Fair Division” also known as cake cutting problem. It is studied in politics, mathematics, economics and the like. Methods and algorithms have been proposed to achieve fair division but all require inputs from the parties involved in the division at different stages of the procedure. Note that these inputs need not be disclosed as these could be the feelings/assumptions/conclusions running in the minds of the parties involved. This means that different inputs at different stages can lead to different outcomes. Does it remind of “Observer Effect” in Physics? Yes. The inputs(observation of a current state of division) by a party affects the outcome of division (phenomenon being observed). It is impossible (?) for a computer to solve a problem of this type entirely on its own. Such problems arise routinely in allocation of goods, dispute resolution, negotiation of  treaties etc.

Borrowing terms from economics, a number can be treated as ‘a homogeneous good’ while a cake is essentially ‘a heterogeneous good’ as different parts of it can taste different. Hence, its envy-free division is far more complicated. If you are interested, try to read “Fair Division-From cake-cutting to dispute resolution“, an excellent book by Steven J. Brams (political scientist) and Alan D. Taylor (mathematician).