Cem Say
banner
saycem.bsky.social
Cem Say
@saycem.bsky.social
Bilgisayar Mühendisliği hocası
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
December 15, 2025 at 9:48 PM
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.
December 10, 2025 at 6:50 AM
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...
kwnsfk27.r.eu-west-1.awstrack.me
November 26, 2025 at 6:33 PM
Reposted by Cem Say
21 Ekim 2025 Boğaziçi Üniversitesi Akademisyenleri Nöbeti no. 1179. Direnişin 5. yılı/1752. günü Boğaziçi Üniversitesi'nde #KabulEtmiyoruzVazgeçmiyoruz
October 21, 2025 Boğaziçi University Faculty Vigil #1179/5th year/1752nd day of the resistance. At Boğaziçi Univ. #WeDoNotAcceptWeDoNotGiveUp!
October 22, 2025 at 10:50 AM
July 17, 2025 at 4:48 PM
Reposted by Cem Say
Bu topraklarda ne sökmez biliyor musunuz? Namertlik sökmez namertlik…
June 29, 2025 at 6:26 AM
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
June 29, 2025 at 1:54 PM
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ü
June 15, 2025 at 9:06 AM
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 😃
June 12, 2025 at 6:17 PM
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?
May 22, 2025 at 11:20 AM
Reposted by Cem Say
Özledim Anne
May 10, 2025 at 7:27 PM
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
April 14, 2025 at 10:18 AM
Reposted by Cem Say
istanbul 6. asliye ceza mahkemesinden örnek karar.
tutuklu olan 5 genç hakkında 2911 sayılı yasanın alt ve üst sınırı da göz önünde bulundurularak tahliye kararı verildi.
April 9, 2025 at 7:51 PM
Reposted by Cem Say
Bugün Ekrem İmamoğlu'na destek vermek için Türk öğrenciler değerli bir etkinlik düzenlemişler. Eyleme Bologna Belediye Başkanı da katılmış ve konuşma yapmış. Ayrıca Bologna Belediye binasına da İmamoğlu için destek sözleri içeren pankartlar asılmış. Tüm dünya demokratları bizimle.
April 5, 2025 at 5:06 PM
Reposted by Cem Say
AK Parti ve MHP’ye oy veren vicdanlı kardeşlerime sesleniyorum.

Herkes için, her zaman adalet.
April 4, 2025 at 7:54 AM
Reposted by Cem Say
Burada toplu block uygulaması var. Dünyanın en iyi uygulamasi. Mesela şu listeye girip sağ üstte tıklarsanız bir sürü zebaniyi tek seferde bloklayabilirsiniz. Önce isimlere bakın tabii, belki bloklamak istemedikleriniz vardır bsky.app/profile/did:...
April 3, 2025 at 8:01 PM
New paper; comments welcome.
March 28, 2025 at 2:00 PM
Bugün.
1024. kez.
February 20, 2025 at 10:58 AM
February 15, 2025 at 8:22 AM
Bu ülkenin en çalışkan gençlerinin torpilsiz hocalardan nitelikli eğitim alabildikleri gerçek, özgür, özerk bir üniversiteleri olabilsin diye.
February 12, 2025 at 8:23 PM
February 7, 2025 at 5:53 PM
20 Ocak 2025.
1001. kez.
January 21, 2025 at 8:29 AM