Login with your Social Account

computer board

Scientist solves 30 year old computer puzzle in two pages

A 30-year-old conjecture about the structure of building blocks of computer circuits which puzzled several computer scientists over many years has been solved by a researcher. Known as the “Sensitivity” Conjecture, it was one of the most frustrating open problems in the area of theoretical computer science. Several prominent scientists in discrete maths and theoretical computer science tried to solve it.

The conjecture involves Boolean functions, rules for converting input bits to a single output bit. One such rule is to output a 1 provided any of the input bits is 1, and a 0 otherwise; another rule is to output a 0 if the string has an even number of 1s, and a 1 otherwise. The computer circuits are a combination of Boolean functions and is the brick and mortar of everything in computer science. 

Researchers have tried to measure the complexity of a Boolean function over the years. Each measure tries to capture an aspect of how the input information determines the output. “Sensitivity” measures the chances of how the change in a single input bit affects the output. Similarly, the query complexity calculates the number of input bits needed to be sure of the output. Scientists have found that the measures fit into one framework, hence the value of one of them is a rough estimate of the value of others. However, only the complexity did not fit in: sensitivity.

Noam Nisan, Hebrew University and Mario Szegedy, Rutgers University conjectured in 1992 that the sensitivity indeed fits in the framework although no one could prove it. Scientists wrote long papers in the hope of the slightest progress. But now, Hao Huang, a mathematician at Emory University has proved it with a simple two-page argument about the combinatorics of points on cubes. Scientists have called the proof a “book” proof in connection to the notion of Paul Erdos that a celestial book is maintained where the proof of every theorem is maintained. 

In a Boolean function, the output is decided by a series of input bits similar to a bank loan application where there are several questions, whose answers on processing determine if the applicant is eligible for the loan. On denial of application one may think if a single question would change the outcome. If one lie flips the outcome then the function is sensitive to the particular bit. If seven lies would have individually flipped the outcome then the sensitivity of the Boolean function is seven. Overall sensitivity is calculated as the largest sensitivity value when considering all possible loan profiles. 

Sensitivity is an easy complexity to compute but it is not the only illuminating measure. Instead of paper application, the applicant could be interviewed where answer of one question determines the next. The maximum possible questions needed to ask is the query complexity of the function. There are several real world applications of this measure such as classification algorithm in machine learning, diagnosis of diseases. A low query complexity often makes things simpler. There are several other measures, such as the simplest way to write a function as a mathematical expression, a quantum physics version of query complexity. 

With the exception of sensitivity, scientists proved that all the measures are very closely linked. They have a polynomial relationship to one another, like one measure may be nearly the square root or cube of another. Only sensitivity did not fit in. Scientists thought it belonged but could not prove it for nearly 30 years.

Huang heard the sensitivity conjecture in 2012 over lunch with Micahel Saks, a mathematician at Institute for Advanced Study where Huang was a postdoctoral fellow. He was obsessed with the simplicity and elegance of the conjecture. He added it to a list of his “secret problems” and tried to solve it whenever he published a paper or learned a new tool. He knew that the conjecture could be proven if another conjecture about collections of points on cubes was proven. There is an easy way to go from string of n 0’s and 1’s to a point on cube with n dimensions. The n bits are used as coordinates of the point. 00,01,10 and 11 correspond to four corners of square in two dimensions: (0,0), (0,1), (1,0) and (1,1). A boolean function can be considered as a rule for coloring the corners with two different colors such as red for 0 and blue for 1. 

Craig Gotsman and Nati Linial figured out in 1992 that the proof of the sensitivity conjecture could be reduced to a simple question regarding cubes of different dimensions. If a collection of more than half of cube corners are chosen and coloured red is there a redpoint always which is connected to other red points. Four points (0,0,0),(1,1,0), (1,0,1) and (0,1,1) sit across the diagonals. However, when more than half points are coloured red, a connection is established and the question is how are the connections distributed. 

Huang tried to understand the question using matrix which tracks the points that are connected and then examine the eigenvalues. He tried on the idea for five years with no success. 

Then in 2018, he used Cauchy interlace theorem, a 200-year-old theorem relating the eigenvalues of the matrix to a submatrix making it the optimal tool to understand the relationship between the cube and subset of corners. He requested a grant from the National Science Foundation to explore the idea. 

But last month he realised that by switching the signs of few numbers in matrix he could prove that in any collection of more than half the number of points, there is some point which is connected to a minimum of square root of n other points. 

