What are the opening hours?

Monday 9am - 5pm Tuesday 9am - 5pm Wednesday 9am - 5pm Thursday 9am - 5pm Friday 9am - 5pm

Institute of Mathematics, Gurgaon, H-501 Palam Vihar Sector 1, Gurugram (2026)

21/04/2024

The third important application of the Clique Algorithm of 2006 is for on-demand data broadcasting, such as over-the-top (OTT) services and live streaming. The method for efficient processing of on-demand broadcast requests with network coding was developed by Victor CS Lee and his team at the City University of Hong Kong in 2011. The typical architecture consists of one database server and many clients. Each client has a local cache to store the requested data items retrieved from the encoded packet broadcast by the server. The on-demand service requests from clients are stored in a service queue on the server. Due to bandwidth limitations of the uplink and downlink channels, the server must encode the packets of data in such a way that a maximum number of client’s service requests are fulfilled with each broadcast of an encoded packet of data. The client-requests (CR) graph is constructed dynamically by the server as follows. There is a vertex v(ij) for every client c(i) who requests data item d(j). There is an edge between v(ij) and v(kl) if and only if either client c(i) and c(k) request the same data item d(j)=d(l) or the client c(i)’s cache contains the data item requested by client c(j) and vice versa. Now, our clique algorithm is invoked, which finds a maximum clique in the CR graph. The packet of data to be broadcast is encoded according to the maximum clique, ensuring that the maximum number of clients have their request fulfilled.
https://www.dharwadker.org/clique/

14/04/2024

The second interesting application of the Clique Algorithm of 2006 is Logical Itemset Mining, an AI technique for retailers to accurately predict the items in a customer’s market basket or semantic association of items in large databases. The logical itemset mining technique was discovered by AI experts at Google Inc. and NIIIT Hyderabad in 2012. They demonstrated the technique for customer wish lists and ratings in the huge Internet Movie Database, IMDb. Here the vocabulary consists of tags of words which customers have associated with particular movies. The semantic association, called co-occurrence, of pairs of tagged words is defined by a probability function based on the Jaccard similarity coefficient which gives a measure of similarity of two sets of data. A finely-tuned threshold value on the probability function determines when a pair of tagged words co-occurs consistently for a particular movie. The co-occurrence consistency graph is defined with vertices as the tagged words in the vocabulary and an edge between two vertices if and only if the two tagged words consistently co-occur. A clique is a logical itemset by definition. They use our algorithm to find a maximum clique in this graph, which yields the largest logical itemset. For instance, a maximal clique with purple vertices and golden edges shown in the picture furnishes a surprisingly intelligent wish list of critically acclaimed movies, associated with the given word tags.
https://www.dharwadker.org/clique/

07/04/2024

The first useful application of the Clique Algorithm of 2006 is the optimization of data exchange in vehicular networks, by NXU Semiconductors, Nanyang Technological University and the Singapore Economic Development Board in 2018. The NXU-NTU Singapore project aims to test smart mobility solutions in real-life scenarios with a focus on secure Vehicle-to-Everything (V2X) communications. V2X are intelligent systems integrated into vehicles, which are capable of wirelessly collecting and analyzing data from other vehicles and surrounding smart infrastructure over a distance of up to two kilometers. Studies have shown that V2X safety functions can reduce multi-vehicle accident figures by more than 80%. The standard for secure data exchange in vehicular networks is the IEEE 802.11p. The actual bits of data consist of service requests by vehicles, which are broadcast as packets in the network. A vehicle submits a new request only when the previous submitted request is served or expired, which means each pending request in the service queue represents a unique vehicle. We define a graph G with the vehicles as vertices and connections in the network as edges. Our algorithm finds a maximum clique in this graph. The encoded packet corresponding to the maximum clique will satisfy the maximum number of vehicles per broadcast. For example, in the V2X vehicular network with 11 vertices the maximum clique is shown with 4 purple vertices and 6 golden edges.
https://www.dharwadker.org/clique/

31/03/2024

The third important application of the Independent Set Algorithm of 2006 is a new method for the protection of Integrated Circuits against hardware Trojans and other malicious modifications, by Sheng Wei in his thesis at UCLA in 2013. This is an emergent threat because various components of an integrated circuit, like the one for the iPhone shown in the picture, are manufactured by various competing companies with their own vested interests. The integrated circuit is a vast network of Boolean logic gates and switches. Hardware Trojans are usually hidden as small modified fragments of the circuit that will attack through certain vulnerable switches undetected. The key idea of Wei’s thesis is to identify the vulnerable switches of the integrated circuit as the switches which are most rarely used during operation. The network is a directed graph with the logic gates as the nodes. A node can have only one output but any number of inputs (fan-ins) and can be an input to any number of other nodes (fan-outs). A fan-in from node A to node B is called transitive if there is a path in the directed graph from A to B. We construct the undirected graph G of the integrated circuit, as follows. The vertices of G are the logic gates and there is an edge between two vertices A and B if and only if A and B share at least one transitive fan-in. Now, our algorithm finds the golden vertices of an independent set in G. These are the rarely used switches.
https://www.dharwadker.org/independent_set/

