280 reputation
111
bio website turingcomplete.blogspot.com
location Thessaloniki, Greece
age 25
visits member for 3 years, 1 month
seen Mar 22 at 12:23

I recently received a BSc in Computer Science from the Computer Science Department of the Aristotle University of Thessaloniki, Greece, with an excellent mark.

My main research interest 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 have taken an undergraduate course strictly on computational theory and I've attended several other courses on relevant subjects, like finite automata, graphs, programming language design etc. Furthermore, I have studied on my own, either by studying papers or reading selected chapters from books such as the graduate-level book of Arora-Barak on Computational Complexity and the book on Communication Complexity by Kushilevitz-Nisan.

The previous year (2010-2011) I was working on my diploma project, a survey on hierarchy theorems and hierarchies in Computational Complexity. This year I am working on Communication Complexity.

I will be continuing my studies with a MS/PhD program in Saarland University, starting in Fall 2012.


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.