Questions tagged [soft-question]
A soft question is a question (possibly subjective) about the field of theoretical computer science as opposed to being a question in theoretical computer science.
387
questions
6
votes
0answers
521 views
How fundamental is undecidability? [closed]
What does it mean that some problem is undecidable?
For instance the halting problem.
Does it mean that humans can never invent a new technique that always decides whether a turing machine will halt?...
5
votes
4answers
456 views
Natural notion for computational hardness
When I teach students concepts like intractable problems and efficient algorithms in discrete structures or data structures and algorithms, it is difficult for students to intuitively grasp somewhat ...
asked Feb 17 '11 at 11:13
Mohammad Al-Turkistany
20.1k4 gold badges55 silver badges138 bronze badges
5
votes
2answers
473 views
Reading Papers with Unclear Typesetting
From time to time, I have to read a paper with unclear typesetting. By this, I mean:
very small fonts; sometimes 8pt or smaller.
very bad scan;
Using bitmap fonts instead of vector ones.
too old ...
5
votes
1answer
566 views
Simple Constructions of Special Graph Families
Consider the following definition, taken from Chung's 1978 paper:
An $(n, m)$-concentrator is a graph with $n$ input vertices and $m$ output vertices,
$n \ge m$, having the property that, for ...
5
votes
2answers
919 views
Handbook of Logic in Computer Science - is it worth it?
I just found the first volume of Handbook of Logic in Computer Science in a library, but unfortunately I won't be able to use it here. It seems like a great resource, but it's insanely expensive to ...
5
votes
4answers
816 views
TCS conferences for undergraduate students?
I have noticed that ICFP has a student volunteer program and research program that accepts undergraduate students and POPL have the Programming Language Mentoring Workshop, so I was wondering if there ...
5
votes
2answers
1k views
What to do as a Theoretical computer science PhD student in a free time?
I am a mid-stage theoretical computer science student. Although I have a busy schedule, I still have a one or one a half hour in a day which I devote to reading and solving the question given Jeff ...
5
votes
2answers
546 views
How can I obtain famous articles which are not available online?
I have Googled myself to death, but have been unable to find the following articles:
Breen, E., Monro, D., 1994. An evaluation of priority queues for
mathematical morphology.
R. Beare and H. Talbot.,...
5
votes
3answers
254 views
What are interesting algorithmic questions for groups in table representation?
I am currently reading about research problems in nilpotent groups ( assume table representation ). As we know that solvable group isomorphism is known to be in the (almost ) intersection of $\mathcal{...
5
votes
1answer
246 views
Is education for research-based CS at odds with that of industrial CS?
I'm an undergraduate strongly interested (well, this is a hunch) in theoretical CS and all things mathematical. While I'd like to devote my time to participating in research opportunities and learning ...
5
votes
2answers
3k views
What are the main sub-areas of theoretical computer science?
I often want to give students a broad view of theoretical computer science, in the beginning of algorithms class or when advising a new student. It is hard for me to decide which sub-areas to talk ...
5
votes
1answer
3k views
Some good Theoretical Computer Science Journals
I have been doing some work in Theoretical Computer Science(especially related to algorithms), and I wanted the publish some of my findings. Can someone please suggest some good journals or ...
5
votes
3answers
410 views
Are there websites for TCS announcements that maintain mailing-lists or web feeds?
For a while, I have been wondering if there exists some site where you can subscribe to receive TCS-conference announcements via e-mail, or, alternatively, that offers some periodically-updated web-...
5
votes
1answer
238 views
Site with collection of exercises in TCS?
Is there a website with a large collection of exercises for theoretical computer science, sorted by topics? I know that many exercises can be found in different textbooks, I'm looking for an online ...
5
votes
1answer
417 views
What type of mathematical problems interesting for TCS researchers?
I am Ph.D student (about to graduate) in TCS. I have worked on some problems. I have been able to publish few research paper. There are many research problems in mathematics as well in TCS. I am sure ...
5
votes
1answer
455 views
How should I perform research as an Undergraduate
Are there distinct fields or types of problems which have contributions that are realistic to achieve for an undergraduate?
5
votes
0answers
125 views
Program size versus program running time
Short "naive" question:
Is it true that faster algorithms require longer programs ?
Given a decision problem $A$ and a reasonable model of computation, there can be many ways (algorithms) ...
5
votes
0answers
163 views
What research is being done in classical complexity theory?
As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as ...
5
votes
0answers
179 views
Is E.M Luks algorithm for trivalent graph isomorphism parallelizable?
It is still open whether also Luks’ efficient GI algorithm for graphs with bounded degree is parallelizable i.e. NC.
I get this from the survey "On Graph Isomorphism for Restricted Graph Classes" by ...
5
votes
0answers
135 views
What is the significance of regarding the mutual exclusion problem as a problem of physics?
In the description of his own paper "On Interprocess Communication" [Distributed Computing 1, 2 (1986), 77-101], Leslie Lamport wrote
Most computer scientists regard synchronization problems, such ...
5
votes
0answers
234 views
Being a theoretician at a business university?
I'm currently on the job market and I've seen some open faculty positions in computer science at a business university (which is quite reputable among its kind). While the job opening doesn't ...
5
votes
0answers
120 views
conceptual tools for illustrating types of computation?
From time to time I come across concepts in programming that take a certain number of exposures to grasp. Things like: tail calls, futures, monads, coroutines, closures, call/cc.
The common theme is ...
5
votes
0answers
608 views
Learning quantum CS [duplicate]
Possible Duplicate:
What is the quantum computational model?
What is the best way to study quantum branch of CS for the person with rather advanced background in classical CS? Does one need to ...
5
votes
1answer
156 views
Interesting programs on small machines
I am teaching a course and have a tiny implementation of a counter-style machine that has the following instructions and two registers, r0 & r1
...
4
votes
4answers
497 views
TCS Research Frontier with Huge Practical and Industrial Impact on our Society
While CS theorists pursue the beauty and unity of their mathematical theories, their results can have a practical and industrial impact.
As we know, P versus NP is often talked about with its ...
4
votes
3answers
526 views
Is one definition of the word paradox, “something that can be used to prove the halting problem undecidable?”
I've been toying recently with the idea that the set of all "real-world" paradoxes...such as the Liar's Paradox, Russell's Paradox, the Unexpected Hanging Paradox, the Berry paradox, etc. ......
4
votes
2answers
360 views
TCS oriented refs/survey on group theoretic word problem
The word problem for groups was shown to be Turing-complete in 1955 but has many decidable subcases. This problem arose more in mathematical group theory than in theoretical computer science, but now ...
4
votes
2answers
726 views
What is considered significant when applying for a TCS PhD with major changed
I am a Master student on CS. Actually in theory.
I have a BE in polymer (Chemical Eng stuff), and I struggled somehow to get enrolled in this program.
I want to apply a TCS PhD in US. So, what do ...
4
votes
2answers
2k views
List of TCS conferences along with important dates
I saw that there is a post with a List of TCS conferences. However, this does not list important dates like conference date, submission deadline etc. Is there any post or website which maintains these ...
4
votes
2answers
752 views
What are the prospects of research in database field?
I have been working with database management systems, and would like to focus on research in this very area some day.
I was having a look at the various research labs around the world,
...
4
votes
1answer
175 views
How often is the ECCC queue cleared?
I wanted to know as to how often are the submissions for ECCC cleared? Or do we know when is the next set of uploads going to be made on that site? Unlike arxiv where I know when my paper will go ...
4
votes
1answer
289 views
Consequences of Polynomial & QuasiPolynomial time algorithms for UP, FewP and CoC=P
I have came up with two alternate universe scenarios that I need some help figuring out the outcome of. Thank you in advance.
There exists two complexity classes $\mathsf{A}$ and $\mathsf{B}$. By ...
4
votes
1answer
179 views
What are the criteria for inviting conference papers (e.g. SODA) for special issue?
This is mostly for some immigration related document that I am trying to write and want to reference an online link which mentions that only a select few papers are invited for special issue for SODA ...
4
votes
1answer
185 views
Have fixed parameter integer program algorithms ever been implemented for research use?
Have any fixed parameter integer programming algorithms described in Integer programming with a fixed number of variables been implemented? Is there a reference code that researchers can use?
4
votes
1answer
203 views
Should one study undergrad TCS materials before taking grad-level ones? (soft question)
I am a 1st year PhD student. I got a bachelor's degree in CS but I didn't start learning TCS systematically until this year.
This dumb question came to me when I opened an undergrad complexity lecture ...
4
votes
1answer
192 views
Online TCS Seminars
I want to have a list of online seminars that holds now.
So far I know only about TCS+(https://sites.google.com/site/plustcs/) seminars.
I would like to ask if there are other TCS seminars.
4
votes
1answer
280 views
The Maxwell's Demon and Computer Science
What is the best source -in terms of quality- that would explain the argument that uses computations concepts to demonstrate that the Maxwell's Demon does not break the second law of thermodynamics? I ...
4
votes
1answer
354 views
Popular Journals for Theoretical CS
Are there some popular journals in the field of theoretical CS that serve the kind of purpose that a journal like "Physics Today" does for the Physics community ?
4
votes
2answers
510 views
How to do organize papers, urls and other TCS related resources?
This question is a try of making
Do you use any article organizers? question suitable for TCS (as suggested in meta answer https://cstheory.meta.stackexchange.com/a/359/6133 )
Question similar -> ...
4
votes
1answer
297 views
Canadian CS University Positions?
Does anyone know if there is a centralized source of Canadian positions advertised by universities for computer science? I conjecture that this might exist since there are websites advertising math ...
4
votes
1answer
155 views
What is the etiquette of naming concepts after people?
There is a concept introduced by other researchers that I use in my work, and IMO it is appropriate to rename it to honor the inventors. Is it considered normal to just go ahead and name it like that ...
4
votes
1answer
238 views
Surveys in other languages than English
Where can I find surveys in languages than English ?
If the question is found to be interesting (it could be usefull for graduated students who are not fluent in English for instance), it would be ...
4
votes
0answers
136 views
The graph of problem reductions
A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
4
votes
0answers
80 views
Status of the Junta Problem (soft question)
Does the learning theory community in general believe that juntas can be learned in polynomial time?
The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta ...
4
votes
0answers
194 views
Advice for new grad student [closed]
I'm a first year PhD student in a CS department at what some would probably consider a mid-tier university. I've been reading from Vershynin's High-Dimensional Probability and been trying to learn ...
4
votes
0answers
92 views
Naming an algorithm after a copyrighted object
In machine learning, it is common to give algorithms quirky names. What happens if you think you've found a name that's actually quite fitting for an algorithm (catchy, descriptive, etc) -- but turns ...
4
votes
0answers
122 views
major applied focuses of different proof assistants
Currently, what are the major applied focuses (if any applications can be deserved such a distinction) of different proof assistants, such as the following? If there are significant differences ...
4
votes
0answers
266 views
Faculty hiring differences between US and UK/Germany [closed]
This question contains some great answers on how to get a job. I wonder whether there are some significant differences if I will be looking for a position in Europe (in particular, UK and Germany) as ...
3
votes
5answers
1k views
Quality of a conference
I am a physicist working in TCS in a new group. I would like to know, given a conference (imagine your favorite ones), how can I know the quality of this conference and also the quality of the ...
3
votes
1answer
511 views
New theories and publications on computer science
When someone develops a new theory on computer science, specifically in artificial intelligence domain, which is barely on schetch (so there are no measurements, nor simulations, nor finished code or ...
