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.
391
questions
6
votes
0answers
901 views
What should I do to switch from math department to cs to research tcs topics?
This can be a very weird question, but I haven't seen the same situation with mine in this forum, so I'd like to put this. Let me introudce my situation first.
I'm now a math student of master ...
6
votes
0answers
292 views
Formula in common: How to search for same/similar equations in other knowledge domains?
In a recent presentation by Sedgewick, he recounts in 1977 Flajolet noticed that they had a formula in common, both in different domains (see slide 4 in http://www.cs.princeton.edu/~rs/talks/AofA2AC....
6
votes
0answers
421 views
What is the origin and meaning of the phrase “Lambda the ultimate?”
I've been messing around with functional programming languages for a few years, and I keep encountering this phrase.
I understand what lambda means, the idea of an anonymous function is both simple ...
6
votes
0answers
530 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
459 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.3k4 gold badges56 silver badges143 bronze badges
5
votes
2answers
476 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
576 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
924 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
820 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
257 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
252 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
4k 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
3answers
443 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
249 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
422 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
462 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
127 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
168 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
136 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
609 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
157 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
501 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
530 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
363 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
753 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
766 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
179 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
296 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
189 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
190 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
211 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
204 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
290 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
363 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
157 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
81 views
Simple randomized priority queue matching the Fibonacci heap time bounds?
Since the Fibonacci heap was developed, many other priority queues have been invented with equivalent time bounds and a simpler design (e.g. hollow heaps, quake heaps, etc.).
Many classical worst-case ...
4
votes
0answers
166 views
What kind of research can be considered publishable for undergraduate or graduate students (MSc level)
I'am currently doing a non-research Dipl.Eng (Engineering Diploma in French school system equivalent to MSc) in Computer Science.
The courses I am currently taking are software oriented, there's an ...
4
votes
0answers
150 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
89 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
201 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
95 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 ...