24/03/2024

The second interesting application of the Independent Set Algorithm of 2006 is constructing Quantum Error Correction Codes by Jonas Almlöf in his 2016 thesis at the KTH Royal Institute of Technology, Stockholm. In quantum computers, the basic unit for storing and transmitting data is the qubit, as opposed to the bit in classical computers. A qubit can be in a state of linear superposition of two logical states, 0 and 1, at the same time; two qubits can be in a state of linear superposition of four logical states 00, 01, 10 and 11, at the same time; and so on. Quantum computers harness these quantum superposition states to speed up computational problem solving by performing many logical steps simultaneously. However, the quantum information stored in a qubit is highly susceptible to errors due to decoherence and other quantum noise. If you peek inside the box, Schrödinger’s cat ceases to exist! Thus, error correction is essential for meaningful quantum computation. The way to construct a quantum error correction code is to spread the logical information of one qubit onto a highly entangled state of several physical qubits. We demonstrate with a 4 qubit example. Define a graph with 16 vertices corresponding to all possible states of the 4 qubits. Define edges between vertices that differ in exactly one qubit. Our algorithm finds a maximal independent set of golden vertices in this graph. This is an error correction code for a qubit.
https://www.dharwadker.org/independent_set/

17/03/2024

The first useful application of the Independent Set Algorithm of 2006 is the design of a triangle mesh data structure for computer graphics by Jarek Rossignac at Georgia Tech in 2013. Triangle meshes are the most common representation of surfaces in computer graphics and correspond to the simplicial decomposition of surface manifolds in mathematics. The usual representations of triangle meshes using x, y, z coordinates of the vertices ignore the adjacency relations of the triangles in the mesh. To find out which triangles are adjacent necessitates a linear search over all triangles. Rossignac’s data structure represents the geometry and connectivity of a mesh by grouping vertices and triangles into fixed-size records, most of which store two adjacent triangles and a shared vertex. The compact random-access file can be streamed, making it possible to render meshes with billions of triangles on a desktop computer. We demonstrate the method with two examples. From the triangle mesh we construct a graph with vertices and edges of the mesh itself. Next, we use our algorithm to find a maximum independent set, shown by the golden vertices in the examples. The golden vertices are paired with their adjacent triangles clockwise. In the left example, all triangles are paired with some golden vertex. In the right example, the triangle 7 is not paired with any golden vertex. Such triangles are presented as isolated records in the data structure.
https://www.dharwadker.org/independent_set/

10/03/2024

The third important application of the vertex cover algorithm of 2006 is to design an optimum strategy for the protection of critical infrastructure, like the electricity grid of a country, from enemy attack and natural disaster. It was shown by Eric Filiol and his team of engineers from the French military in 2016, that it is possible to take down the entire electricity grid by targeting only a few of its critical components. The electricity grid is a synchronized network of transmission and distribution lines operated by sophisticated control centers. Considered as a graph, the control centers are the vertices and the transmission lines are the edges. The critical components form a vertex cover for the graph, a subset of vertices adjacent to every edge in the graph. The control centers forming a vertex cover can monitor the entire grid. Thus, a minimum vertex cover found by our algorithm is an optimum solution for monitoring the entire electricity grid. From the satellite image of the illuminated subcontinent at night, we can construct a model of India’s electricity grid as a graph with 30 vertices (control centers) and edges (transmission lines). Care is taken to ensure that the graph is planar so that the transmission lines do not cross. Our vertex cover algorithm finds a minimum vertex cover consisting of 16 green vertices that meet all edges in the graph. The entire electricity grid can be monitored from these 16 control centers.
https://www.dharwadker.org/vertex_cover/

03/03/2024

The second interesting application of the Vertex Cover Algorithm of 2006 is the design of robust Firewalls to protect computer networks against Malware attacks. In 2007, Eric Filiol and his team of cyber security experts with the French military examined how the vertex cover algorithm may be used to tackle the problem. They first looked at the problem from the hacker’s point of view. The malware is designed to spread throughout the graph of the network, with vertices representing the individual computers (IP addresses) and edges representing the connections. Since we cannot predict which vertex the malware will infect first and along which connections it will attempt to spread, our firewall must be designed to scan every edge and every attempt by the malware to spread to other vertices. The firewall must be a vertex cover for the entire network graph, so by definition, the firewall can scan every attempted connection in the graph. To save on computational resources, the optimum firewall is a minimum vertex cover in the graph. Filiol’s team tested the firewall on a simulation of a complex heterogeneous network consisting of millions of clients, servers and routers, like the internet. For example, our algorithm finds an optimum firewall (minimum vertex cover with 40 green vertices) in a computer network (graph with 60 vertices). Note that every edge is incident to at least one green vertex and every connection is scanned by the firewall.
https://www.dharwadker.org/vertex_cover/

25/02/2024

