See full post

Cem Say

Followers · Following

Bilgisayar Mühendisliği hocası

Joined December 2023

Posts Replies Media Original posts Likes

Cem Say handle.invalid · Dec 15, 2025
New paper alert! We (Utkan Gezer & me) prove that interactive proof systems whose verifiers are polynomial-time constant-space machines that are allowed to hide a constant number of their random bits correspond precisely to the complexity class P. DMTCS link: dmtcs.episciences.org/paper/view/i...
$\rm P$ has polynomial-time finite-state verifiers

Interactive proof systems whose verifiers are constant-space machines have interesting features that do not have counterparts in the better studied case where the verifiers operate under reasonably large space bounds. The language verification power of finite-state verifiers is known to be sensitive to the difference between private and public randomization. These machines also lack the capability of imposing worst-case superlinear bounds on their own runtime, and long interactions with untrustable provers can involve the risk of being fooled to loop forever. We analyze such verifiers under different bounds on the numbers of private and public random bits that they are allowed to use. This separate accounting for the private and public coin budgets as resource functions of the input length provides interesting characterizations of the collections of the associated languages. When the randomness bound is constant, the verifiable class is $\rm NL$ for private-coin machines, but equals just the regular languages when one uses public coins. Increasing the public coin budget while keeping the number of private coins constant augments the power: We show that the set of languages that are verifiable by such machines in expected polynomial time (with an arbitrarily small positive probability of looping) equals the complexity class $\rm P$. This hints that allowing a minuscule probability of looping may add significant power to polynomial-time finite-state automata, since it is still not known whether those machines can verify all of $\rm P$ when required to halt with probability 1, even with no bound on their private coin usage. We also show that logarithmic-space machines which hide a constant number of their coins are limited to verifying the languages in $\rm P$.

dmtcs.episciences.org

View on Bluesky Show all post labels

Cem Say handle.invalid · Dec 10, 2025
Boğaziçi Üniversitesi Mühendislik Fakültesi profesörlerinin Fakülte Kurulunda boş olan profesör temsilciliği için seçim yapmalarının engellenmesi yargıdan döndü. Mahkeme, dekanın seçimi yaptırmasının zorunlu olduğuna karar verdi. Kararın bir ay içinde uygulanması gerekiyor.

View on Bluesky Show all post labels

Cem Say handle.invalid · Nov 26, 2025
New paper alert! I prove the existence of two infinite hierarchies of time complexity classes of problems solvable by small-space quantum computers, and provide an improved polynomial-time quantum advantage result. Gift link (until Jan. 15): kwnsfk27.r.eu-west-1.awstrack.me/L0/https:%2F...
https://kwnsfk27.r.eu-west-1.awstrack.me/L0/https:%2F%2Fauthors.elsevier.com%2Fa%2F1mAKq15DaIMJN6/1/0102019abf5cb143-bfd60eb7-a3f0-40bf-af1a-8fabe4098576-000000/1Bxm3XYZiWvxq3JMKxTRYw5I_8M=454

kwnsfk27.r.eu-west-1.awstrack.me

View on Bluesky Show all post labels

Cem Say handle.invalid · Oct 23, 2025
www.cumhuriyet.com.tr/yazarlar/bar...
Barış Terkoğlu yazdı : Boğaziçi’ni nasıl çökerttiler | Cumhuriyet

Kime söylendiği belirsizse en ağır sözler bile havada kalır. En son Yargıtay başkanı konuştu. AYM kararlarının uygulanmamasını eleştirdi. Başkan haklı

cumhuriyet.com.tr

View on Bluesky Show all post labels

Reposted by Cem Say
cncndn cncndn.bsky.social · Oct 22, 2025
[Not loaded yet]

View on Bluesky Show all post labels

Reposted by Cem Say
tinkel tinkel@mastodon.social · Aug 28, 2025
[Not loaded yet]

View on Bluesky Show all post labels

Cem Say handle.invalid · Jul 17, 2025

View on Bluesky Download image Show all post labels

Reposted by Cem Say
Ekrem İmamoğlu ekremimamoglu.com · Jun 29, 2025
Bu topraklarda ne sökmez biliyor musunuz? Namertlik sökmez namertlik…

View on Bluesky Download video Show all post labels

Cem Say handle.invalid · Jun 29, 2025
Boğaziçi Ü. yönetiminin bir hukuksuzluğu daha mahkemeden döndü: Seçilmiş üyesi olduğu Senato toplantısına girmesi güvenlik görevlilerine engelletilen Prof. Dr. Ünal Zenginobuz'un açtığı davada yürütmeyi durdurma kararı çıktı; o Senato toplantısında alınan tüm kararlar iptal oldu. 🇹🇷🏆💝⚖️
Boğaziçi Üniversitesi’nde senato üyesi Prof. Dr. Zenginobuz’un alınmadığı toplantının yürütmesi durduruldu; "Küçüğünden büyüğüne birçok karar boşa düştü"

Boğaziçi Üniversitesi’nde senato üyesi Prof. Dr. Zenginobuz’un alınmadığı toplantının yürütmesi durduruldu; "Küçüğünden büyüğüne birçok karar boşa düştü"

t24.com.tr

