Indian Institute of Technology Hyderabad (IITH) is a premier institute of science and technology established in 2008. IITH has been consistently ranked in the&nbsp;<a href="https://iith.ac.in/reports/" rel="noopener noreferrer">top 10 institutes</a>&nbsp;in India for Engineering&nbsp;<a href="https://www.nirfindia.org/2021/EngineeringRanking.html" rel="noopener noreferrer" target="_blank">according to NIRF</a>&nbsp;making it one of the most coveted schools for science and technology in the country.

IITH offers&nbsp;<a href="https://iith.ac.in/academics/under-graduate/">undergraduate programs</a>&nbsp;in all the classical engineering disciplines, applied sciences, design, as well as several modern interdisciplinary areas. Students are given a flexibility to explore a broad set of areas, and potentially pursue a minor or double major in a discipline that is not their own. Students who wish to seek a deeper understanding of their own discipline are strongly encouraged to get involved in cutting-edge research with the help of a faculty to mentor them, and earn an Honors in their own field.

The very foundation of IIT Hyderabad is based on&nbsp;<a href="https://iith.ac.in/research/">research and innovation</a>. The vibrant research culture is evident from the number of patents and publications that IITH produces consistently every year. IITH offers&nbsp;<a href="https://iith.ac.in/academics/programmes-offered/">graduate programs</a>&nbsp;at both a masters, and a doctoral level, in several diverse areas. There are separate programs for technology, design, science, and liberal arts. The&nbsp;<a href="https://iith.ac.in/academics/post-graduate/">MTech program</a>&nbsp;is offered in various modes and durations to cater to the ever-growing need of postgraduate level professionals in the country.

IITH encourages and supports&nbsp;<a href="https://iic-iith.netlify.app/index.html" rel="noopener noreferrer" target="_blank">innovation and entrepreneurship</a>&nbsp;at every stage. The minor program in entrepreneurship is open to all students of IITH, and many of the courses are offered by industrialists who are entrepreneurs themselves. There are various&nbsp;<a href="https://iith.ac.in/research/centres-incubators/">innovation centers and incubators</a>&nbsp;that promote entrepreneurship and help mentor young innovators. IITH has been very successful in building tie-ups with leading academic institutions around the globe.

IITH enjoys a very special relationship with Japanese universities and industries that goes beyond academic and research collaborations. In fact, some of the iconic buildings in IITH campus will carry the signature of Japanese architecture.

IITH creates a unique holistic ecosystem for education that offers interactive learning, a very flexible academic structure, cutting-edge research, strong industry collaboration, and entrepreneurship. This is an environment which enables students and faculty to translate their dreams into realities.

IIT Hyderabad

For Affine Control Programs or Static Control Programs (SCoP), symbolic counting of reuse distances could induce polynomials for each reuse pair. These polynomials along with cache capacity constraints lead to non-Affine (semi-Algebraic) sets; and counting these sets is considered to be a hard problem. The state-of-The-Art methods use various exact enumeration techniques relying on existing cardinality algorithms that can efficiently count affine sets.We propose BullsEye , a novel, scalable, accurate, and problem-size independent approximation framework. It is an analytical cache model for fully associative caches with LRU replacement policy focusing on sampling and linearization of non-Affine stack distance polynomials. First, we propose a simple domain sampling method that can improve the scalability of exact enumeration. Second, we propose linearization techniques relying on Handelman's theorem and Bernstein's representation. To improve the scalability of the Handelman's theorem linearization technique, we propose template (Interval or Octagon) sub-polyhedral approximations.Our methods obtain significant compile-Time improvements with high-Accuracy when compared to HayStack on important polyhedral compilation kernels such as nussinov, cholesky, and adi from PolyBench, and harris, gaussianblur from LLVM-TestSuite. Overall, on PolyBench kernels, our methods show up to 3.31× (geomean) speedup with errors below ≈ 0.08% (geomean) for the octagon sub-polyhedral approximation. © 2022 Association for Computing Machinery.

World University root node

Department of Computer Science and Engineering

ACM Transactions on Architecture and Code Optimization

BullsEye : Scalable and Accurate Approximation Framework for Cache Miss Calculation

In the Euclidean k-Means problem we are given a collection of n points D in an Euclidean space and a positive integer k. Our goal is to identify a collection of k points in the same space (centers) so as to minimize the sum of the squared Euclidean distances between each point in D and the closest center. This problem is known to be APX-hard and the current best approximation ratio is a primal-dual 6.357 approximation based on a standard LP for the problem [Ahmadian et al. FOCS'17, SICOMP'20]. In this note we show how a minor modification of Ahmadian et al.'s analysis leads to a slightly improved 6.12903 approximation. As a related result, we also show that the mentioned LP has integrality gap at least [Formula presented]. © 2022 The Author(s)

Information Processing Letters

A refined approximation for Euclidean k-means

Graph partitioning problems are a central topic of study in algorithms and complexity theory. Edge expansion and vertex expansion, two popular graph partitioning objectives, seek a 2-partition of the vertex set of the graph that minimizes the considered objective. However, for many natural applications, one might require a graph to be partitioned into k parts, for some k &gt; 2. For a k-partition S1,..., Sk of the vertex set of a graph G = (V, E), the k-way edge expansion (resp. vertex expansion) of {S1,..., Sk} is defined as maxi∈[k] Φ(Si), and the balanced k-way edge expansion (resp. vertex expansion) of G is defined as min {S1,...,Sk}∈Pk max i∈[k] Φ(Si) , where Pk is the set of all balanced k-partitions of V (i.e each part of a k-partition in Pk should have cardinality |V |/k), and Φ(S) denotes the edge expansion (resp. vertex expansion) of S ⊂ V. We study a natural planted model for graphs where the vertex set of a graph has a k-partition S1,..., Sk such that the graph induced on each Si has large expansion, but each Si has small edge expansion (resp. vertex expansion) in the graph. We give bi-criteria approximation algorithms for computing the balanced k-way edge expansion (resp. vertex expansion) of instances in this planted model. © Anand Louis and Rakesh Venkat; licensed under Creative Commons License CC-BY.