The first useful application of the Vertex Cover Algorithm of 2006 is the optimal positioning of sentinels on a network of streets. The picture shows an aerial view of the streets adjoining the institute and we demonstrate how the algorithm works for the area marked by the white square. There are 19 streets with 14 intersections in the network. The sentinels must be placed at the intersections so that they have a clear view of all the streets converging at that intersection. If the street bends around the line of sight, we must add intersections to the curved street in straight line segments until the whole street is in line of sight from some intersection. An optimum solution consists of placing sentinels at the intersections such that every street in the network is covered by some sentinel, using the minimum number of sentinels. We first convert this into a graph theory problem. The network of streets in the white square is shown on the left. The 14 intersections define the vertices and the 19 streets define the edges of a graph shown on the right. A solution consists of finding a subset of vertices, called a vertex cover, such that every edge of the graph has an endpoint in the vertex cover. An optimum solution consists of finding a minimum vertex cover, one with the fewest number of vertices. Our algorithm finds a minimum vertex cover 2, 4, 5, 7, 9, 11 and 13. Positioning seven sentinels at these intersections solves the problem.
https://www.dharwadker.org/vertex_cover/

18/02/2024

The third important application of the Hamiltonian circuit algorithm of 2004 that we wish to highlight is the fault-tolerant ring topology for a wireless sensor network with time division multiple access (TDMA), designed by Gyula Simon in 2012. In TDMA networks, nodes mainly sleep and only wakeup when their transmission or reception time is scheduled. TDMA provides an energy efficient real time operation of the sensor network. For example, TDMA is a cell phone standard which first appeared with second generation 2G cell phone systems. The ring topology is best suited for applications like Alarm Systems that require data to be transmitted from any node to potentially every node, in guaranteed time. We explain the methodology with a small example of a TDMA network with 8 sensors shown on the bottom left. This is a Dirac graph, since each sensor is connected to 4 = 8/2 other sensors in the network. Our algorithm is used to find a Hamiltonian circuit, shown in blue. Now, the same graph with the vertices ordered by the Hamiltonian circuit is shown on the right and the blue ring topology for the sensor network becomes apparent. If one or more sensors in the network are damaged then we redefine the network graph by removing the damaged sensor vertices and corresponding edges. Our algorithm is used again to find a Hamiltonian circuit, if one exists, in the reduced sensor network. This defines a fault tolerant ring topology for the sensor network.
https://www.dharwadker.org/hamilton/

11/02/2024

The second interesting application of the Hamiltonian circuit algorithm of 2004 uses Hamiltonian Totems as passwords, a physical authentication protocol developed by Harvé Chabanne and his team at the Paris Tech Consortium in 2013. Existing authentication protocols such as textual and graphical passwords are subject to brute force and shoulder surfing attacks, while users are reluctant to use biometrics for identification, due to its intrusiveness. The term “Totem” is inspired by Christopher Nolan’s Sci-Fi classic “Inception”. The physical Totem is constructed from a cube as follows. Four vertical sides of the cube are divided into small squares and four Dirac graphs are defined by connecting vertices with edges on each face. In the definition, it is ensured that each vertex has degree at least n/2 where n is the total number of vertices. The Hamiltonian circuit algorithm finds a Hamiltonian circuit in each of the four graphs. Now enough edges are removed from the graphs so that each Hamiltonian circuit shown in the picture is unique. The top and bottom faces of the cube may be added to provide physical stability and the Totem can easily be printed using a 3D printer. A recognition procedure similar to scanning QR or bar codes is used to read the Totem. In future development, the Totem could use the inside of the cube to define a more complicated Hamiltonian circuit.
https://www.dharwadker.org/hamilton/

04/02/2024

The first useful application of the Hamiltonian circuit algorithm of 2004 we discuss is 3D Hardware canaries that are designed to provide security for 3D integrated circuit chips. Since the limits of Moore’s Law have already been reached for 2D chip design, we are forced to use the third dimension to design even more complicated integrated circuits. For example, Samsung announced a new 3D chip to power its 5G phone infrastructure in 2020. A 3D chip is manufactured by stacking many layers of metal to form the integrated circuit. Security sensitive circuits need to be surrounded by a wire cage and a Hamiltonian circuit in the resulting graph acts as a hardware integrity verification sensor, called a canary. The terminology comes from the fact that it is an early indicator of potential danger or failure, like a canary in a coal mine! A team of telecom engineers at the Paris Tech Consortium studied various design strategies for canaries. They found that Hamiltonian circuits on certain cubical cages generated by our algorithm give an optimum solution. A specific example of the canary is shown. Consider 1000 = 10x10x10 unit cubes stacked to form a larger cube. The common vertices and edges are identified to give the cubical cage graph with 1000 vertices. Our algorithm finds a Hamiltonian circuit in the cubical cage graph, a path that visits each vertex exactly once and returns to the original vertex, shown in blue. This is an optimum canary.
https://www.dharwadker.org/hamilton/

Institute of Mathematics, Gurgaon

21/04/2024

14/04/2024

07/04/2024

31/03/2024

24/03/2024

17/03/2024

10/03/2024

03/03/2024

25/02/2024

18/02/2024

11/02/2024

04/02/2024

Address

Opening Hours

Website

Alerts

Contact The University

Shortcuts

Share

Category

Monday	9am - 5pm
Tuesday	9am - 5pm
Wednesday	9am - 5pm
Thursday	9am - 5pm
Friday	9am - 5pm