290 reputation
111
bio website turingcomplete.blogspot.com
location Saarbrucken, Germany
age 26
visits member for 3 years, 9 months
seen Dec 10 at 17:40

In November 2011, I obtained a BSc in Computer Science from the Computer Science Department of the Aristotle University of Thessaloniki, Greece, with an excellent mark. My bachelor thesis included a survey on hierarchy theorems and hierarchies in Computational Complexity, as well as investigating the possibilities of improving the deterministic time hierarchy theorem.

Currently I am investigating algebraic complexity theory, especially in relation with the recent sequence of results based on depth reduction that have come close to separating VP and VNP. I am interested in so called "separating modules", which are sets of polynomials that characterize complexity classes and provide a common framework for many algebraic circuit lower bound proofs. I wish to investigate the inherent strengths and weaknesses of this framework, whether it is possible to utilize it in producing new proofs in the area of algebraic complexity theory and how it can be "translated" to the boolean world.

Another research interest of mine is structural complexity theory. I am highly interested in the polynomial hierarchy and determining the relations between classes in the hierarchy and other classes related to it. I am also acquainted with communication complexity, which I studied to some extent after receiving my BSc degree.

Since Fall 2012, I am pursuing a Ms/PhD degree in Saarland university. During this time, I have completed a variety of advanced courses, including ones in Complexity Theory, Algorithms and Data Structures and Graph Theory.


May
14
awarded  Caucus
Jul
2
revised Prime number generator, how to make
changed question objective
Jun
30
answered Prime number generator, how to make
Jun
14
comment Reductions for regular languages?
I would recommend crossposting this to cstheory stackexchange, even if an answer is already given, for future users' convenience. Be sure to mention that you crossposted it on both sites if you do.
Mar
16
awarded  Yearling
Jan
5
answered Is Turing completeness monotone with respect to Cook reductions?
Jan
5
comment Expanding this boolean expression
A more general comment: If you work with small boolean expressions (<4 variables) a truth-table for both expressions can always determine equivalence.
Aug
11
comment satisfiable assignment close to an unsatisfiable assignment
For those not familiar with complexity, Levon's error is using "definitely" , since we do not know if P is equal to NP or not.
Aug
4
comment Applications of Convergence of a series in Algorithms
Sometimes convergence is used to show that an algorithm is correct or behaves like it should, e.g. in machine learning and probabilistic algorithms.
Aug
4
comment Find the NFA for the language $\{ w | \text{ w contains an even number of 0s, or contains exactly two 1s } \}$
Raphael , you are right. The extra advice that small examples from exercise books will be ok, even if there is an exponential blowup (still , it can be time-consuming). As for the link, it was downloading a .pdf.gz file that wasn't working with my reader, so I changed it to a plain html view of the slides.
Aug
4
revised Find the NFA for the language $\{ w | \text{ w contains an even number of 0s, or contains exactly two 1s } \}$
added 69 characters in body
Aug
3
answered Find the NFA for the language $\{ w | \text{ w contains an even number of 0s, or contains exactly two 1s } \}$
Aug
2
comment non time constructible functions
I believe the Inverse Ackermann function is not-time constructible.
Jul
25
comment How to determine in polynomial time if a number is a product of two consecutive primes?
Yes but this algorithm is for general use, while this question addresses a specific factoring problem. Special conditions can make the difference between NP-completeness and membership P, or even computability and uncomputability.
Jul
23
comment Can an algorithm be faster than O(1)?
Let's assume that the particle model you describe is indeed less than constant in running time. My point is that under any model, you must observe the output somehow, therefore you need at least 1 step. As a small correction, the omega in my previous comment was supposed to be capital. Furthermore, we must consider not what model are possible, but rather what models better fit computation as it is in our universe. So is there a computational procedure that takes less than constant time and if yes, does it matter to us?
Jul
22
comment Can an algorithm be faster than O(1)?
Given your examples, e.g. the gears model, a suitable measure of complexity is needed (e.g. number of revolutions). I believe the issue that all algorithms are $\omega(1)$ is simple as stating that all algorithms must output at least 1 bit of information. As a sidenote, big-oh notation was there half a century before modern digital computers.
Apr
19
comment What is a good language to develop in for simple, yet customizable math programs?
I believe you should ask your question is more appropriate for stackoverflow.com
Apr
13
comment Any concise way to represent this in a formula?
Just keep in mind that if you are too concise you risk confusing your audience.
Apr
12
awarded  Citizen Patrol
Apr
10
comment What is undecidability
@persononinternet I can guarantee you that you cannot simulate a 1x1x1 cm cube of the real world on the best supercomputer there is now. The reasons are due to physics but the borders between physics and computational models can be thin, so you can interpet them in a computation light. Simulations like the ones of the recent tsunami ignore many events as irrelevant and only monitor the progress of events that will have a significant effect.