Leibniz International Proceedings in Informatics, LIPIcs

Planted models for k-way edge and vertex expansion

The problem of computing the vertex expansion of a graph is an NP-hard problem. The current best worst-case approximation guarantees for computing the vertex expansion of a graph are a O log n-approximation algorithm due to Feige et al. [16], and O OPT log d bound in graphs having vertex degrees at most d due to Louis et al. [29]. We study a natural semi-random model of graphs with sparse vertex cuts. For certain ranges of parameters, we give an algorithm to recover the planted sparse vertex cut exactly. For a larger range of parameters, we give a constant factor bi-criteria approximation algorithm to compute the graph's balanced vertex expansion. Our algorithms are based on studying a semidefinite programming relaxation for the balanced vertex expansion of the graph. In addition to being a family of instances that will help us to better understand the complexity of the computation of vertex expansion, our model can also be used in the study of community detection where only a few nodes from each community interact with nodes from other communities. There has been a lot of work on studying random and semi-random graphs with planted sparse edge cuts. To the best of our knowledge, our model of semi-random graphs with planted sparse vertex cuts has not been studied before. © 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

Semi-random graphs with planted sparse vertex cuts: Algorithms for exact and approximate recovery

We investigate the value of parallel repetition of one-round games with any number of players k ≥ 2. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are connected in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.

Multiplayer parallel repetition for expanding games

We consider the problem of embedding a finite set of points {x1, . . . , xn} 2 Rd that satisfy 22 triangle inequalities into 1, when the points are approximately low-dimensional. Goemans (unpublished, appears in [20]) showed that such points residing in exactly d dimensions can be embedded into 1 with distortion at most p d. We prove the following robust analogue of this statement: if there exists a r-dimensional subspacesuch that the projections onto this subspace satisfy P i,j2[n] kxi - xjk 22 (1) P i,j2[n] kxi - xjk 22 , then there is an embedding of the points into 1 with O(p r) average distortion. A consequence of this result is that the integrality gap of the well-known Goemans-Linial SDP relaxation for the Uniform Sparsest Cut problem is O(p r) on graphs G whose r-th smallest normalized eigenvalue of the Laplacian satisfies r(G)/n(1)SDP (G). Our result improves upon the previously known bound of O(r) on the average distortion, and the integrality gap of the Goemans-Linial SDP under the same preconditions, proven in [7, 6]. © Yuval Rabani and Rakesh Venkat.

Approximating sparsest cut in low rank graphs via embeddings from approximately low dimensional spaces

Goemans showed that any n points x1, . . . xn in d-dimensions satisfying ℓ22 triangle inequalities can be embedded into ℓ1, with worst-case distortion at most √d. We consider an extension of this theorem to the case when the points are approximately low-dimensional as opposed to exactly low-dimensional, and prove the following analogous theorem, albeit with average distortion guarantees: There exists an ℓ22-to-ℓ1 embedding with average distortion at most the stable rank, sr(M), of the matrix M consisting of columns {xi-xj}i&lt;j. Average distortion embedding suffices for applications such as the SPARSEST CUT problem. Our embedding gives an approximation algorithm for the SPARSEST CUT problem on low threshold-rank graphs, where earlier work was inspired by Lasserre SDP hierarchy, and improves on a previous result of the first and third author [Deshpande and Venkat, In Proc. 17th APPROX, 2014]. Our ideas give a new perspective on ℓ22 metric, an alternate proof of Goemans' theorem, and a simpler proof for average distortion √d. © Amit Deshpande, Prahladh Harsha, and Rakesh Venkat.

Embedding approximately low-dimensional ℓ22 metrics into ℓ1

A recent result of Moshkovitz [10] presented an ingenious method to provide a completely elementary proof of the Parallel Repetition Theorem for certain projection games via a construction called fortification. However, the construction used in [10] to fortify arbitrary label cover instances using an arbitrary extractor is insufficient to prove parallel repetition. In this paper, we provide a fix by using a stronger graph that we call fortifiers. Fortifiers are graphs that have both ℓ1 and ℓ2 guarantees on induced distributions from large subsets. We then show that an expander with sufficient spectral gap, or a bi-regular extractor with stronger parameters (the latter is also the construction used in an independent update [11] of [10] with an alternate argument), is a good fortifier. We also show that using a fortifier (in particular ℓ2 guarantees) is necessary for obtaining the robustness required for fortification. © Amey Bhangale, Ramprasad Saptharishi, Girish Varma, and Rakesh Venkat.

On fortification of projection games

Guruswami and Sinop [11] give a O(1/δ) approximation guarantee for the non-uniform Sparsest Cut problem by solving O(r)-level Lasserre semidefinite constraints, provided that the generalized eigenvalues of the Laplacians of the cost and demand graphs satisfy a certain spectral condition, namely, λr+1 ≥ Φ∗/(1-δ). Their key idea is a rounding technique that first maps a vector-valued solution to [0, 1] using appropriately scaled projections onto Lasserre vectors. In this paper, we show that similar projections and analysis can be obtained using only ℓ22 triangle inequality constraints. This results in a O(r/δ2) approximation guarantee for the non-uniform Sparsest Cut problem by adding only ℓ22 triangle inequality constraints to the usual semidefinite program, provided that the same spectral condition λr+1 ≥ Φ∗/(1-δ) holds as above. © Amit Deshpande and Rakesh Venkat.