3 Search Results for "Hegselmann, Stefan"

Document

DOI: 10.4230/LIPIcs.MFCS.2025.40

Symmetric Proofs in the Ideal Proof System

Authors: Anuj Dawar, Erich Grädel, Leon Kullmann, and Benedikt Pago

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract

We consider the Ideal Proof System (IPS) introduced by Grochow and Pitassi and pose the question of which tautologies admit symmetric proofs, and of what complexity. The symmetry requirement in proofs is inspired by recent work establishing lower bounds in other symmetric models of computation. We link the existence of symmetric IPS proofs to the expressive power of logics such as fixed-point logic with counting and Choiceless Polynomial Time, specifically regarding the graph isomorphism problem. We identify relationships and tradeoffs between the symmetry of proofs and other parameters of IPS proofs such as size, degree and linearity. We study these on a number of standard families of tautologies from proof complexity and finite model theory such as the pigeonhole principle, the subset sum problem and the Cai-Fürer-Immerman graphs, exhibiting non-trivial upper bounds on the size of symmetric IPS proofs.

Cite as

Anuj Dawar, Erich Grädel, Leon Kullmann, and Benedikt Pago. Symmetric Proofs in the Ideal Proof System. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.MFCS.2025.40,
  author =	{Dawar, Anuj and Gr\"{a}del, Erich and Kullmann, Leon and Pago, Benedikt},
  title =	{{Symmetric Proofs in the Ideal Proof System}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.40},
  URN =		{urn:nbn:de:0030-drops-241477},
  doi =		{10.4230/LIPIcs.MFCS.2025.40},
  annote =	{Keywords: proof complexity, algebraic complexity, descriptive complexity, symmetric circuits, graph isomorphism}
}

Document

DOI: 10.4230/OASIcs.SLATE.2025.1

From Prediction to Precision: Leveraging LLMs for Equitable and Data-Driven Writing Placement in Developmental Education

Authors: Miguel Da Corte and Jorge Baptista

Published in: OASIcs, Volume 135, 14th Symposium on Languages, Applications and Technologies (SLATE 2025)

Abstract

Accurate text classification and placement remain challenges in U.S. higher education, with traditional automated systems like Accuplacer functioning as "black-box" models with limited assessment transparency. This study evaluates Large Language Models (LLMs) as complementary placement tools by comparing their classification performance against a human-rated gold standard and Accuplacer. A 450-essay corpus was classified using Claude, Gemini, GPT-3.5-turbo, and GPT-4o across four prompting strategies: Zero-shot, Few-shot, Enhanced, and Enhanced+ (definitions with examples). Two classification approaches were tested: (i) a 1-step, 3 class classification task, distinguishing DevEd Level 1, DevEd Level 2, and College-level texts in one single run; and (ii) a 2-step classification task, first separating College vs. Non-College texts before further classifying Non-College texts into DevEd sublevels. The results show that structured prompt refinement improves the precision of LLMs' classification, with Claude Enhanced + achieving 62.22% precision (1 step) and Gemini Enhanced + reaching 69.33% (2 step), both surpassing Accuplacer (58.22%). Gemini and Claude also demonstrated strong correlation with human ratings, with Claude achieving the highest Pearson scores (ρ = 0.75; 1-step, ρ = 0.73; 2-step) vs. Accuplacer (ρ = 0.67). While LLMs show promise for DevEd placement, their precision remains a work in progress, highlighting the need for further refinement and safeguards to ensure ethical and equitable placement.

Cite as

Miguel Da Corte and Jorge Baptista. From Prediction to Precision: Leveraging LLMs for Equitable and Data-Driven Writing Placement in Developmental Education. In 14th Symposium on Languages, Applications and Technologies (SLATE 2025). Open Access Series in Informatics (OASIcs), Volume 135, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dacorte_et_al:OASIcs.SLATE.2025.1,
  author =	{Da Corte, Miguel and Baptista, Jorge},
  title =	{{From Prediction to Precision: Leveraging LLMs for Equitable and Data-Driven Writing Placement in Developmental Education}},
  booktitle =	{14th Symposium on Languages, Applications and Technologies (SLATE 2025)},
  pages =	{1:1--1:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-387-4},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{135},
  editor =	{Baptista, Jorge and Barateiro, Jos\'{e}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2025.1},
  URN =		{urn:nbn:de:0030-drops-236817},
  doi =		{10.4230/OASIcs.SLATE.2025.1},
  annote =	{Keywords: Large Language Models (LLMs), Developmental Education (DevEd), writing assessment, text classification, English writing proficiency}
}

