Browsing Computer Science and Automation (CSA) by Subject "Research Subject Categories::MATHEMATICS::Applied mathematics::Theoretical computer science"
Now showing items 1-4 of 4
-
Equivalence test for the trace iterated matrix multiplication polynomial
An m-variate polynomial f is affine equivalent to an n-variate polynomial g if m > n and there is a full rank n * m matrix A and a n-dimensional vector b such that f(x) = g(Ax + b). Given blackbox access to f and g (i.e ... -
Fast Algorithms for Max Cut on Geometric Intersection Graphs
In this work, we design fast algorithms for max cut on geometric intersection graphs. In the maximum cut (a.k.a., max cut) problem, the input is an undirected graph, and the goal is to partition the vertex set into two ... -
Multi-Armed Bandits – On Range Searching and On Slowly-varying Non-stationarity
Multi-Armed Bandits (MAB) is a popular framework for modelling sequential decision-making problems under uncertainty. This thesis is a compilation of two independent works on MABs. 1. In the first work, we study a ... -
New Algorithmic and Hardness Results in Learning, Error Correcting Codes and Constraint Satisfaction Problems
Approximation algorithms are a natural way to deal with the intractability barrier that is inherent in many naturally arising computational problems. However, it is often the case that the task of solving the approximation ...