The proof is simple enough to understand in one sitting and it might be taught now in every combinatorics course at master level. The proof is strong enough to prove the conjecture and it can give new insights about measures of complexity. 

Journal Reference: arxiv

string theory

Physicist one step closer towards solution of the string theory puzzle

A physicist from the University of Colorado, Boulder is very close in solving a puzzle in the string theory which has been unsolved for more than 20 years now. 

Paul Romatschke, an associate physics professor at CU Boulder has figured out a different set of tools for what created the three-quarters dilemma. This mathematical puzzle of string theory has plagued scientists for several years. This has kept them from the realization and proof of the “Theory of everything”. The results of the study have been published in Physical Review Letters.

It may not be applicable for the regular world we see around us but it opens the possibilities for the understanding of high-level physics. The results of the study could change the ways we look at the several important domains of physics such as string theory or quantum field theory. These set of theories describe the field dynamics and the entities which permeate everything. 

Romatschke said that it would have been really great to actually understand the meaning of three-quarters however this outlook is a step towards the solution, if not the solution, and provides a suggestive picture. 

The string theory has puzzled the scientists since 1960’s. It is a theoretical framework which involves fundamental, one dimensional objects known as strings. These entities constitute the fabric of everything. It was first put forward for addressing a number of questions in fundamental physics. But from there it has been applied for studying several topics such as black holes, nuclear physics to even the origin of the universe. 

One of the biggest achievements of the string theory is the conclusion that black holes and matter are nearly the two faces of a single coin. This duality allows researchers to map several properties of matter such as pressure to the black hole properties as obtained from the general theory of relativity of Einstein. It would create the possibility of a greater mathematical exploration of the string theory. However, physicists have not been able to prove a major aspect of the string theory. 

Since the duality was discovered 20 years ago, researchers have tried to clear the roadblock with equations of increasing complexity. But they arrive at the same result always. The free energy obtained from the strong interaction is nearly three-quarters of the strength of weak coupling. 

Romatschke put the equations for space which has only two dimensions. He used equations from the previous research, as well as modern techniques of quantum field theory and he proved that a relationship exists when the matter is forced to interact from zero to infinite interaction. Calculations revealed the infinite coupling’s pressure is four-fifths of that at zero coupling. This can be a standard approach in solving puzzles of this nature. It also indicates there is a stronger relationship for space with lesser dimensions. 


Stata Center1 MIT

20 year old cryptographic puzzle solved by self-taught programmer

World famous architect, Frank Gehry received a time capsule in the month of April in 1999. It had the instructions to be included in his designs for the building which would eventually house the Computer Science and Artificial Intelligence Lab of MIT. It was basically a museum which included the early history of computing. It had items which were contributed by the likes of Tim Berners Lee and Bill Gates.

It was not to be opened for the next 35 years unless someone cracked the cryptographic puzzle which was present in the design. It was made by Ron Rivest, one of the co-inventors of the RSA cryptographic protocol. It was designed in such a way that it would take almost 35 years to compute the answer.

However, on April 15, after almost 20 years the puzzle was announced, it has been solved by Bernard Fabrot, a Belgian programmer. The solution was to be sent to the director for the Laboratory of Computer Science. But Bernard found out that the laboratory did not exist any more. It was merged with CSAIL.

The puzzle was to find a number which was obtained after executing a squaring calculation almost 80 trillion times. After obtaining this number it is to be put in a mathematical operation which uses this and another number which is present in a puzzle. This gives a new number which can be translated to a congratulatory message.

Solving this puzzle needed sequential operations. It means that the calculations had to be approached one by one, as the next step needed the previous result. Thus using powerful machines such as supercomputers was of no use here. Rivest calculated that it would take almost 35 years to come up with the answer to the puzzle.

Bernard Fabrot, an independent developer came to know about the puzzle in 2015. He felt that it could be solved faster using the GNU Multiple Precision Arithmetic Library which is a free software for performing precise arithmetic calculations. Only for solving the puzzle, he dedicated one of his CPU cores to compute the squaring operations and his computer was running 24/7, except when he was holidaying. He solved the puzzle after three and a half years.

Unbeknownst to Fabrot, another group called Cryptophage was also working to solve the puzzle. Led by an ex-Intel engineer, Simon Peffers, this group was working on verifiable delay functions for security operations. With the help of an algorithm designed by Erdinc Ozturk, Sabanci University and a multi-purpose chip they would have solved the puzzle on May 10, but they were beaten by Fabrot just by few days.