Amik Raj Behera
I am a Ph.D. student at the Department of Computer Science, Aarhus University. I am glad to be advised by Prof. Srikanth Srinivasan. I completed my undergraduate studies at the Chennai Mathematical Institute.
My interests are primarily in Complexity Theory.
Check out this cool video by our department :)
I organized a combinatorics seminar in Spring 2024 at Aarhus University. Here is the webpage with pointers to some resources.
Research
In the problem of local correction, we are given a polynomial promised to be close to a unique linear function, and the task is to recover local information of the linear function by making queries to the input polynomial. We consider linear functions with Boolean cube as the domain and coefficients are real numbers.
We give a nearly optimal local corrector algorithm (in terms of queries).
We also consider the problem of local list correction, we are given a polynomial, which is close to several linear functions. The task is to recover local information of all the close linear functions by making queries to the input polynomial (the setup is the same as local correction).
We first show that the number of close linear functions is small (a combinatorial bound) and then give a local list corrector algorithm.
[STOC 2024] [ECCC] [arXiv] [Slides (1-hour talk)]
Contact Details
Email - bamikraj [at] cs [dot] au [dot] dk
Building: Nygaard (5335), Room: 328
Department of Computer Science, Aarhus University
We decreased the number of questions without increasing the number of answers. - From Nature of Computation
"It is only those who have neither fired a shot nor heard the shriek and groans of the wounded and lacerated who cry aloud for blood, more vengeance, more desolation." - General Sherman, from a letter sent in May of 1865 in the midst of his march to the sea.
“An algorithm without a proof is a conjecture, it’s not a theorem. And if you’re proving things, well, that means mathematics.” - Leslie Lamport in The Man Who Revolutionized Computer Science With Math
“If you cannot solve a problem, then there is an easier problem that you cannot solve: find that problem.” - George Pólya