Stephan Schäperklaus<p>Solving P = NP would be a master key, but for what? <a href="https://mastodon.social/tags/PvsNP" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>PvsNP</span></a> <a href="https://mastodon.social/tags/ComplexityTheory" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>ComplexityTheory</span></a> <a href="https://mastodon.social/tags/CyberSecurity" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>CyberSecurity</span></a> <a href="https://mastodon.social/tags/AIResearch" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>AIResearch</span></a> <a href="https://mastodon.social/tags/Innovation" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Innovation</span></a> <a href="https://mastodon.social/tags/FutureOfTech" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>FutureOfTech</span></a> <a href="https://mastodon.social/tags/Mathematics" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Mathematics</span></a> <a href="https://mastodon.social/tags/TheoreticalComputerScience" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>TheoreticalComputerScience</span></a> <a href="https://mastodon.social/tags/Optimization" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>Optimization</span></a> <a href="https://mastodon.social/tags/DigitalInfrastructure" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>DigitalInfrastructure</span></a></p><p><a href="https://t.co/qgPMixQpt6" rel="nofollow noopener noreferrer" translate="no" target="_blank"><span class="invisible">https://</span><span class="">t.co/qgPMixQpt6</span><span class="invisible"></span></a></p>
Recent searches
No recent searches
Search options
Only available when logged in.
mathstodon.xyz is one of the many independent Mastodon servers you can use to participate in the fediverse.
A Mastodon instance for maths people. We have LaTeX rendering in the web interface!
Administered by:
Server stats:
2.8Kactive users
mathstodon.xyz: About · Status · Profiles directory · Privacy policy
Mastodon: About · Get the app · Keyboard shortcuts · View source code · v4.3.7
#theoreticalComputerScience
0 posts · 0 participants · 0 posts today
HoldMyType<p>Just because its turin complete and computable and can define bool/if-else, currying recursion, church numerals and exprs reduce correctly shouldnt mean that it can attribute a computational meaning to an otherwise absurd <a href="https://mathstodon.xyz/tags/math" class="mention hashtag" rel="tag">#<span>math</span></a> expression <br />Or should it?<br />My question is computational meaning even a thing ? If yes , how does that even relate to meaning applied math<br />I mean the count of 1 , 2, 3 can always be attributed to something g physically measurable <br /><a href="https://mathstodon.xyz/tags/theoreticalcomputerscience" class="mention hashtag" rel="tag">#<span>theoreticalcomputerscience</span></a> <br />-- noob</p>
Mark Gritter<p>Is there a meaningful way to characterize some "fastest growing function", subject to particular computational limitations? (I answered a question today that asked if all computable functions have polynomial bounds, which they obviously don't.)</p><p>We can't ask for the fastest-growing function in FP, because the composition of polynomial runtimes is polynomial. So if f(x) is in FP, so is the faster-growing f(f(x)).</p><p>Could we identify the fastest-growing function (using binary) in DTIME(n^2)? It seems like it would be something like "given an n-bit input, write n^2 1's after the input". So if the input was 2^a, we'd get 2^a * 2^(a^2) + (2^(a^2+1) - 1) as output.</p><p>But, strictly speaking, there would be a little bit of overhead meaning we couldn't do quite that well. The algorithm above is in DTIME(O(n^2)) but not DTIME(n^2). So it feels like there is a sequence of functions that converges on this one, but there might not be any best possible. And if we permit O(n^2) we're back to not having any fastest-growing function again because we can just slap bigger multiples on our allowed runtime.</p><p>So, is there a nontrivial class of computable functions that has an unambiguously fastest-growing member?</p><p><a href="https://mathstodon.xyz/tags/TheoreticalComputerScience" class="mention hashtag" rel="tag">#<span>TheoreticalComputerScience</span></a></p>
Clément Canonne<p>This Karp Distinguished Lecture at at the Simons Institute by Rocco Servedio on July 10 on "New Directions in Property Testing" looks exciting! Rocco is a fantastic speaker.<br /><a href="https://simons.berkeley.edu/events/new-directions-property-testing-richard-m-karp-distinguished-lecture" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">simons.berkeley.edu/events/new</span><span class="invisible">-directions-property-testing-richard-m-karp-distinguished-lecture</span></a></p><p>The Karp Lectures are public lectures, meant for a broad, general <a href="https://mathstodon.xyz/tags/TheoreticalComputerScience" class="mention hashtag" rel="tag">#<span>TheoreticalComputerScience</span></a> audience. Registration is free, in person or online.</p><p>To check your time zone: <a href="https://timeanddate.com/worldclock/converter.html?iso=20240710T223000&p1=tz_pt&p2=240&p3=195&p4=179&p5=438&p6=236" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">timeanddate.com/worldclock/con</span><span class="invisible">verter.html?iso=20240710T223000&p1=tz_pt&p2=240&p3=195&p4=179&p5=438&p6=236</span></a></p>
Joshua Moerman<p>Call for papers for the LearnAut (<a href="https://mathstodon.xyz/tags/Learning" class="mention hashtag" rel="tag">#<span>Learning</span></a> and <a href="https://mathstodon.xyz/tags/Automata" class="mention hashtag" rel="tag">#<span>Automata</span></a>) 2024 workshop co-located with ICALP/LICS/FSCD!</p><p>Please consider submitting your work. 😊</p><p>"The aim of this workshop is to bring together experts on <a href="https://mathstodon.xyz/tags/FormalLanguageTheory" class="mention hashtag" rel="tag">#<span>FormalLanguageTheory</span></a> that could benefit from <a href="https://mathstodon.xyz/tags/GrammaticalInference" class="mention hashtag" rel="tag">#<span>GrammaticalInference</span></a> tools, and researchers in grammatical inference who could find new insights for their methods in <a href="https://mathstodon.xyz/tags/TheoreticalComputerScience" class="mention hashtag" rel="tag">#<span>TheoreticalComputerScience</span></a>. [...] We do accept submissions of work recently published, currently under review or work-in-progress."</p><p><a href="https://learnaut24.github.io/" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">learnaut24.github.io/</span><span class="invisible"></span></a></p>
Clément Canonne<p>📢 Next week (Wed 12/13) on TCS+: at 10am PT/1pm ET, Aaron Bernstein from Rutgers University will speak on "Negative-Weight Single-Source Shortest Paths in Near-linear Time." Join us for the last TCS+ talk of 2023! <a href="https://mathstodon.xyz/tags/Algorithms" class="mention hashtag" rel="tag">#<span>Algorithms</span></a> <a href="https://mathstodon.xyz/tags/TheoreticalComputerScience" class="mention hashtag" rel="tag">#<span>TheoreticalComputerScience</span></a> </p><p>Details: <a href="https://tcsplus.wordpress.com/2023/12/06/tcs-talk-wednesday-december-13-aaron-bernstein-rutgers-university/" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">tcsplus.wordpress.com/2023/12/</span><span class="invisible">06/tcs-talk-wednesday-december-13-aaron-bernstein-rutgers-university/</span></a></p><p>Register (optional): <a href="https://docs.google.com/forms/d/e/1FAIpQLSdSrnuZ2jH8KGepSEJ0uz_iCRr7mJtMntIu6ZBsXIhhKovI6A/viewform" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">docs.google.com/forms/d/e/1FAI</span><span class="invisible">pQLSdSrnuZ2jH8KGepSEJ0uz_iCRr7mJtMntIu6ZBsXIhhKovI6A/viewform</span></a></p>
Mohammad Hajiaghayi<p>In our effort to put courses online, we continue lectures on Algorithmic Lower Bound Course. Now you can watch</p><p>Lesson 4-11: Algorithmic Lower Bounds by Mohammad Hajiaghayi - NP-Completeness and Beyond</p><p>(FEEL FREE TO SUBSCRIBE TO YOUTUBE @hajiaghayi FOR FUTURE LESSONS Premiering on WEDNESDAYS)</p><p><a href="https://youtu.be/VZyffnAb1r0" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/VZyffnAb1r0</span><span class="invisible"></span></a> (Lesson 4: 3-Partition Problem & Proving NP-Hardness)</p><p><a href="https://youtu.be/4fCD9_1eQw0" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/4fCD9_1eQw0</span><span class="invisible"></span></a> (Lesson 5: Puzzle Problem NP-Hardness & 3-Partition)</p><p><a href="https://youtu.be/FIyEj72-UJQ" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/FIyEj72-UJQ</span><span class="invisible"></span></a> (Lesson 6: 3-SAT Problem & Proving NP-Hardness)</p><p><a href="https://youtu.be/tbSJzaKx2pA" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/tbSJzaKx2pA</span><span class="invisible"></span></a> (Lesson 7: Puzzle Problem NP-Hardness via 3-SAT)</p><p><a href="https://youtu.be/voRVebBsh94" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/voRVebBsh94</span><span class="invisible"></span></a> (Lesson 8: Fine-grained Subcubic Complexity: Part 1)</p><p><a href="https://youtu.be/gRURSM6QARo" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/gRURSM6QARo</span><span class="invisible"></span></a> (Lesson 9: Fine-grained Subcubic Complexity: Part 2)</p><p><a href="https://youtu.be/qPw82bTAXkc" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/qPw82bTAXkc</span><span class="invisible"></span></a> (Lesson 10: Fine-grained Subquadratic Complexity 1)</p><p><a href="https://youtu.be/C6j4avVkI7U" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">youtu.be/C6j4avVkI7U</span><span class="invisible"></span></a> (Lesson 11: Fine-grained Subquadratic Complexity 2)</p><p><a href="https://mathstodon.xyz/tags/AlorithmicComplexity" class="mention hashtag" rel="tag">#<span>AlorithmicComplexity</span></a>, </p><p><a href="https://mathstodon.xyz/tags/3SAT" class="mention hashtag" rel="tag">#<span>3SAT</span></a>,</p><p><a href="https://mathstodon.xyz/tags/3Partition" class="mention hashtag" rel="tag">#<span>3Partition</span></a>,</p><p><a href="https://mathstodon.xyz/tags/subquadratic" class="mention hashtag" rel="tag">#<span>subquadratic</span></a>,</p><p><a href="https://mathstodon.xyz/tags/subcubic" class="mention hashtag" rel="tag">#<span>subcubic</span></a>,</p><p><a href="https://mathstodon.xyz/tags/Finegrained" class="mention hashtag" rel="tag">#<span>Finegrained</span></a>,</p><p><a href="https://mathstodon.xyz/tags/HardnessExploration" class="mention hashtag" rel="tag">#<span>HardnessExploration</span></a>, </p><p><a href="https://mathstodon.xyz/tags/NP" class="mention hashtag" rel="tag">#<span>NP</span></a>, </p><p><a href="https://mathstodon.xyz/tags/PSPACE" class="mention hashtag" rel="tag">#<span>PSPACE</span></a>, </p><p><a href="https://mathstodon.xyz/tags/NPComplete" class="mention hashtag" rel="tag">#<span>NPComplete</span></a>, </p><p><a href="https://mathstodon.xyz/tags/LogSpace" class="mention hashtag" rel="tag">#<span>LogSpace</span></a>, </p><p><a href="https://mathstodon.xyz/tags/ExponentialComplexity" class="mention hashtag" rel="tag">#<span>ExponentialComplexity</span></a>, </p><p><a href="https://mathstodon.xyz/tags/ParallelComputation" class="mention hashtag" rel="tag">#<span>ParallelComputation</span></a>, </p><p><a href="https://mathstodon.xyz/tags/PvsNP" class="mention hashtag" rel="tag">#<span>PvsNP</span></a>, </p><p><a href="https://mathstodon.xyz/tags/NPSPACE" class="mention hashtag" rel="tag">#<span>NPSPACE</span></a>, </p><p><a href="https://mathstodon.xyz/tags/NonDeterministicSpace" class="mention hashtag" rel="tag">#<span>NonDeterministicSpace</span></a>, hashtag</p><p><a href="https://mathstodon.xyz/tags/SavitchTheorem" class="mention hashtag" rel="tag">#<span>SavitchTheorem</span></a>, </p><p><a href="https://mathstodon.xyz/tags/ComplexityClasses" class="mention hashtag" rel="tag">#<span>ComplexityClasses</span></a>, </p><p><a href="https://mathstodon.xyz/tags/Reductions" class="mention hashtag" rel="tag">#<span>Reductions</span></a>, </p><p><a href="https://mathstodon.xyz/tags/ImportantProblems" class="mention hashtag" rel="tag">#<span>ImportantProblems</span></a>, </p><p><a href="https://mathstodon.xyz/tags/CommunicationComplexity" class="mention hashtag" rel="tag">#<span>CommunicationComplexity</span></a>, hashtag</p><p><a href="https://mathstodon.xyz/tags/GeometricProblems" class="mention hashtag" rel="tag">#<span>GeometricProblems</span></a>, </p><p><a href="https://mathstodon.xyz/tags/AlgorithmDesign" class="mention hashtag" rel="tag">#<span>AlgorithmDesign</span></a>, </p><p><a href="https://mathstodon.xyz/tags/ComputationalComplexity" class="mention hashtag" rel="tag">#<span>ComputationalComplexity</span></a>, </p><p><a href="https://mathstodon.xyz/tags/TheoreticalComputerScience" class="mention hashtag" rel="tag">#<span>TheoreticalComputerScience</span></a>, </p><p><a href="https://mathstodon.xyz/tags/AlgorithmicLowerBounds" class="mention hashtag" rel="tag">#<span>AlgorithmicLowerBounds</span></a></p><p>For comprehensive handwritten lecture notes on this course, visit the instructor's website:</p><p><a href="http://www.cs.umd.edu/~hajiagha/" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">http://www.</span><span class="">cs.umd.edu/~hajiagha/</span><span class="invisible"></span></a><br />The course textbook "Computational Intractability: A Guide to Algorithmic Lower Bounds" by Demaine, Gasarch, and Hajiaghayi is available for free at:</p><p><a href="https://hardness.mit.edu/" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">hardness.mit.edu/</span><span class="invisible"></span></a></p>
Clément Canonne<p>📢 Next week (Wed 9/27) at 10:00am PT, Hanlin Ren from Oxford will give the first TCS+ talk of the season, on "Polynomial-Time Pseudodeterministic Construction of Primes." <a href="https://mathstodon.xyz/tags/TheoreticalComputerScience" class="mention hashtag" rel="tag">#<span>TheoreticalComputerScience</span></a> </p><p>Details: <a href="https://tcsplus.wordpress.com/2023/09/20/tcs-talk-wednesday-september-27-hanlin-ren-university-of-oxford/" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">tcsplus.wordpress.com/2023/09/</span><span class="invisible">20/tcs-talk-wednesday-september-27-hanlin-ren-university-of-oxford/</span></a></p><p>Register (optional): <a href="https://docs.google.com/forms/d/e/1FAIpQLScenFfBzn6Kl45Y1reJAB08D1V4Sd_z0eQTgG76XsG4lpPV1w/viewform" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">docs.google.com/forms/d/e/1FAI</span><span class="invisible">pQLScenFfBzn6Kl45Y1reJAB08D1V4Sd_z0eQTgG76XsG4lpPV1w/viewform</span></a></p>
Ross Gayler<p>Here's a really interesting (long) paper on what a theory of computing based on arbitrary physical substrates might look like: <a href="http://arxiv.org/abs/2307.15408" rel="nofollow noopener noreferrer" target="_blank"><span class="invisible">http://</span><span class="">arxiv.org/abs/2307.15408</span><span class="invisible"></span></a></p><p>"Toward a formal theory for computing machines made out of whatever physics offers: extended version"</p><p>Herbert Jaeger, Beatriz Noheda, Wilfred G. van der Wiel (2023)</p><p><span class="h-card"><a href="https://mas.to/@bnoheda" class="u-url mention" rel="nofollow noopener noreferrer" target="_blank">@<span>bnoheda</span></a></span> </p><p><a href="https://aus.social/tags/NewPaper" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>NewPaper</span></a> <a href="https://aus.social/tags/TheoreticalComputerScience" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>TheoreticalComputerScience</span></a> <a href="https://aus.social/tags/neuromorphic" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>neuromorphic</span></a> <a href="https://aus.social/tags/CogSci" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>CogSci</span></a> <a href="https://aus.social/tags/CognitiveScience" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>CognitiveScience</span></a> <a href="https://aus.social/tags/VSA" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>VSA</span></a> <a href="https://aus.social/tags/VectorSymbolicArchitecture" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>VectorSymbolicArchitecture</span></a> <a href="https://aus.social/tags/HDC" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>HDC</span></a> <a href="https://aus.social/tags/HyperdimensionalComputing" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>HyperdimensionalComputing</span></a> <a href="https://aus.social/tags/AnalogComputing" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>AnalogComputing</span></a></p>
Ross Gayler<p>Collective <a href="https://aus.social/tags/math" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>math</span></a> / <a href="https://aus.social/tags/TheoreticalComputerScience" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>TheoreticalComputerScience</span></a> memory question: Sometime in the last couple of months I followed a link from Masto to a blog post about computing (in the most general sense) defined as continuous rather than discrete mathematics. This blog post mentioned (with references) that having *partial* functions was essential for computation.</p><p>Now I can't find the blog post or references. Any pointers to works explaining why partial functions are essential to computation (or refutation) would be greatly appreciated.</p>
e7_87<p>ChatGPT introduces me a branch of <a href="https://mathstodon.xyz/tags/theoreticalComputerScience" class="mention hashtag" rel="tag">#<span>theoreticalComputerScience</span></a> called "<a href="https://mathstodon.xyz/tags/gameSemantics" class="mention hashtag" rel="tag">#<span>gameSemantics</span></a>" today!</p><p><a href="https://mathstodon.xyz/tags/gameTheory" class="mention hashtag" rel="tag">#<span>gameTheory</span></a></p>
Clément Canonne<p><span class="h-card" translate="no"><a href="https://mathstodon.xyz/@Jose_A_Alonso" class="u-url mention">@<span>Jose_A_Alonso</span></a></span> <a href="https://mathstodon.xyz/tags/ComputationalComplexity" class="mention hashtag" rel="tag">#<span>ComputationalComplexity</span></a> <a href="https://mathstodon.xyz/tags/theoreticalComputerScience" class="mention hashtag" rel="tag">#<span>theoreticalComputerScience</span></a> <a href="https://mathstodon.xyz/tags/TCS" class="mention hashtag" rel="tag">#<span>TCS</span></a> <a href="https://mathstodon.xyz/tags/phdPosition" class="mention hashtag" rel="tag">#<span>phdPosition</span></a></p>
Clément Canonne<p>Very nice and clear article by <span class="h-card" translate="no"><a href="https://sciencemastodon.com/@benbenbrubaker" class="u-url mention">@<span>benbenbrubaker</span></a></span> on <span class="h-card" translate="no"><a href="https://mstdn.social/@QuantaMagazine" class="u-url mention">@<span>QuantaMagazine</span></a></span>, describing the meaning and implications of the latest advances regarding random <a href="https://mathstodon.xyz/tags/quantum" class="mention hashtag" rel="tag">#<span>quantum</span></a> circuit sampling: <br /><a href="https://www.quantamagazine.org/new-algorithm-closes-quantum-supremacy-window-20230109/" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://www.</span><span class="ellipsis">quantamagazine.org/new-algorit</span><span class="invisible">hm-closes-quantum-supremacy-window-20230109/</span></a></p><p>Heck, I felt I understood something! <a href="https://mathstodon.xyz/tags/TheoreticalComputerScience" class="mention hashtag" rel="tag">#<span>TheoreticalComputerScience</span></a> <a href="https://mathstodon.xyz/tags/TCS" class="mention hashtag" rel="tag">#<span>TCS</span></a> <a href="https://mathstodon.xyz/tags/ComputationalComplexity" class="mention hashtag" rel="tag">#<span>ComputationalComplexity</span></a></p>
Clément Canonne<p>ICYMI, there's been a series of online talks on "adversarially robust streaming <a href="https://mathstodon.xyz/tags/algorithms" class="mention hashtag" rel="tag">#<span>algorithms</span></a>" on the Foundations of <a href="https://mathstodon.xyz/tags/DataScience" class="mention hashtag" rel="tag">#<span>DataScience</span></a> virtual seminar series. The first 3 recordings are available:<br /><a href="https://sites.google.com/view/dstheory/past-talks_1" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">sites.google.com/view/dstheory</span><span class="invisible">/past-talks_1</span></a> </p><p>David Woodruff on "Adversarially Robust Streaming Algorithms"</p><p>Edith Cohen "On Robustness to Adaptive Inputs: A Case Study of CountSketch"</p><p>Omri Ben-Eliezer on "Robust sampling and online learning"</p><p>(one or two more to come this semester!) <a href="https://mathstodon.xyz/tags/TheoreticalComputerScience" class="mention hashtag" rel="tag">#<span>TheoreticalComputerScience</span></a> <a href="https://mathstodon.xyz/tags/TCS" class="mention hashtag" rel="tag">#<span>TCS</span></a> <a href="https://mathstodon.xyz/tags/talks" class="mention hashtag" rel="tag">#<span>talks</span></a></p>
Clément Canonne<p>Hey, that seems cool!* Zero-Knowledge proofs in the streaming setting (verifier has limited working memory, gets one pass over the input). <br /><a href="https://arxiv.org/abs/2301.02161" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="">arxiv.org/abs/2301.02161</span><span class="invisible"></span></a><br />By Cormode, Dall’Agnol, <span class="h-card" translate="no"><a href="https://qubit-social.xyz/@tomgur" class="u-url mention">@<span>tomgur</span></a></span>, and Hickey. <a href="https://mathstodon.xyz/tags/TCS" class="mention hashtag" rel="tag">#<span>TCS</span></a> <a href="https://mathstodon.xyz/tags/arXiv" class="mention hashtag" rel="tag">#<span>arXiv</span></a> <a href="https://mathstodon.xyz/tags/TheoreticalComputerScience" class="mention hashtag" rel="tag">#<span>TheoreticalComputerScience</span></a> </p><p>* Except for the default bright green color of the links, that is :)</p>
Stephan Beyer<p>Oh, polynomial3sat.org is down and the respective code on GitHub is removed. The corresponding paper on arXiv is still accessible. Does anyone know more about what happened?</p><p><a href="https://arxiv.org/abs/1903.10081" rel="nofollow noopener noreferrer" target="_blank"><span class="invisible">https://</span><span class="">arxiv.org/abs/1903.10081</span><span class="invisible"></span></a></p><p><a href="https://hachyderm.io/tags/satsolving" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>satsolving</span></a> <a href="https://hachyderm.io/tags/complexitytheory" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>complexitytheory</span></a> <a href="https://hachyderm.io/tags/PequalsNP" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>PequalsNP</span></a> <a href="https://hachyderm.io/tags/compsci" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>compsci</span></a> <a href="https://hachyderm.io/tags/theoreticalcomputerscience" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>theoreticalcomputerscience</span></a></p>
Clément Canonne<p>I have been making an online <a href="https://mathstodon.xyz/tags/weaeklyquiz" class="mention hashtag" rel="tag">#<span>weaeklyquiz</span></a> 📊 in <a href="https://mathstodon.xyz/tags/TheoreticalComputerScience" class="mention hashtag" rel="tag">#<span>TheoreticalComputerScience</span></a> and <a href="https://mathstodon.xyz/tags/maths" class="mention hashtag" rel="tag">#<span>maths</span></a> for more than 3 years now: first on Twitter weekly, now fortnightly both there and here on Mastodon. If you're interested, all the <a href="https://mathstodon.xyz/tags/quiz" class="mention hashtag" rel="tag">#<span>quiz</span></a> threads and their answers are listed here: <br /><a href="https://ccanonne.github.io/weeklyquiz.html" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">ccanonne.github.io/weeklyquiz.</span><span class="invisible">html</span></a></p>
Clément Canonne<p>This season of TCS+ has concluded, with 7 talks (including two Test-of-Time surveys), which you can (re)watch at will on the TCS+ website! <a href="https://tcsplus.org/welcome/past-talks/2022-2023" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">tcsplus.org/welcome/past-talks</span><span class="invisible">/2022-2023</span></a> 📽️</p><p>We're going to decide on next semester's speakers very soon, so if you have suggestions, please send them through: <a href="https://tcsplus.org/welcome/suggest-a-talk" target="_blank" rel="nofollow noopener noreferrer" translate="no"><span class="invisible">https://</span><span class="ellipsis">tcsplus.org/welcome/suggest-a-</span><span class="invisible">talk</span></a></p><p>See you next year, and Happy Holidays! 🎉 <a href="https://mathstodon.xyz/tags/TheoreticalComputerScience" class="mention hashtag" rel="tag">#<span>TheoreticalComputerScience</span></a> <a href="https://mathstodon.xyz/tags/seminars" class="mention hashtag" rel="tag">#<span>seminars</span></a> <a href="https://mathstodon.xyz/tags/talks" class="mention hashtag" rel="tag">#<span>talks</span></a></p>
Lenore Blum<p>Manuel Blum and I study <a href="https://sigmoid.social/tags/consciousness" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>consciousness</span></a> from a <a href="https://sigmoid.social/tags/TheoreticalComputerScience" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>TheoreticalComputerScience</span></a> (TCS) perspective. <br> TCS is a branch of <a href="https://sigmoid.social/tags/mathematics" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>mathematics</span></a> concerned with understanding the underlying principles of <a href="https://sigmoid.social/tags/computation" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>computation</span></a> and <a href="https://sigmoid.social/tags/complexity" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>complexity</span></a>, including the implications and surprising consequences of resource limitations. <br> For a TCS perspective on <a href="https://sigmoid.social/tags/consciousness" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>consciousness</span></a>, see, <a href="https://bit.ly/38zAhf6" rel="nofollow noopener noreferrer" target="_blank"><span class="invisible">https://</span><span class="">bit.ly/38zAhf6</span><span class="invisible"></span></a> <br> For a TCS perspective on <a href="https://sigmoid.social/tags/FreeWill" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>FreeWill</span></a>, see, <a href="https://arxiv.org/pdf/2206.13942.pdf" rel="nofollow noopener noreferrer" target="_blank"><span class="invisible">https://</span><span class="">arxiv.org/pdf/2206.13942.pdf</span><span class="invisible"></span></a></p>
Clément Aubert<p>Is there a canonical term for "either coinitial or composable <a href="https://lipn.info/tags/traces" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>traces</span></a>"? Concomitant? Adjacent? <a href="https://lipn.info/tags/TheoreticalComputerScience" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>TheoreticalComputerScience</span></a> <a href="https://lipn.info/tags/CS" class="mention hashtag" rel="nofollow noopener noreferrer" target="_blank">#<span>CS</span></a></p>
SearchLive feeds
Mastodon is the best way to keep up with what's happening.
Follow anyone across the fediverse and see it all in chronological order. No algorithms, ads, or clickbait in sight.
Create accountLoginDrag & drop to upload