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.

Filter by
Sorted by
Tagged with
9
votes
1answer
428 views

Understanding the talks in Conferences and Workshops

I am a graduate student from India. I am very much interested in attending the Workshops, conferences, and invited lecturers given by prominent professors. At the end of the talk as usual some people ...
9
votes
1answer
462 views

Is there a relationship between computational complexity theory and complex systems theory?

Computational complexity theory classifies problems according to their inherent difficulty. Complex systems theory addresses systems that exhibit behaviours that do not obviously arise from the ...
9
votes
1answer
354 views

How do you remember parameters?

I'm currently doing research in pseudorandomness, which involves a zoo of wonderful objects such as pseudorandom generators, randomness extractors, expander graphs, etc. I find it a fascinating topic, ...
8
votes
3answers
2k views

P vs NP: Instructive example of when Brute Force search can be avoided

To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately ...
8
votes
5answers
807 views

Are there any schools with researchers interested in cellular automata?

I have been working on an independant project focusing on cellular automata and was wondering if this might be something that I could continue on in graduate school somewhere. I've seen some ...
8
votes
3answers
749 views

Monitoring PhD positions in TCS

Are there any ways of getting to know about new PhD positions in TCS other then just looking trough ubniversity/research groups web sites? Maybe people from different branches (type theory, ...
8
votes
1answer
587 views

Connections between the Erdos Discrepancy Problem and (Theoretical) CS?

Recently there have been some new results on computer-based experimental study of the Erdos Discrepancy Problem (EDP) (via SAT solvers, cited below). This problem has been cited and studied by several ...
8
votes
1answer
397 views

Is it a bad idea to critique someone's paper in my first publication?

I am currently facing a situation that I am not sure how to handle. Basically, there is this problem $A$. Problem $A$ has been a hot topic in the past $5$ years. Last year, a paper was published in ...
8
votes
1answer
1k views

Accomplished autodidact theoretical computer scientists

While it is very common to see successful autodidact musicians, painters, authors and architects - I am not familiar with any famous autodidacts in the field of TCS. Are there any examples of an ...
8
votes
2answers
766 views

How would a theory of computation course that culminated in lambda-calculus as “the” model of computation, instead of Turing machines, look like?

Currently, our ToC (Theory of Computation) courses are designed with the following progression of topics: Finite automata and regular languages Pushdown automata and context-free languages Turing ...
8
votes
1answer
385 views

Recent Probabilistic Methods in Combinatorics and its appplications to Complexity Theory

I read the famous book by Alon and Spencer on the probabilistic method in combinatorics. Is there a survey or lecture notes on recent advances and relationships with the following complexity ...
8
votes
1answer
514 views

Papers on Prolog-like languages without closed world assumption (CWA)

Prolog execution process may be seen as a search that model scientific search for a proof of a proposition. At the same time, real world scientific search greatly differs from Prolog search in the ...
8
votes
0answers
137 views

How to succeed in remote TCS research as undergraduate

I am participating in a remote summer research program in theoretical computer science due to the current pandemic. I recognize that given the current situation, it may be harder to collaborate with ...
8
votes
0answers
644 views

Why is single authorship so common among breakthrough papers in computer science?

Looking at the list of important papers in computer science one notices that the majority are authored by a single author. Those include classic papers of Turing, Shannon, Karp and Cook. Cook's solo ...
7
votes
6answers
2k views

“The Solution Problem” - How to get credit for your work as an undergrad?

I have come to a rather startling discovery in regards to a question that has been posed to me a number of times through my now almost 1 year of CS studies. Solving this problem is of great interest ...
7
votes
4answers
859 views

Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus?

I know very little about what I am talking about in what follows, so I appreciate any all help in pointing out all of my mistakes -- otherwise I won't be able to learn more and advance in my knowledge ...
7
votes
5answers
572 views

What is a substantial contribution to software design, with respect to authorship?

Background I am a biologist. I wrote and am about to submit a manuscript that describes a statistical analysis of computer model; it is a statistical methods and modeling paper. After my manuscript ...
7
votes
3answers
498 views

How do you go from insights to formal solutions?

My question pertains to the problem of translating ideas and insights to the solution (of some problem) into formal notations, thus expressing the answer formally. In other words, having a bunch of ...
7
votes
5answers
2k views

Is a CS degree for me?

I'm a UK student who will soon be going to university and would like some advice from people who have already done this on what course to take. I really enjoy the theoretical side of computer ...
7
votes
4answers
307 views

Proofs on unconventional computing

Are there any interesting proofs on unconventional computing? When reading on the topic I most often see soft analysis – like following paragraph from Wikipedia (Natural computing): Swarm ...
7
votes
3answers
700 views

Different definitions of complexity

I'm a math student and have encountered the concept of (mainly time) complexity of algorithms in several courses so far (Analysis of Algorithms, Cryptography, Numerical Analysis). However what strikes ...
7
votes
3answers
709 views

How to efficiently read the theoretical computer science research papers?

I am a computer science graduate student works in theory. The general advice is to go through the paper and then in the second or third round try to understand the detail. Read the abstract, ...
7
votes
3answers
772 views

What is the importance of a TCS researcher in a mostly applied CS department?

Stating the title in another way, how to convince a strong applied CS department that a theorist would be a better choice than one more applied computer scientist? I understand that it is natural for ...
7
votes
2answers
1k views

Deciding between different PhD programs

Edited Version What are the main characteristics and qualities that you would consider if you were going to choose a PhD program in theoretical computer science (or related areas) today (based on ...
7
votes
1answer
303 views

How to be formal while writing papers?

I am just beginning my second year of PhD. While my advisor is largely happy with my progress and work, there seems to be a recurring point in our discussions that I need to be more formal in my ...
7
votes
3answers
824 views

Do you use any article organizers? [closed]

There is an increasing number of scientific articles which I look through and somehow I feel a lack of a tool to keep track of the already read ones and my summary notes on it. Or another usage ...
7
votes
1answer
224 views

Where do people publish/submit their work on type theory?

Besides the most common venues (perhaps POPL, ICFP, LICS and FSCD), where else are papers on type theory commonly published? Especially, I'm looking for more "pure mathematical" venues/journals which ...
7
votes
2answers
463 views

A System for Visualizing Bibliography Information

I'm looking for a software for visualizing main trends in some field. Specifically, I want it to build a graph of the field with vertexes representing papers and edges representing how close papers ...
7
votes
1answer
294 views

(Self-)citation etiquette

This is particularly pertinent to the CS culture, where competitive conferences are often the main publication unit, which are then (sometimes) followed by journal versions. Suppose that a paper was ...
7
votes
4answers
600 views

Explaining computer science algorithms/concepts/ideas using metaphors

Recently I found an interesting algorithm book entitled 'Explaining Algorithms Using Metaphors' (Google books) by Michal Forišek and Monika Steinová. "Good" metaphors help people understand and even ...
7
votes
1answer
1k views

TCS online library

My question isn't really related to TCS itself, it's more about technical and informational equipment of a computer scientist. There is a website SafariBooksOnline by O'Reilly Media where anyone can ...
7
votes
0answers
177 views

Tortoise and hare algorithms

Consider the problem: Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$. This problem has a stunning solution running ...
7
votes
0answers
224 views

Low barrier to entry Computational Complexity problems

I could use some help navigating which areas of Computational Complexity (e.g. CCC, STOC topics) require the least amount of background knowledge to get involved in basic research. I am looking to ...
7
votes
0answers
306 views

Awards, grants and fellowships for PhD students in TCS

I think that a PhD student that received some awards and fellowships has better chance to get a good postdoc position. I was wondering what awards/grants/fellowships should one consider to apply for? ...
7
votes
0answers
540 views

Does a depth knowledge on theory of computation helps to be a better practitioner

I would like to know whether knowledge of the theory of computation can help you to be a better practitioner. Is it enough to obtain some depth of knowledge of algorithms and data structures, or would ...
6
votes
5answers
4k views

How to make a paper stronger?

After reading this question and David's answer I thought a more general question asking for tips would be useful. So how can authors make (and write) a paper stronger?
6
votes
2answers
1k views

If you have a casual conversation with someone and it leads to a paper, what do you owe them?

What if you had a casual conversation with someone, and that conversation lead to your findings? What do you owe them? When is it plagiarism? I read somewhere that "first to submit, wins" - so ...
6
votes
1answer
410 views

How to format author information in research papers?

Is there any standard style for adding author information in research papers? I see different papers use different styles. Some have affiliation and contact address only. Some have affiliation, email, ...
6
votes
1answer
466 views

Is it considered OK to email authors to inquire about their paper while subreviewing their paper for a conference?

More generally, how do you reconcile questions that you may have about the paper's technical material?
6
votes
2answers
627 views

Funding opportunities for non-european people going to Europe for a PhD in TCS

There are two chinese students who would like to come to Spain to pursue a PhD in TCS in our group. I know of course the funding possibilities in my country but wonder if you know any European and non-...
6
votes
1answer
317 views

Is the basis of parity functions the only orthonormal basis for Boolean functions?

Is there another orthonormal basis of functions for Boolean functions? Or, more specifically, besides the parity functions, is there another explicit function (which is common and has a name) that can ...
6
votes
1answer
292 views

Are there works on “quantum parametrized complexity”?

I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. I don't know if researchers in quantum complexity have started using ...
6
votes
3answers
2k views

Mathematical background needed for pursuing a PhD in TCS [duplicate]

Possible Duplicate: What kind of mathematical background is needed for complexity theory? I'm a final year undergrad and I'm looking to pursue a PhD in theoretical computer science in the long ...
6
votes
2answers
531 views

Is getting post-doc difficult in theoretical computer science with few published papers? [closed]

I am a Ph.D student ( expected to graduate in few months ) works in computational mathematics. In my PhD, I have published just couple of research papers. I am willing to go for a post-doc( US, Europe,...
6
votes
1answer
448 views

Physics and TCS

I was curious as to the ability to move between different academic disciplines with an advanced degree in TCS. So would I be able to move, with a little bit of elbow grease, between physics and ...
6
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 ...
6
votes
2answers
489 views

(concise?) definition of thread safety

Wikipedia has the following definition: Thread safety is a computer programming concept applicable in the context of multi-threaded programs. A piece of code is thread-safe if it only ...
6
votes
1answer
268 views

Advice on undergraduate research

I am a junior in college who is very interested in doing some sort of REU/research internship in theoretical computer science this summer, as I would like to get research experience before potentially ...
6
votes
2answers
455 views

Could any one enumerate some applications of enumerative combinatorics and Ramsey theory in TCS?

The combinatorics, needless to say, is very closely related to TCS. But I found it hard to find the applications of enumerative combinatorics or Ramsey theory. Or rather than being applied to TCS, ...
6
votes
0answers
314 views

What is the current status of Acta Informatica?

Almost everybody knows the journal Acta Informatica. Some really important publications appeared there over the years. Upon looking on the website of the journal I noticed the following: Number of ...

1
4
5
6 7 8