View on Bluesky Show all post labels

Cem Say handle.invalid · Jun 15, 2025
Babam Cemil Say, 13 Kasım 1937'de Atatürk'ün kendi türettiği Türkçe terimlerle geometri dersi verdiği Sivas Lisesi 9-A sınıfı öğrencilerindendi. Büyük bir mutlulukla anlatırdı. Onların izinden gidiyoruz. #BabalarGünü

View on Bluesky Show all post labels

Cem Say handle.invalid · Jun 12, 2025
Hani Boğaziçi Üniversitesi Bilgisayar Mühendisliği Bölümü Bilgisayar Bilimleri Anabilim Dalı Başkanlığından hukuksuzca alınmış, mahkeme kararıyla geri gelmiş, ertesi gün yine görevden alınmış, yine dava açmış, sonunda tekrar seçilip görevime dönmüştüm ya? Bilin bakalım ne oldu 😃

View on Bluesky Show all post labels

Cem Say handle.invalid · May 22, 2025
Kanuna göre Türkiye'de bütün üniversitelerde profesörler Fakülte Kuruluna katılacak temsilcilerini seçimle belirler. Bilin bakalım Boğaziçi Üniversitesi Mühendislik Fakültesinde kim aday oldu diye yasa çiğnenerek 6 aydır seçim yaptırılmıyor?

View on Bluesky Show all post labels

Cem Say handle.invalid · May 14, 2025
New paper on sublogarithmic-space quantum Merlin-Arthur: arxiv.org/abs/2505.084...
Short and useful quantum proofs for sublogarithmic-space verifiers

Quantum Merlin-Arthur proof systems are believed to be stronger than both their classical counterparts and ``stand-alone'' quantum computers when Arthur is assumed to operate in $Ω(\log n)$ space. No ...

arxiv.org

View on Bluesky Show all post labels

Reposted by Cem Say
Ekrem İmamoğlu ekremimamoglu.com · May 10, 2025
Özledim Anne

View on Bluesky Download video Show all post labels

Cem Say handle.invalid · Apr 14, 2025
Our paper "Unconditional Proofs of Quantumness Between Small-Space Machines" (with Utkan Gezer) has just been published in Quantum Information & Computation. Comments welcome. Here is the link: sciendo.com/article/10.2...
Unconditional Proofs of Quantumness Between Small-Space...

A proof of quantumness is a protocol through which a classical machine can test whether a purportedly quantum device, with comparable time and...

sciendo.com

View on Bluesky Show all post labels

Reposted by Cem Say
fırat fıstık firatfstk.bsky.social · Apr 9, 2025
[Not loaded yet]

View on Bluesky Show all post labels

Reposted by Cem Say
cankakisim cankakisim.bsky.social · Apr 5, 2025
[Not loaded yet]

View on Bluesky Show all post labels

Reposted by Cem Say
Ekrem İmamoğlu ekremimamoglu.com · Apr 4, 2025
[Not loaded yet]

View on Bluesky Show all post labels

Reposted by Cem Say
Erevis handle.invalid · Apr 3, 2025
[Not loaded yet]

View on Bluesky Show all post labels

Cem Say handle.invalid · Mar 28, 2025
New paper; comments welcome.
- cscc-bot cscc-bot.bsky.social · Mar 28, 2025
  [Not loaded yet]
View on Bluesky Show all post labels

Cem Say handle.invalid · Feb 20, 2025
Bugün. 1024. kez.

View on Bluesky Download video Show all post labels

Cem Say handle.invalid · Feb 15, 2025

View on Bluesky Download image Show all post labels

Cem Say handle.invalid · Feb 12, 2025
Bu ülkenin en çalışkan gençlerinin torpilsiz hocalardan nitelikli eğitim alabildikleri gerçek, özgür, özerk bir üniversiteleri olabilsin diye.

View on Bluesky Download video Show all post labels

Cem Say handle.invalid · Feb 7, 2025

View on Bluesky Download image Show all post labels

Cem Say handle.invalid · Jan 21, 2025
20 Ocak 2025. 1001. kez.

View on Bluesky Download image Show all post labels

Reposted by Cem Say
Lance Fortnow lance.fortnow.com · Jan 15, 2025
[Not loaded yet]

View on Bluesky Show all post labels

Cem Say handle.invalid · Jan 16, 2025
Bugün. 999. kez.

View on Bluesky Download image Show all post labels

Cem Say handle.invalid · Jan 15, 2025
Bugün. 998. kez.

View on Bluesky Download image Show all post labels

Cem Say handle.invalid · Jan 9, 2025
Bugün.

View on Bluesky Download image Show all post labels

Cem Say handle.invalid · Jan 6, 2025
Bugün.

View on Bluesky Download image Show all post labels

Cem Say handle.invalid · Jan 3, 2025
Bugün. Beşinci yıldayız. #ÖzerkÖzgürDemokratikÜniversite için #KabulEtmiyoruzVazgeçmiyoruz

View on Bluesky Download image Show all post labels

Reposted by Cem Say
Clément Canonne ccanonne.github.io · Nov 27, 2024
[Not loaded yet]

View on Bluesky Show all post labels

An unhandled error has occurred. Reload 🗙