Document

DOI: 10.4230/LIPIcs.CSL.2016.35

Counting in Team Semantics

Authors: Erich Grädel and Stefan Hegselmann

Published in: LIPIcs, Volume 62, 25th EACSL Annual Conference on Computer Science Logic (CSL 2016)

Abstract

We explore several counting constructs for logics with team semantics. Counting is an important task in numerous applications, but with a somewhat delicate relationship to logic. Team semantics on the other side is the mathematical basis of modern logics of dependence and independence, in which formulae are evaluated not for a single assignment of values to variables, but for a set of such assignments. It is therefore interesting to ask what kind of counting constructs are adequate in this context, and how such constructs influence the expressive power, and the model-theoretic and algorithmic properties of logics with team semantics. Due to the second-order features of team semantics there is a rich variety of potential counting constructs. Here we study variations of two main ideas: forking atoms and counting quantifiers. Forking counts how many different values for a tuple w occur in assignments with coinciding values for v. We call this the forking degree of bar v with respect to bar w. Forking is powerful enough to capture many of the previously studied atomic dependency properties. In particular we exhibit logics with forking atoms that have, respectively, precisely the power of dependence logic and independence logic. Our second approach uses counting quantifiers E^{geq mu} of a similar kind as used in logics with Tarski semantics. The difference is that these quantifiers are now applied to teams of assignments that may give different values to mu. We show that, on finite structures, there is an intimate connection between inclusion logic with counting quantifiers and FPC, fixed-point logic with counting, which is a logic of fundamental importance for descriptive complexity theory. For sentences, the two logics have the same expressive power. Our analysis is based on a new variant of model-checking games, called threshold safety games, on a trap condition for such games, and on game interpretations.

Cite as

Erich Grädel and Stefan Hegselmann. Counting in Team Semantics. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gradel_et_al:LIPIcs.CSL.2016.35,
  author =	{Gr\"{a}del, Erich and Hegselmann, Stefan},
  title =	{{Counting in Team Semantics}},
  booktitle =	{25th EACSL Annual Conference on Computer Science Logic (CSL 2016)},
  pages =	{35:1--35:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-022-4},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{62},
  editor =	{Talbot, Jean-Marc and Regnier, Laurent},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2016.35},
  URN =		{urn:nbn:de:0030-drops-65757},
  doi =		{10.4230/LIPIcs.CSL.2016.35},
  annote =	{Keywords: logics with counting, team semantics, fixed-point logic with counting}
}

Refine by Type
3 Document/PDF
2 Document/HTML

Refine by Publication Year
2 2025
1 2016

Refine by Author
2 Grädel, Erich
1 Baptista, Jorge
1 Da Corte, Miguel
1 Dawar, Anuj
1 Hegselmann, Stefan
Show More...

Refine by Series/Journal
2 LIPIcs
1 OASIcs

Refine by Classification
1 Computing methodologies → Information extraction
1 Computing methodologies → Language resources
1 Computing methodologies → Lexical semantics
1 Computing methodologies → Natural language generation
1 Social and professional topics → Adult education
Show More...

Refine by Keyword
1 Developmental Education (DevEd)
1 English writing proficiency
1 Large Language Models (LLMs)
1 algebraic complexity
1 descriptive complexity
Show More...

3 Search Results for "Hegselmann, Stefan"

Symmetric Proofs in the Ideal Proof System

Abstract

Cite as

From Prediction to Precision: Leveraging LLMs for Equitable and Data-Driven Writing Placement in Developmental Education

Abstract

Cite as

Counting in Team Semantics

Abstract

Cite as

Thanks for your feedback!

Could not send message