chazisop

275 reputation

111

bio	website	turingcomplete.blogspot.com
	location	Thessaloniki, Greece
	age	24
visits	member for	2 years, 2 months
	seen	19 hours ago
stats	profile views	68

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.

	275 reputation	bio	website	turingcomplete.blogspot.com	visits	member for	2 years, 2 months
111 badges		location	Thessaloniki, Greece		seen	19 hours ago

summary answers questions tags badges favorites bounties reputation activity

56 Actions

suggestions reviews revisions comments badges posts accepts all

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.